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

我正在实现4个算法，它们完全是，除了它们使用的是什么数据结构 - 两个使用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类是一个禁忌。那么我该如何得到这种行为呢？

来源

2011-01-27 Joel McCance

你可以写一个非成员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-27 21:05:04

我正在实现一组搜索算法，所以我需要适配器的特定排序行为。（LIFO给我一个宽度优先的搜索，而FIFO给我深度优先，例如） – 2011-01-27 21:17:38

-1

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

来源

2011-01-27 20:57:16 aschepler

'的std :: priority_queue`，`的std :: stack`，和'的std :: queue`不是容器和他们都不是可迭代的序列。 – 2011-01-27 20:58:28

queue，priority_queue和stack都是容器适配器;它们是底层容器周围的包装（默认情况下，deque对于queue和stack和vector对于priority_queue）。

由于vector，deque和list（“真正的”容器类）共享他们的大部分方法，所以可以剪掉中间人并使用这些类。

并记住public继承对于STL容器并不是一个好主意; 私有继承是可以的（可能是你想要的）。

来源

2011-01-27 21:03:35

您可以在不使用继承的情况下创建一个围绕std::queue的包装;事实上，继承会因为你试图装饰一个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-27 21:04:15 templatetypedef

您可以使用偏特选择正确的方法：

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-27 21:10:04

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

回答

相关问题