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

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( ))。我知道我可以专门针对这种情况使用模板，但那样我就会有一大堆重复的代码(这是我试图避免的)。

实现此目标的最佳方法是什么？我的第一直觉是为队列创建一个包装类，它添加了一个等同于 stack 的 top() 操作，但我一直在读到 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)可能比使用其中一个序列适配器更直接。