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,dequelist(“真正的”容器类)共享它们的大部分方法,因此您可以切断中间人并改用这些类。

请记住,公共继承对于 STL 容器来说不是一个好主意;私有继承是可以的(可能是你想要的)。

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

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

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