如何编写可以接受堆栈或队列的函数模板？

Question

除了使用什么数据结构之外，我正在实现四种完全相同的算法--两种使用priority_queue，一种使用stack，最后一种使用queue。它们相对较长，所以我希望只有一个函数模板，它接受容器类型作为模板参数，然后让每个算法用适当的参数调用该模板，如下所示：

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 */);
}

我成功地在priority_queue和stack-based实现中做到了这一点，但是对于queue-based算法却不能这样做，因为它使用不同的名称来访问最重要的元素(front( )而不是top( ))。我知道我可以为这个例子专门化模板，但是这样我就有了大量的重复代码(这正是我想要避免的)。

做这件事最好的方法是什么？我的第一反应是为队列创建一个包装类，它添加了一个与top( )类似的stack操作，但是我一直在读到，子类STL类是禁止的。那么，我应该如何获得这种行为呢？

Answer 1

可以在容器适配器的类型上重载非会员top函数：

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.

如果在容器适配器中使用不同的序列容器(通过它们的Sequence模板参数)，则需要适当地修改重载以处理这个问题。

直接使用序列容器(例如std::vector)可能比直接使用序列适配器更简单。

Answer 2

您可以使用部分专门化来选择正确的方法：

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

您可以在不使用继承的情况下为std::queue创建一个包装器；实际上，在这里，继承是一个错误的工具，因为您试图修饰一个queue，而不是细化或扩展queue。这里有一个可能的实现：

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;
};

希望这能有所帮助！