2

I stumbled upon a specific instance where it seems that modularity and simplicity are at conflict with each other. Usually that's not the case, so I was really unsure how to resolve it.

Suppose I would like to make a queue interface:

template<typename T>
class queue {
 public:
  virtual ~queue() {}
  virtual void enqueue(const T& t) = 0;
  virtual void enqueue(T&& t) = 0;
  virtual T dequeue() = 0;
};

As I was making a couple implementations (some of which are atomic), I noticed that I could really save time by having an "abstract class" which called on empty() or full() methods to help implement condition variables. That way any synchronized class I implement could also just extend that "abstract class." The abstract class, in turn, implemented an extended interface:

template<typename T>
class bounded_queue : public queue<T> {
public:
  virtual ~bounded_queue() {}
  virtual bool full() = 0;
  virtual bool empty() = 0;
};

But wouldn't it be simpler if I just shoved those methods into queue, perhaps returning false by default? The answer to this question is not immediately obvious to me. If it is, then consider the other end of the spectrum.

I'm not even sure the above design (in the link) works as expected! How do I decide on something simple, yet modular?

  • They should be in same interface. Reason: full() is a condition whether you're allowed to call enqueue(), and empty() is a condition whether you're allowed to call dequeue(). Thus they should be in same interface. – tp1 Aug 2 '14 at 19:12
  • @tp1 Aren't you forcing boundedness on a generic queue? The generic queue is not aware of boundedness. By default, it is infinite (which is why in the case where we merge them it should be false by default). – VF1 Aug 2 '14 at 19:18
  • No the real problem is that to call enqueue, you must first check if the operation is allowed. Now If you have algorithm void algo(queue<int> &q); then that algo is NOT asking permission to call enqueue, and thus the algo would not work for bounded_queue. Thus the empty() and full() needs to be in original queue interface. – tp1 Aug 2 '14 at 19:21
1

They should be in the same interface. Bounded vs unbounded does not change this. The simple solution is to provide default implementations of isfull() and isempty() which a subclass can override. [My answer is much the same as comments by @tp1.]

If you do not provide empty(), how can a caller determine whether to request a dequeue or not?

You should also consider including a peek(). Once you implement isempty() then both dequeue() and peek() can block or raise an exception if called on an empty queue.

The general alternative is to provide several different types of queue. In this case a blocking queue might well be a different class, but with the same interface. However the same does not apply to an infinite queue, in which isfull() is never true.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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