如何编写一个函数模板，可以接受栈或队列作为参数？

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的实现方式做到了这一点，但是我无法像处理queue的算法那样处理，因为它使用不同的名称来访问最前面的元素(front( )而不是top( ))。我知道我可以针对这种情况进行特化模板，但那样会有很多重复的代码(这正是我想避免的)。

那么实现这个最好的方法是什么呢？我的第一反应是创建一个包装器类来为队列添加一个top( )操作，相当于stack，但我读到了关于子类化STL类的禁忌。那么我该如何获得这个行为呢？

- Joel McCance

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）可能会更加简单，而不是使用其中一个序列适配器。

- James McNellis

---

我正在实现一组搜索算法，因此我需要适配器的特定排序行为。（LIFO 给我广度优先搜索，而 FIFO 给我深度优先搜索，例如） - Joel McCance

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.  :(
}

- Fred Nurk

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

希望这能帮到你！

- templatetypedef

Answer 4

queue、priority_queue 和 stack 都是容器适配器，它们是对底层容器的包装（默认情况下，queue 和 stack 使用 deque，而 priority_queue 使用 vector）。

由于 vector、deque 和 list（真正的容器类）共享大部分方法，因此您可以省略中间人并直接使用这些类。

请记住，STL 容器不适合使用公有继承；私有继承是可以的（也可能是您想要的）。

- Etienne de Martel

Answer 5

front()和top()是特定于某些类型的容器，但所有STL容器都支持*begin()。

- aschepler

---

std::priority_queue、 std::stack 和 std::queue 都不是容器，也没有可迭代的序列。 - James McNellis