如何編寫可以接受堆棧或隊列的函數模板？

我正在實現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

如何編寫可以接受堆棧或隊列的函數模板？

回答

相關問題