容器適配器

在c++常用的容器中，有的是以容器迭代器為核心，而有的則以容器適配器為核心。較為常用的就包括queue和stack。接下來(lái)我將簡(jiǎn)單的以queue和stack的模擬實(shí)現(xiàn)介紹其特點(diǎn)。

在以下的模擬實(shí)現(xiàn)中，class Con就是我們的容器適配器，他用于傳一個(gè)容器，默認(rèn)為deque類(lèi)模版，deque模版是一種奇妙的模版，他在頭部插入和刪除時(shí)，效率很高，擴(kuò)容效率也高，但是其不適合遍歷。當(dāng)我們想要實(shí)現(xiàn)某個(gè)類(lèi)，而剛好這個(gè)類(lèi)可以用其他類(lèi)的功能來(lái)直接實(shí)現(xiàn)，那么我們就可以將這個(gè)類(lèi)用另一個(gè)類(lèi)包裝起來(lái)。

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

仿函數(shù)

在學(xué)習(xí)priority_queue的時(shí)候，我們可以注意到他其中有一個(gè)參數(shù)是class?Compare?=?std::less，那么，這個(gè)std::less是什么呢？經(jīng)過(guò)查看，我們可以知道他是一個(gè)類(lèi)，他內(nèi)部包含了一個(gè)operator()，對(duì)()進(jìn)行了一次運(yùn)算符重載。再認(rèn)真看priority_queue中Compare出現(xiàn)的地方，我們可以發(fā)現(xiàn)，他廣泛的用于比較的地方。為何要如此定義？因?yàn)閜riority_queue本質(zhì)上就是一個(gè)堆，后面的Comepare本質(zhì)上就是決定他要建大堆還是小堆。而且在這還有一個(gè)反過(guò)來(lái)的地方，那就是如果你選的是less，那么他建的是大堆，即最大值在堆頂，這是和我們?nèi)粘Ｖ庇X(jué)不同的。

    template <class T>struct less{bool operator()(const T& left,const T& right){return left < right;}};template <class T>struct greater{bool operator()(const T& left, const T& right){return left > right;}};

接著讓我們看看在具體代碼中他的代碼，第一句是他的一句代碼，第二句是他的一個(gè)參數(shù)，comp是一個(gè)Compare類(lèi)型的類(lèi)對(duì)象。在第一句代碼中我們直接用comp包住兩個(gè)數(shù)據(jù)，這兩個(gè)數(shù)據(jù)分別會(huì)被帶入comp()符號(hào)的運(yùn)算符重載的左右參數(shù)。因此就會(huì)直接返回仿函數(shù)的結(jié)果。

if (child + 1 < c.size() && comp(c[child], c[child + 1]))Compare comp;

?

仿函數(shù)