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

Question

我正在实现四种算法，除了使用的数据结构外，它们完全相同 - 两种使用 priority_queue，一种使用 stack，最后一种使用 priority_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）可能比使用序列适配器之一更直接。

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 的包装器；事实上，继承在这里是错误的工具，因为您试图装饰一个队列，而不是精炼或扩展 队列。这是一种可能的实现：

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

希望这有帮助！

Answer 4

queue、priority_queue 和 stack 都是容器适配器；它们是底层容器的包装器（默认情况下，queue 为 deque，stack 和 vector优先级队列）。

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

请记住，公共继承对于 STL 容器来说并不是一个好主意； 私有继承是可以的（可能也是你想要的）。

Answer 5

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