分配器

allocator 是一种 STL 标准，不同的编译器有不同的实现。

直接使用分配器，分配 512 个字节的整数。

1
2
int* p = allocator<int>().allocate(512);
allocator<int>().deallocate(p, 512);

注意 allocator<int>()语法，这里产生了一个临时对象（见《STL源码剖析》36页）。

VC、BC5、G2.9 的分配器没有任何独特设计，它们就是调用了 C 的 malloc() 和 free() 来分配和释放内存，而且它们的接口设计使得我们不太容易去用（没有程序员会去记忆申请的时候申请了 512个字节，释放的时候再释放 512 字节）。

G2.9 里面各种容器的默认分配器是 alloc，其实现如下 <stl_alloc.h>，其设计了 16 条单向链表，分别负责以 8 为倍数，不同字节大小的区块（例如 0 号链表负责大小为 8 字节的块，15 号链表负责大小为 128 字节的块）。这个设计节省了很多每次 malloc 时内存的额外开销。

G4.9 版本的默认分配器不再是 alloc，而是回到了VC、BC5的直接调用 C 的 malloc() 的方式，原因不得而知，但旧版的分配器仍然在，使用方式为：vector<string, __gnu_cxx::__pool_alloc<string>> vec

容器

以内缩方式表达内含(containment)关系，例如，heap内含一个vector，priority-queue内含一个heap等。

c++11中，slist 改名为 forward_list，以 hash_ 开头的容器，改名为以 unordered_ 开头的容器。

除了 vector 和 array 之外的所有容器的迭代器(iterator)，都必须是一个智能指针。

iterator 和 trits

熟悉的迭代器类型：输入、输出、前向、双向、随机。

vector

所在头文件：#include <vector>

迭代器：

基本操作：

list 双向链表

所在头文件：#include <list>

迭代器：

迭代器函数 功能
begin() 返回指向容器中第一个元素的双向迭代器（正向迭代器）。
end() 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。（正向迭代器）。
rbegin() 返回指向最后一个元素的反向双向迭代器。
rend() 返回指向第一个元素所在位置前一个位置的反向双向迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，正向迭代器增加了 const 属性，即不能用于修改元素。
cend() 和 end() 功能相同，只不过在其基础上，正向迭代器增加了 const 属性，即不能用于修改元素。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，反向迭代器增加了 const 属性，即不能用于修改元素。
crend() 和 rend() 功能相同，只不过在其基础上，反向迭代器增加了 const 属性，即不能用于修改元素。

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
  // 使用 bengin() 和 end() 输出 list 中的元素
  list<int> values = {1, 2, 3, 4, 5, 6};
  for (auto ite = values.begin(); ite != values.end(); ite++) {
    cout << *ite;
  }

  cout << endl;

  // 使用 rbengin() 和 rend() 输出 list 中的元素
  for (auto ite = values.rbegin(); ite != values.rend(); ite++) {
    cout << *ite;
  }

  return 0;
}

基本用法参考：C++ list（STL list）容器完全攻略（超级详细）

queue

所在头文件：#include <queue>

迭代器：

基本操作：

1
2
bool empty() const; // 判空
size_type size();

map

所在头文件：#include <unordered_map>

迭代器：

基本操作：

set

所在头文件：#include <unordered_set>

迭代器：

基本操作：