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

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's 的操作,但我一直在读这个子类化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)而不是使用序列适配器之一可能更直接.