How can I write a function template that can accept either a stack or a queue?

Question

I'm implementing four algorithms that are completely identical except for what data structure they use — two use priority_queue, one uses stack, and the last uses queue. They're relatively long, so I'd like to have just one function template that accepts the container type as a template argument and then have each algorithm call that template with the appropriate argument, like so:

template <class Container>
void foo(/* args */)
{
    Container dataStructure;
    // Algorithm goes here
}

void queueBased(/* args */)
{
    foo<queue<Item> >(/* args */);
}

void stackBased(/* args */)
{
    foo<stack<Item> >(/* args */);
}

I've managed to do just this with the priority_queue- and stack-based implementations, but I can't do the same for the queue-based algorithm because it uses a different name to access the foremost element (front( ) instead of top( )). I know that I could specialize the template for this case, but then I'd have a big stretch of duplicated code (which is what I'm trying to avoid).

What's the best way to accomplish this? My first instinct was to create a wrapper class for queue that adds a top( ) operation equivalent to stack's, but I've been reading that subclassing STL classes is a no-no. How should I get this behavior, then?

Answer 1

You can write a non-member top function overloaded on the type of the container adapter:

template <typename T>
T& top(std::stack<T>& s) { return s.top(); }

template <typename T>
T& top(std::queue<T>& q) { return q.front(); }

// etc.

If you actually use a different sequence container with the container adapters (via their Sequence template parameter), you'll need to modify the overloads appropriately to handle that.

It might just be more straightforward to use a sequence container (e.g. std::vector) directly rather than using one of the sequence adapters.

Answer 2

You can use partial specialization to select the right method:

template<class Container>
struct foo_detail {
  static typename Container::value_type& top(Container &c) { return c.top(); }
  static typename Container::value_type const& top(Container const &c) { return c.top(); }
};
template<class T, class Underlying>
struct foo_detail<std::queue<T, Underlying> > {
  typedef std::queue<T, Underlying> Container;
  static typename Container::value_type& top(Container &c) { return c.front(); }
  static typename Container::value_type const& top(Container const &c) { return c.front(); }
};

template<class Container>
void foo(/* args */)
{
    Container dataStructure;
    // Use foo_detail<Container>::top(dataStructure) instead of dataStructure.top().
    // Yes, I know it's ugly.  :(
}

Answer 3

You can create a wrapper around std::queue without using inheritance; in fact, inheritance would be the wrong tool here because you're trying to decorate a queue rather than refining or extending the queue. Here's one possible implementation:

template <typename QueueType>
class QueueWrapper {
public:
    explicit QueueWrapper(const QueueType& q) : queue(q) {
        // Handled in initializer list
    }

    typedef typename QueueType::value_type value_type;

    value_type& top() {
        return queue.front();
    }
    const value_type& top() const {
        return queue.front();
    }

    void pop() {
        queue.pop();
    }
private:
    QueueType queue;
};

Hope this helps!