3

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

13
  • 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.
    – Doc Brown
    Sep 1, 2014 at 6:06
  • @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.
    – VF1
    Sep 1, 2014 at 6:24
  • 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.
    – Doc Brown
    Sep 1, 2014 at 6:31
  • 1
    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
    Sep 1, 2014 at 10:59
  • 1
    @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.
    – david.pfx
    Sep 2, 2014 at 2:39

2 Answers 2

2

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.

3
  • 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?
    – Bill Door
    Sep 1, 2014 at 22:48
  • 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).
    – VF1
    Sep 2, 2014 at 2:28
  • @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.
    – Doc Brown
    Sep 2, 2014 at 6:15
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.

1
  • 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>.
    – VF1
    Sep 2, 2014 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.