容器适配器
Stack
stack 是一种先进后出（First In Last Out）的数据结构，只有一个出口。stack 支持的操作：增加元素（push）、移除元素（pop）、获取最顶端元素（top）。stack 无遍历操作，无 iterator。使用时必须包含 <stack> 头文件。stack 底层以容器 Deque 实现，因为 stack 修改了 deque 的接口，使其以另一种风貌出现，故可称其为适配器（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）的数据结构，有两个出口。queue 支持的操作：增加元素（push）、移除元素（pop）、获取最前段元素（front）、获取最后的元素（back）。queue 无遍历操作，无 iterator。使用时必须包含 <queue> 头文件。queue 底层以容器 deque 实现，也是一种容器适配器。同样可以使用 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，其内的元素自动依照元素的权值排列，权值最高者，排在最前面。priority_queue 以 max-heap 实现其依据权值高低自动递减排序的特性，而 max-heap 底层则以容器 vector 实现。
// 摘自《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;
}
关联容器
Set
set 是一种关联容器，存储的对象既是键值（Key） 又是实值（Value）。
- 不允许有重复的 Key;
- 所有元素根据键值自动被排序；
- 存储的对象必须具备可排序性，默认采用less定义排序行为，存储对象必须具备 operator < 行为；
- 不能通过迭代器改变对象成员中真正的 Key；
- set 以 RB-tree 为底层机制；
- 相关算法有交集（set_intersection）、联集（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 是一种关联容器，存储的对象是键值与实值构成的数据对（Key/Value pair）。pair 的第一元素为 key，第二元素为 value。
- 不允许有重复的 Key;
- 所有元素根据键值自动被排序；
- 存储的对象必须具备可排序性，默认采用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内部没有像 set 那样采用 RB-tree，元素不会按任何顺序排序，而是通过以键值为参数的 hash 函数生成的 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 对，但内部并未像 map 那样采用 RB-tree，元素之间不会按任何顺序排列。 unordered_map 通过以键值 key 为参数的 hash 函数得到 hash 值，将元素分组放置到各个桶（bucket）中，这样就能通过键值快速地访问各个对应的元素（平均耗时为一个常量，即时间复杂度为O(1)）。
- 在访问容器中的某个元素时，unordered_map 容器比 map 容器高效，而在迭代容器元素的某个子集时，前者比后者稍微低效了一点；
- unordered_map 实现了直接访问操作符 []，使得可以通过键值 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 {
...
};
仿函数适配器
**bind1st 与 bind2nd **
bind1st和bind2nd函数用于将一个二元算子（binary functor，bf）转换成一元算子（unary functor，uf）。它们需要两个参数：要转换的二元算子 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
对于函数 f 以及对象 obj，在 obj 上调用 f 的形式可以有3种：
f(obj) // f 是全局函数，非 obj 成员函数
obj.f // f 是 obj 的成员函数，obj 非指针
obj->f // f 是 obj 的成员函数，obj 是指针
为了使 obj 的成员函数能够以第一种形式被调用，则需要使用 mem_fun 或 mem_fun_ref。当 obj 为指针时，将 obj 成员函数的引用作为参数传递给 mem_fun()，当 obj 非指针时，将obj成员函数的引用作为参数传递给 mem_fun_ref()。
