5

我正在实现四种算法，除了它们使用的数据结构外，它们完全相同——两种使用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( )与 's 等效的操作stack，但我一直在读到子类化 STL 类是一个禁忌。那我应该如何得到这种行为呢？

4

5 回答 5

7

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）可能比使用序列适配器之一更直接。

于 2011-01-27T21:05:04.387 回答
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.  :(
}
于 2011-01-27T21:10:04.557 回答
1

std::queue您可以在不使用继承的情况下创建包装器；实际上，继承在这里是错误的工具，因为您试图装饰a而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;
};

希望这可以帮助！

于 2011-01-27T21:04:15.047 回答
0

queue,priority_queue并且stack都是容器适配器；它们是底层容器的包装器（默认为dequeforqueue和for ）。stackvectorpriority_queue

由于vector,deque和list（“真正的”容器类）共享它们的大部分方法，因此您可以切断中间人并改用这些类。

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

于 2011-01-27T21:03:35.613 回答
-1

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

于 2011-01-27T20:57:16.257 回答