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).

• Doc Brown: I would use the bool try_dequeue(T* t) approach (though I prefer bool try_dequeue(T& t)), the restriction on T beeing "trivially constructible" is IMHO seldom a problem in any real-world case.
• VF1: @DocBrown but it'd also require operator=, which is generally frowned upon in certain style-guides-which-shall-not-be-named, and, style aside, may actually be a pain to implement depending on the type.
• Doc Brown: When using a container with the ability to put elements in and out, you can IMHO hardly avoid any real-world need for an assignment operator.
• david.pfx: Looks like T* dequeue() returning null for empty queue would meet all the requirements, even if that isn't the style you like.
• david.pfx: @C.R.: Exceptions are a major performance hit and act like gotos, they make it hard to manage state. Excellent for handling disasters, not recommended for 'normal' flow of control.

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.

• Bill Door: I wonder what the pointer or reference is pointing or referring too? dequeue would imply that the object is being removed from the queue. If the object is no longer on the queue, where does the responsibility for object life-time fall?
• VF1: Interestingly, I couldn't find a "rule of three" for move construction (move construct, move assign, destruct), just a "rule of five" on the wiki page. You'd think that the moving rule of three would be more popular, given that a lot of complex structures that can't easily be copied but can easily be moved (and most operations on standard containers only require the move-rule-of-three).
• Doc Brown: @BillDoor: see my edit, I added an example. The responsibility is similar to types like std::vector: the caller manages its object, the container his own objects, and putting things in and out is accomplished by copying.

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.

• VF1: Well, the return value can very well be a pointer - we can allocate a copy on the stack and return it, as would be the case with returning a unique_ptr<T>.