容器適配器
Stack
stack 是一種先進后出（First In Last Out）的數(shù)據(jù)結構秘噪，只有一個出口犁珠。stack 支持的操作：增加元素（push）、移除元素（pop）盼樟、獲取最頂端元素（top）同窘。stack 無遍歷操作，無 iterator附井。使用時必須包含 <stack> 頭文件讨越。stack 底層以容器 Deque 實現(xiàn)，因為 stack 修改了 deque 的接口永毅，使其以另一種風貌出現(xiàn)把跨，故可稱其為適配器（adapter），具體而言就是容器適配器卷雕。另外也可以 list 作為 stack 的底層容器节猿。
// 摘自《STL源碼剖析》
// file: 4stack-test.cpp
#include <stack>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
stack<int, list<int> > istack;
istack.push(1);
istack.push(3);
istack.push(5);
istack.push(7);
cout << istack.size() << endl; // 4
cout << istack.top() << endl; // 7
istack.pop(); cout << istack.top() << endl; // 5
istack.pop(); cout << istack.top() << endl; // 3
istack.pop(); cout << istack.top() << endl; // 1
cout << istack.size() << endl; // 1
}
Queue
queue 是一種先進后出（First In First Out）的數(shù)據(jù)結構票从，有兩個出口漫雕。queue 支持的操作：增加元素（push）、移除元素（pop）峰鄙、獲取最前段元素（front）浸间、獲取最后的元素（back）。queue 無遍歷操作吟榴，無 iterator魁蒜。使用時必須包含 <queue> 頭文件。queue 底層以容器 deque 實現(xiàn)吩翻，也是一種容器適配器兜看。同樣可以使用 list 作為 queue 的底層容器。
// 摘自《STL源碼剖析》
// file: 4queue-test.cpp
#include <queue>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
queue<int, list<int> > iqueue;
iqueue.push(1);
iqueue.push(3);
iqueue.push(5);
iqueue.push(7);
cout << iqueue.size() << endl; //4
cout << iqueue.front() << endl; // 1
iqueue.pop(); cout << iqueue.front() << endl; // 3
iqueue.pop(); cout << iqueue.front() << endl; // 5
iqueue.pop(); cout << iqueue.front() << endl; // 7
cout << iqueue.size() << endl; // 1
}
Priority_queue
priority_queue 是一個帶有權值觀念的 queue狭瞎，其內(nèi)的元素自動依照元素的權值排列细移，權值最高者，排在最前面熊锭。priority_queue 以 max-heap 實現(xiàn)其依據(jù)權值高低自動遞減排序的特性弧轧，而 max-heap 底層則以容器 vector 實現(xiàn)。
// 摘自《STL源碼剖析》
// file: 4pqueue-test.cpp
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int ia[9] = {0, 1, 2, 3, 4, 8, 9, 3, 5};
priority_queue<int> ipq(ia, ia + 9);
cout << "size = " << ipq.size() << endl; // size = 9
for (int i = 0; i < ipq.size(); ++i) {
cout << ipq.top() << ' '; // 9 9 9 9 9 9 9 9 9
}
cout << endl;
while (!ipq.empty()) {
cout << ipq.top() << ' '; // 9 8 5 4 3 3 2 1 0
ipq.pop();
}
cout << endl;
}
關聯(lián)容器
Set
set 是一種關聯(lián)容器碗殷，存儲的對象既是鍵值（Key） 又是實值（Value）精绎。
- 不允許有重復的 Key;
- 所有元素根據(jù)鍵值自動被排序；
- 存儲的對象必須具備可排序性锌妻，默認采用less定義排序行為代乃，存儲對象必須具備 operator < 行為；
- 不能通過迭代器改變對象成員中真正的 Key仿粹；
- set 以 RB-tree 為底層機制襟己；
- 相關算法有交集（set_intersection）引谜、聯(lián)集（set_union）、差集（set_difference）擎浴、對稱差集（set_symmetric_difference）员咽。
template < class T,
class Compare = less<T>,
class Alloc = allocator<T> >
class set {
...
};
Multiset
multiset 與 set 的特性及用法與 set 相同，差別在于 multiset 允許鍵值重復贮预，因此其插入操作采用的底層機制是 RB-tree 的 insert_equal()贝室，而 set中的插入操作則采用 RB-tree 的 insert_unique()。
Map
map 是一種關聯(lián)容器仿吞，存儲的對象是鍵值與實值構成的數(shù)據(jù)對（Key/Value pair）滑频。pair 的第一元素為 key，第二元素為 value唤冈。
- 不允許有重復的 Key;
- 所有元素根據(jù)鍵值自動被排序峡迷；
- 存儲的對象必須具備可排序性，默認采用less定義排序行為你虹，存儲對象必須具備 operator < 行為绘搞；
- 不能通過迭代器改變對象的 Key；
- map 以 RB-tree 為底層機制傅物；
template < class Key, class T,
class Compare = less<Key>,
class Alloc = allocator< pair<const Key, T> > >
class map {
...
};
Multimap
multimap 與 map 的特性和用法與 map 相同夯辖，差別在于 multimap 允許鍵值相同，因此其插入操作采用的底層機制是 RB-tree 的 insert_equal()董饰，而 map 中的插入操作則采用 RB-tree 的 insert_unique()蒿褂。
Unordered Set
unordered_set 容器中存儲的對象既是鍵值也是實值。元素的值是不可修改的卒暂，但可以刪除和插入啄栓。unordered_set內(nèi)部沒有像 set 那樣采用 RB-tree，元素不會按任何順序排序也祠，而是通過以鍵值為參數(shù)的 hash 函數(shù)生成的 hash 值將元素分組放置到各個桶（bucket）中昙楚，這樣就能通過鍵值快速地訪問各個對應的元素（平均耗時為一個常量，即時間復雜度為O(1)）齿坷。
- 在訪問容器中的某個元素時桂肌，unordered_set 容器比set 容器高效，而在迭代容器元素的某個子集時永淌，前者比后者稍微低效了一點崎场；
- unordered_set 容器支持正向迭代。
template < class Key,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator<Key> >
class unordered_set {
...
};
Unordered Map
在 unordered_map 容器像 map 一樣存儲 key/value 對遂蛀，但內(nèi)部并未像 map 那樣采用 RB-tree谭跨，元素之間不會按任何順序排列。 unordered_map 通過以鍵值 key 為參數(shù)的 hash 函數(shù)得到 hash 值，將元素分組放置到各個桶（bucket）中螃宙，這樣就能通過鍵值快速地訪問各個對應的元素（平均耗時為一個常量蛮瞄，即時間復雜度為O(1)）。
- 在訪問容器中的某個元素時谆扎，unordered_map 容器比 map 容器高效挂捅，而在迭代容器元素的某個子集時，前者比后者稍微低效了一點堂湖；
- unordered_map 實現(xiàn)了直接訪問操作符 []闲先，使得可以通過鍵值 key 直接訪問被映射的實值 value；
- unordered_map容器支持正向迭代无蜂。
template < class Key,
class T,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator< pair<const Key, T> > >
class unordered_map {
...
};
仿函數(shù)適配器
**bind1st 與 bind2nd **
bind1st和bind2nd函數(shù)用于將一個二元算子（binary functor伺糠，bf）轉換成一元算子（unary functor，uf）斥季。它們需要兩個參數(shù)：要轉換的二元算子 bf 和一個值 v训桶。
template <class _Fn2, class _Ty>
inline binder1st<_Fn2> bind1st(const _Fn2& Func, const _Ty& _Left)
{
typename _Fn2::first_argument_type _Val(_Left);
return (binder1st<_Fn>(_Func, _Val));
}
mem_fun 與 mem_fun_ref
對于函數(shù) f 以及對象 obj，在 obj 上調(diào)用 f 的形式可以有3種：
f(obj) // f 是全局函數(shù)酣倾，非 obj 成員函數(shù)
obj.f // f 是 obj 的成員函數(shù)舵揭，obj 非指針
obj->f // f 是 obj 的成員函數(shù)，obj 是指針
為了使 obj 的成員函數(shù)能夠以第一種形式被調(diào)用灶挟，則需要使用 mem_fun 或 mem_fun_ref琉朽。當 obj 為指針時毒租，將 obj 成員函數(shù)的引用作為參數(shù)傳遞給 mem_fun()稚铣，當 obj 非指針時，將obj成員函數(shù)的引用作為參數(shù)傳遞給 mem_fun_ref()墅垮。
