stack

Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.

上述描述出自cplusplus.

重點是stack是一個container adaptor也就是容器適配器。
這意味著我們不需要也沒有必要從0開始實現stack的方法，而可以通過一個模板，來調用其他容器來實現，以下是stack的部分從成員函數：

template<class T, class Container = deque<int>>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con.back();}private:Container _con;
};

可以發現只需要調用傳來的模板參數即可。

這里的默認容器是deque，這是一個均衡的容器，整體效率沒有vector高，但是可以實現push_front。這是vector做不到的，或者說vector的頭插效率是O(n)，過低。

值得注意的是，所有容器適配器都不支持迭代器。
就以stack舉例，如果支持迭代器，那是否意味著破壞了他的FILO特性呢？是的。因此不支持迭代器。

reverse_iterator

上文提到容器適配器，那就不得不提到反向迭代器了。
之前我們實現vector和list的時候都沒有實現反向迭代器，因為兩者內容過于相似，現在了解了反向迭代器的機制后我們知道，是否可以通過穿入迭代器容器，然后實現反向迭代器。

這意味著，我們可以同時實現所有容器的反向迭代器，也就是實現他們的模板：

template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *((--tmp));}Ptr operator->(){return &(operator*());}Self& operator++(){return --_it;}Self& operator--(){return ++_it;}bool operator!=(const Self& it){return _it != it;}};

需要注意的一點是，我們的operator*返回的是 *（--tmp)，而不是 *（tmp).

原因是，我們的rbegin（）和rend（）返回的是end()和begin（）。這是基于代碼對稱性考慮的，正常而言我們的rbegin（）和rend（）理應返回end()-1和begin（）-1.

為了解決這個問題，就只能令operator*返回 *（--tmp)。

注：以上實現是visual studio的實現方式。

queue

template<class T, class Container = deque<int>>
class queue
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& front(){return _con.front();}const T& back(){return _con.back();}private:Container _con;
};

priority_queue

priority_queue實質上就是一個堆，并且是默認大根堆。那么我們想要將其改變為小根堆改如何實現？
如果是C語言的話，我們會增加一個函數指針的參數來實現。
在C++中，我們通過傳入一個仿函數來實現。

仿函數

所謂仿函數就是指能夠像函數一樣使用的對象，如下：

template<class T>
class less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
void test(int x,int y)
{less l;if(l(x,y))cout<<"x<y";else cout<<"x>=y";
}

本質上，我們重載了 ()，因此能夠將這個對象像函數一樣使用。

具體代碼

堆的實現，我們已經講過，這里就不做贅述，感興趣的讀者可以翻閱我前面的文章。

template<class T,class Container=vector<T>,class Compare = less<T>>
class priority_queue
{
public://默認大堆void adjust_up(size_t child){size_t parent = (child - 1) / 2;Compare com;while (child >0){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 < _con.size() && com(_con[child],_con[child+1])){++child;}if (com(_con[parent],_con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;
};

說起來這里比較奇怪的點是，默認傳入less<T>是大根堆，而穿入greater<T>卻是小根堆。
但sort穿入，less<T>卻是升序排序：

int main()
{vector<int>v = { 1,5,4,3,2 };sort(v.begin(), v.end(),less<int>());//傳入less的匿名對象for (auto& e : v)cout << e << ' ';cout << endl;return 0;
}

Output:1 2 3 4 5