Are there alternatives to using an optional type in a multithreaded environment?

Question

I'm making an MPMC queue in C++, and I would like to find out what the best interface for a try_dequeue method would be (I'm not concerned about its implementation). I'd like to provide a method which does not block if the queue is empty (like my dequeue() method does), but somehow notifies this to the caller.

While I provide a bool empty() const method as well, this unfortunately does no good because for a multithreaded queue doing something along the lines of if(!queue.empty()) queue.dequeue(); provides no guarantees.

What I currently have is T try_dequeue(), which throws an exception if the queue is empty. This seems to offer the most intuitive interface, but an empty queue is hardly an exceptional situation, and that seems an awful lot like using exceptions for control flow.

Another option would be bool try_dequeue(T* t), which would write to t only if the queue was not empty and return if t was written to. After using the exception method above, this seems probably least intrusive, but it would require that T is both default-constructible (or in some manner trivially constructible, so the caller can do T t; queue.try_dequeue(&t);) and assignable.

I wouldn't want to force those requirements on T, though, so perhaps a Java-like approach such as optional<T> try_dequeue() is in order. One of the minor issues with this is that I'd have to implement my own (can't use boost). Perhaps more importantly, it makes the interface seem bloated, in the sense that now I'm now dragging another type in where it would (hopefully) be avoidable, and, much like the situation with STL's set::insert requires us to copy a pair, then "unfold" its arguments, it forces the user into clumsy, long ritual that has to be repeated every time he or she uses the function.

Perhaps I'm worrying too much about optional<T>'s usability, given that it doesn't have any of the more serious problems that the other two approaches do, but I'm wondering, what would be the best approach here? Is it the optional one?

Edit: It occurred to me that there's also a bit of an outlandish bool try_dequeue(std::function<void(T&)>) option which actually seems pretty nice (in fact this one will actually have the most minimal interface you can have, where there's no need for any external logic setting a local T to the returned value). Unfortunately I'd prefer to avoid the overhead incurred by calling an actual std::function, and using a template function template<class F> bool try_deque(const F&) isn't an option either since this is a derived class (from a generic queue interface).

Answer 1

As long as the task is not to design a 100% generic lib for each and every case, only a queue for types "T" under your teams control, I would prefer the bool try_dequeue(T* t) approach, or even better bool try_dequeue(T& t) (since T* t must never be NULL). By this design, the usage will typically look like this:

  T t;
  if(try_dequeue(t))
  {
     // do something  with t;
  }

and the implementation will look like this:

  bool try_dequeue(Type &t)
  {
      // ... make things thread-safe
      // ... return false if queue is empty
      // ... find index to your storage array
      t=queueStorage[foundIndex];
      // ... remove element at "foundIndex" from "queueStorage"
      return true;
  }

This imposes some requirements on your type T: it will need a "simple" (probably parameterless) ctor, and it needs a "copy assignment operator". A copy constructor won't be enough. For many real-world types, these requirements are easy to fulfill (especially when they are under your control). Note, that according to the rule of three it is most times good idea to implement not only a user defined copy ctor alone, so if your current type T has only such a copy ctor, consider to add a copy assignment operator as well.

Answer 2

Using the process of elimination.

Assumption - the queue is value-based. The same as std::vector, etc.

Assumption - try_dequeue will remove the value from the queue if the value is available and return the value to the caller. Technically, being value based means that the value is copied or moved to the caller.

The return type cannot be a pointer or a reference. The queue only has values. Once the value is removed from the queue, a pointer or reference cannot be maintained. Therefore a value must be returned.

You sited three potential solutions in reverse order of preference.

1. throw an exception. (ick)
2. return std::pair<T, bool> i.e. like std::set
3. return optional<T>

The last two are quite similar syntactically. Some helper functions could make option 2 more tolerable.