12 容器

12.1 引言

大多数计算任务都会涉及创建值的集合，然后对该集合执行某种操作。一个简单的例子是读取字符串并保存到string中，然后打印这个string对象中的字符串。如果一个类的主要用途就是保存对象，那么这个类就被称为容器（container）。为特定任务选择合适的容器，及其上有用的基本操作，是构建任何程序的重要步骤。

这里以一个保存姓名和电话号码的简单程序为例，说明标准库容器的用法。这就是那种对不同背景的人都显得简单而明显的程序。用户自定义的Entry类，用于表示一个简单的电话簿条目。例如：

xxxxxxxxxx
28
1
struct Entry {
2
    string name;
3
    unsigned long long number;
4
};
5

6
ostream& operator<<(ostream& os, const Entry& e) {
7
    return os << "{\"" << e.name << "\", " << e.number << '}';
8
}
9

10
istream& operator>>(istream& is, Entry& e) {
11
    char c, q;
12
    if (is >> c && c == '{' && is >> q && q == '"') { // 以“{”开始，后跟“"”，跳过空白字符
13
        string name; // string的默认值是空串
14
        while (is.get(c) && c != '"') // 读取两个“"”之间的姓名，空白字符也要读取
15
            name += c;
16

17
        if (is >> c && c == ',') { // 姓名和电话号码之间以“,”分隔，跳过空白字符
18
            unsigned long long number = 0;
19
            if (is >> number >> c && c == '}') { // 读取“}”之前的电话号码，跳过空白字符
20
                e = { name, number }; // 赋值给Entry对象
21
                return is;
22
            }
23
        }
24
    }
25

26
    is.setstate(ios_base::failbit); // 设置错误
27
    return is;
28
}

这里有意忽略了很多现实世界中的复杂因素，例如一个真正意义上的电话号码，未必能用一个“unsigned long long”类型的整数表示。

12.2 vector

最有用的标准库容器当属vector（动态数组）。vector就是一个特定类型元素的序列，其中的元素存储在一段连续的内存空间中。典型的vector实现会包含一个句柄，保存指向首元素的指针（elem）。此外，还包含一个指向尾元素下一个位置的指针（space），和一个指向所分配内存空间后第一个字节的指针（last）。另一些实现可能会用偏移量，等价地替代这些指针。除了这些指针（或者偏移量），vector还包含一个分配器（alloc），用于为容器中的元素分配内存空间。默认的分配器使用new和delete分配和释放内存。使用稍微先进一点的实现技术，就可以避免在vector对象中存储简单分配器的任何数据。

xxxxxxxxxx
13
1
 ________
2
| vector |
3
|--------|
4
|   last |___________________________
5
|  space |_______________            |
6
|   elem |___            |           |
7
|        |   v___________v___________v___________
8
|  alloc |   | 0 | 1 | 2 |   |   |   |
9
|________|   |___|___|___|___|___|___|___________
10
              \_________/ \_________/ \__________
11
                元素空间      额外空间     未分配空间
12
              \_____________________/
13
                      可用空间

可以用一组值来初始化vector，当然，值的类型必须与vector元素的类型一致。例如：

xxxxxxxxxx
5
1
vector<Entry> phoneBook{
2
    { "Zhang Fei", 13910110072 },
3
    { "Zhao Yun",  13512819007 },
4
    { "Guan Yu",   13044724277 }
5
};

可以通过下标访问vector中的元素。例如：

xxxxxxxxxx
2
1
for (int i = 0; i < phoneBook.size(); ++i)
2
    cout << phoneBook[i] << endl;

下标从0开始。vector的成员函数size，返回容器中元素的个数。

vector中的元素构成了一个范围，因此也可以使用基于范围的for循环，遍历其中的元素。例如：

xxxxxxxxxx
2
1
for (const auto& e : phoneBook)
2
    cout << e << endl;

创建vector容器时，可为其指定初始大小（元素数）。例如：

xxxxxxxxxx
4
1
vector<int> v1{ 1, 2, 3, 4, 5 }; // 初始大小为5，其值分别为1、2、3、4、5
2
vector<string> v2;               // 初始大小为0
3
vector<double> v4(5, 1.23);      // 初始大小为5，每个元素都是1.23
4
vector<double*> v5(5);           // 初始大小为5，每个元素都是nullptr

可以在一对圆括号中显式指定vector容器的初始大小，即初始元素数，如“vector<double*> v5(5)”。默认情况下，初始元素取默认值，如整型元素初始化为0，指针型元素初始化为nullptr。如果不想用默认值初始化容器中的元素，可以通过构造函数的第二个参数显式指定元素初值，如“vector<double> v4(5, 1.23)”。

vector容器的大小并非一成不变，随着程序的运行，新元素不断加入，其大小也会随之改变。vector最常用的一个操作就是push_back，它在元素序列的末尾追加一个新元素，从而使其大小加一。例如：

xxxxxxxxxx
2
1
for (Entry e; cin >> e;)
2
    phoneBook.push_back(e);

以上代码从标准输入读取Entry，并保存到phoneBook中，直至遇到文件尾或输入格式错误。

标准库的vector经过精心设计，即便不断调用push_back函数扩展vector中的元素序列，也不会导致性能下降。为了说明这一点，下面给出vector容器的形式化实现：

xxxxxxxxxx
40
1
template<typename T>
2
class vector {
3
private:
4
    allocator<T> alloc; // T类型元素的标准库分配器
5
    T*           elem;  // 指向首元素的指针
6
    T*           space; // 指向尾元素下一个位置的指针
7
    T*           last;  // 指向所分配内存空间后第一个字节的指针
8
    ...
9

10
public:
11
    // 获取元素数量
12
    int size() const {
13
        return space - elem;
14
    }
15

16
    // 获取可用空间
17
    int capacity() const {
18
        return last - elem;
19
    }
20

21
    // 扩展可用空间
22
    void reserve(int newcap) {
23
        ... 将可用空间扩大到足以容纳newcap个元素 ...
24
    }
25

26
    // 尾端追加元素
27
    void push_back(const T& t) {
28
        if (capacity() <= size()) // 可用空间不足
29
            reserve(size() ? size() * 2 : 8); // 扩充可用空间
30
        construct_at(space, t); // 在尾元素的下一个位置构建t的副本
31
        ++space;
32
    }
33

34
    // 尾端追加元素
35
    void push_back(T&& t) {
36
        ... 将t转移到元素序列尾端 ...
37
    }
38

39
    ...
40
};

标准库的vector类模板有capacity、reserve和push_back等几个成员函数。vector容器的使用者和其它成员函数都能通过reserve函数扩展可用空间，以容纳更多的元素。在此过程中可能需要重新分配内存，并将现有元素拷贝到新分配的内存中。当reserve函数将所有元素移至更大的可用空间后，所有之前取得的元素指针都将因此而失效，并不能再继续使用。

在push_back函数中，对可用空间的扩展采用启发式的倍增策略，如“reserve(size() ? size() * 2 : 8)”，以此降低执行内存分配和元素迁移的频率。也正是因为如此，vector容器的使用者通常很少在外部手动调用reserve函数，除非需要使用元素指针，为避免其因元素迁移而失效，而在最开始的时候通过reserve函数，一次性预留出足够的内存空间。

vector支持拷贝构造、拷贝赋值、转移构造和转移赋值。例如：

xxxxxxxxxx
4
1
vector<Entry> phoneBook2 = phoneBook;       // 拷贝构造
2
phoneBook = phoneBook2;                     // 拷贝赋值
3
vector<Entry> phoneBook3 = move(phoneBook); // 转移构造
4
phoneBook = move(phoneBook3);               // 转移赋值

这一切都是通过相应的构造函数和赋值操作符函数实现的。vector容器的拷贝，会连同其中的元素一起拷贝。当容器中包含很多元素时，这样一个看起来无害的初始化或赋值操作可能会非常耗时。因此，当拷贝并非必要时，应尽可能在容器中保存引用或指针。当然，以转移代替拷贝也是一个不错的选择。

标准库的vector非常灵活且高效，应当将其作为默认容器。换言之，除非有充分的理由使用其它容器，否则都应该使用vector。如果想以效率作为选择其它容器的理由，那么通过测试证明这一点是有必要的，毕竟有关容器性能方面的任何直觉，通常都不怎么靠得住。

12.2.1 元素

与所有标准库容器类似，vector是某种（T）类型元素的容器，即vector<T>。几乎任何类型都可以作为vector中元素的类型，包括但不限于内置的数值类型（char、int、double、······）、用户自定义类型（string、Entry、list<int>、Matrix<double, 2>、······）、指针类型（const char*、Shape*、double*、······），等等。当向一个vector容器存入元素时，它的值被拷贝到容器中。例如将整数7存入vector，vector中真的会有一个值为7的整数元素，而不是指向某个包含7的对象的引用或指针。这样的策略促成了精巧、紧凑、访问快速的容器。对于那些十分在意内存大小和运行时性能的开发者而言，这一点非常关键。

如果在一个类的层次结构中存在依赖于虚函数的多态性，那么就不应该在容器中保存对象，而应该保存对象的指针，或智能指针。例如：

xxxxxxxxxx
1
1
vector<Shape> shapes; // 错误，当存入Circle、Rectangle或Smiley对象时会发生对象截切，失去多态性

xxxxxxxxxx
1
1
vector<Shape*> shapes; // 好一些，保证了多态性，但当容器销毁时，被其管理的Shape对象不会随之销毁

xxxxxxxxxx
1
1
vector<unique_ptr<Shape>> shapes; // 最好，既保证了多态性，又规避了内存泄漏的风险

12.2.2 范围检查

vector的下标操作符（[]）并不进行范围检查。例如：

xxxxxxxxxx
1
1
cout << phoneBook[phoneBook.size()] << endl; // 下标越界

以上代码会导致什么样的输出，完全无法确定。类似这样的下标越界问题，并非程序设计者的本意，却又非常难以避免。vector的at成员函数，会在其表示下标的参数发生越界时，抛出一个类型为out_of_range的异常。例如：

xxxxxxxxxx
6
1
try {
2
    cout << phoneBook.at(phoneBook.size()) << endl; // invalid vector subscript
3
}
4
catch (const out_of_range& ex) {
5
    cerr << ex.what() << endl;
6
}

发生下标越界的代码会抛出一个异常，然后捕获该异常。如果用户不捕获该异常，程序会以良好定义的方式被终止运行，而不是继续执行或以未定义的方式失败。为了避免因未捕获异常而导致其它问题，可以将main函数的整个函数体放在一个try块中，并用“catch (...)”捕获所有未被显式捕获的异常。例如：

xxxxxxxxxx
14
1
int main() {
2
    try {
3
        ...
4
        cout << phoneBook.at(phoneBook.size()) << endl;
5
        ...
6
    }
7
    catch (const out_of_range& ex) {
8
        cerr << ex.what() << endl;
9
    }
10
    ...
11
    catch (...) {
12
        cerr << "unknown exception thrown" << endl;
13
    }
14
}

这段代码提供了默认的异常处理分支（catch (...) { ... }），因此，当某个异常未被其它catch成功捕获时，就会进入该分支，并在cerr上打印错误信息：unknown exception thrown。

vector的下标操作符（[]）为什么不做范围检查？有很多性能关键型应用程序都在使用vector，对所有下标操作都进行范围检查，意味着需要额外付出大约10%的性能开销。这么大的开销足以引发人们心中的恐惧，并导致他们最终放弃标准容器，而转投相对不安全的内置数组。现在，可以在调试阶段使用带范围检查的at函数，确认无误后，再在正式发布的版本中使用不带范围检查的下标操作符，以优化性能。

基于范围的for循环，通过隐式访问范围内的所有元素，零开销地避免了下标越界风险。只要参数有效，标准库算法都用类似的方法，保证在没有范围检查的前提下，不发生下标越界错误。

某些编译器还提供了一个编译选项，可以人为指定vector的下标操作符带不带范围检查。

12.3 list

标准库提供了名为list的双向线性链表容器：

如果希望在一个序列中插入、删除元素时无须移动其它元素，则可以使用list容器。对电话簿而言，插入、删除操作可能会很频繁，因此list容器很适合于简单电话簿的实现。例如：

xxxxxxxxxx
5
1
list<Entry> phoneBook{
2
    { "Zhang Fei", 13910110072 },
3
    { "Zhao Yun",  13512819007 },
4
    { "Guan Yu",   13044724277 }
5
};

象使用动态数组那样使用链表是不合适的。不能通过下标访问链表中的特定元素，但是可以在链表中搜索某个与给定条件匹配的元素。为了完成这样的操作，只需牢记list也是一个由其中的元素组成的序列即可。例如：

xxxxxxxxxx
7
1
unsigned long long getNumberByName(const list<Entry>& phoneBook, const string& name) {
2
    for (const auto& e : phoneBook)
3
        if (e.name == name)
4
            return e.number;
5

6
    return 0; // 返回0表示没有找到
7
}

getNumberByName函数从phoneBook链表的第一个元素开始搜索，直到找到姓名与name参数匹配的条目，返回该条目中的电话号码，或到达链表末尾，查找失败，返回0。

人们有时需要在list中定位一个元素，并在后续操作中删除这个元素，或该元素前面插入一个新元素。为此，可以使用迭代器。list的迭代器就象一个指向其中元素的指针，可用于对list中的每个元素做迭代遍历，这也正是“迭代器”一词的由来。每个标准库容器都提供begin和end两个成员函数，分别返回一个指向首元素的起始迭代器，和一个指向尾元素的下一个位置的终止迭代器。getNumberByName函数的迭代器版本如下，虽然不够优雅：

xxxxxxxxxx
7
1
unsigned long long getNumberByName(const list<Entry>& phoneBook, const string& name) {
2
    for (auto p = phoneBook.begin(); p != phoneBook.end(); ++p)
3
        if (p->name == name)
4
            return p->number;
5

6
    return 0; // 返回0表示没有找到
7
}

使用范围for循环的版本更简练，也更不容易出错。事实上，编译器对范围for循环的实现，基本上与迭代器版本一致。对于迭代器p，“*p”表示它所指向的元素，“++p”令它指向下一个元素，“--p”令它指向前一个元素。如果p所指向的元素是一个类类型的对象，且其包含一个名为m的成员，访问该成员可以使用“p->m”或者“(*p).m”。

向list中插入元素，以及从list中删除元素，都非常简单。例如：

xxxxxxxxxx
3
1
auto p = phoneBook.begin();
2
p = phoneBook.insert(++p, { "Huang Zhong", 13051205722 });
3
cout << *phoneBook.erase(--p) << endl;

对list而言，“insert(p,elem)”将一个新元素elem插到p所指向的元素之前，并返回指向新插入元素的迭代器，“erase(p)”删除并销毁p所指向的元素，同时返回指向被删除元素下一个位置的迭代器。在这两个操作中，p都可以是起始或者终止迭代器：

• insert(l.begin(),elem)：在首元素之前插入一个元素，被插入的元素成为新的首元素

• insert(l.end(),elem)：在尾元素之后插入一个元素，被插入的元素成为新的尾元素

• erase(l.begin())：删除首元素，被删除元素的下一个元素（如果存在）成为新的首元素

• erase(l.end())：空操作

以上这些例子里的list，都可以被等价地替换为vector。不可思议的是（除非充分了解机器的体系架构），vector的性能经常会优于list。一般而言，除非有充分的理由使用list，否则vector总是被优先选择的。vector无论是遍历（如find、count等），还是排序和搜索（如sort、binary_search等），性能都优于list。

12.4 forward_list

标准库提供了名为forward_list的单向线性链表容器：

forward_list和list的区别仅在于，它只有一个迭代方向，即forward_list的迭代器只能“++”不能“--”，这是由其单向链表的结构特点决定的。forward_list的价值在于它占用更少的内存空间，因为每个节点只需要保存一个指向下一个节点的指针。一个空forward_list的大小仅与一个指针相当。forward_list甚至不保存元素的个数。每次获取元素数，都要在遍历中统计。如果这个开销是无法容忍的，那么根本就不应该使用forward_list。

C++11：单向链表（forward_list）

12.5 map

在一个由键值对（比如姓名和电话号码）组成的序列中，根据键（比如姓名）顺序查找所对应的值（比如电话号码），是一件令人深感厌烦的工作。而且，除非这个序列足够短，顺序搜索的效率也会低到令人发指的地步。标准库提供了名为map的平衡二分搜索树（通常是红黑树）容器：

map亦称关联数组或者字典。

标准库的map是个键值对的容器，经过特殊优化可提高其搜索性能。可以向初始化vector或者list那样初始化map。例如：

xxxxxxxxxx
5
1
map<string, unsigned long long> phoneBook{
2
    { "Zhang Fei", 13910110072 },
3
    { "Zhao Yun",  13512819007 },
4
    { "Guan Yu",   13044724277 }
5
};

map也支持下标操作，不过下标值并非元素在序列中的序号，而应该是map的第一个类型参数型对象，作为键。下标操作的结果是map的第二个类型参数型对象，即与该键相对应的值。例如：

xxxxxxxxxx
3
1
unsigned long long getNumberByName(map<string, unsigned long long>& phoneBook, const string& name) {
2
    return phoneBook[name];
3
}

map下标操作的本质就是在平衡二分搜索树中执行一次搜索。如果map中存在与给定键匹配的键值对，则返回该键所对应的值，若没有该键，则插入一个新元素，键取给定的键，值取默认值。例如：

xxxxxxxxxx
2
1
cout << getNumberByName(phoneBook, "Zhao Yun") << endl;
2
cout << getNumberByName(phoneBook, "Huang Zhong") << endl; // 0

在本例中，unsigned long long类型整数的默认值是0，恰好用来表示无效的电话号码。如果不想将无效的电话号码添加到电话簿中，可以使用map的find成员函数，代替其下标操作。例如：

xxxxxxxxxx
7
1
unsigned long long getNumberByName(map<string, unsigned long long>& phoneBook, const string& name) {
2
    auto p = phoneBook.find(name);
3
    if (p != phoneBook.end())
4
        return p->second;
5

6
    return 0; // 返回0表示没有找到
7
}

12.6 unordered_map

搜索map的平均时间复杂度是$O(\log (n))$$O(\log(n))$，$n$$n$是map中的元素数。通常情况下，这样的性能表现已经相当完美了。假设map中包含100万个元素，最多只要执行20次比较和间接寻址操作，即可得到与查找目标匹配的元素。但在某些情况下，人们还希望能做得更好，那就要用哈希查找，取代顺序比较（如“<”）。标准库中的哈希容器也被称作无序容器，因为其中的元素不需要提供对顺序比较的支持。

例如：

xxxxxxxxxx
5
1
unordered_map<string, unsigned long long> phoneBook{
2
    { "Zhang Fei", 13910110072 },
3
    { "Zhao Yun",  13512819007 },
4
    { "Guan Yu",   13044724277 }
5
};

与map的情况的类似，unordered_map也支持下标形式的搜索、插入操作。例如：

xxxxxxxxxx
4
1
unsigned long long getNumberByName(unordered_map<string,
2
    unsigned long long>& phoneBook, const string& name) {
3
    return phoneBook[name];
4
}

和find成员函数。例如：

xxxxxxxxxx
8
1
unsigned long long getNumberByName(unordered_map<string,
2
    unsigned long long>& phoneBook, const string& name) {
3
    auto p = phoneBook.find(name);
4
    if (p != phoneBook.end())
5
        return p->second;
6

7
    return 0; // 返回0表示没有找到
8
}

标准库为所有内置类型和string等自定义类型，提供了默认的哈希函数。必要时，程序员可以自己定义哈希函数，特别是当元素中的键是某种自定义类型的对象时。哈希函数通常以函数对象的形式提供。例如针对自定义类型：

xxxxxxxxxx
4
1
struct Record {
2
    string name;
3
    int productCode;
4
};

的哈希函数：

xxxxxxxxxx
5
1
struct RecordHash {
2
    size_t operator()(const Record& r) const {
3
        return hash<string>()(r.name) ^ hash<int>()(r.productCode);
4
    }
5
};

在构造容器时指定哈希函数：

xxxxxxxxxx
1
1
unordered_map<Record, Value, RecordHash> m;

设计优秀的哈希函数是一门艺术，这需要对所处理的数据有深刻的认识。相比之下，通过按位异或（^）组合现有哈希函数的计算结果，常常更加简单而有效。当然，要注意确保所有的原始信息都参与了哈希值的运算，以提高不同元素的区分度，减少发生哈希冲突的机会。

还可以通过特例化标准库哈希函数模板的形式，提供针对自定义类型的自定义哈希函数。例如：

xxxxxxxxxx
10
1
namespace std {
2
    template<> struct hash<Record> {
3
        using argument_type = Record;
4
        using result_type = size_t;
5

6
        size_t operator()(const Record& r) const {
7
            return hash<string>()(r.name) ^ hash<int>()(r.productCode);
8
        }
9
    };
10
}

这样在构造容器时就可以避免显式提供哈希函数参数。例如：

xxxxxxxxxx
1
1
unordered_map<Record, Value> m;

注意map和unordered_map的区别：

• 放在map中的键值对，其中键需要支持顺序比较，通常是“<”操作符

• 放在unordered_map中的键值对，其中键无需支持顺序比较，但要支持相等性比较，通常是“==”操作符

在给定了优秀哈希函数的前提下，搜索unordered_map要比搜索map快得多，尤其是对包含海量元素的容器而言。但是，在最坏的情况下，比如配备了糟糕的哈希函数，unordered_map的性能可能远比map要差。

C++11：哈希容器（unordered_map、unordered_multimap、unordered_set和unordered_multiset）

12.7 分配器

默认情况下，标准库容器所持有的动态内存，都是通过new和delete操作符分配和释放的。标准库容器利用这些内存保存任意大小的对象，并负责管理这些对象的生命周期。但是，默认内存管理机制的时间和空间开销，未必总能尽如人意。为此，在某些特定情形下，标准库容器允许用户安装自定义的分配器，针对元素对象和使用场景的特殊性，提供更加高效且安全的动态内存管理策略。这种机制常被用于解决那些在编程实践中广泛存在的，诸如性能问题（如内存池化）、安全问题（如内存泄漏）、竞态问题（如内存共享），以及异构问题（如不同类型的对象适合使用不同的内存区域）等等。

假定有一个重要且长时间运行的系统，一到多个生产者线程负责向事件队列中压入事件对象，同时一到多个消费者线程从该队列中弹出事件并使用，每个事件的最后一个使用者会隐式地释放该事件所占用的内存空间：

xxxxxxxxxx
21
1
using namespace std;
2

3
struct Event {
4
    vector<int> data = vector<int>(512); // 每个事件对象均包含一个由512个整数组成的动态数组
5
};
6

7
list<shared_ptr<Event>> queue; // 指针链表形式的事件队列
8

9
void producer() { // 生产者线程的执行过程
10
    for (;;) {
11
        ... 线程同步操作 ...
12
        queue.push_back(make_shared<Event>()); // 创建一个事件对象并将其指针压入事件队列
13
        ... 线程同步操作 ...
14
    }
15
}
16

17
void consumer() { // 消费者线程的执行过程
18
    for (;;) {
19
        ...
20
    }
21
}

从逻辑上看，上面的代码会运行得很好，条理清晰，健壮且易维护。然而不幸的是，这会导致大量的内存碎片。当16个生产者和4个消费者处理了10万个事件后，6GB以上的内存将被碎片吞噬。

内存碎片问题的传统解决方案是使用内存池。内存池负责内存资源的实际分配与释放，借助精巧的生命周期策略，最大限度地复用已分配而未使用的内存，降低内存分配的频率，减少内存碎片的产生。

C++标准库通过名为synchronized_pool_resource的内存池分配器，支持上述功能。它被定义在std命名空间的pmr子空间中。例如：

xxxxxxxxxx
25
1
using namespace std;
2
using namespace std::pmr;
3

4
pmr::synchronized_pool_resource pool; // 基于内存池的分配器
5

6
struct Event {
7
    vector<int> data = vector<int>{ 512, &pool }; // 在内存池中分配动态数组
8
};
9

10
list<shared_ptr<Event>> queue{ &pool }; // 在内存池中创建链表
11

12
void producer() { // 生产者线程的执行过程
13
    for (;;) {
14
        ... 线程同步操作 ...
15
        queue.push_back(allocate_shared<Event,
16
            polymorphic_allocator<Event>>{ &pool }; // 在内存池中创建事件对象
17
        ... 线程同步操作 ...
18
    }
19
}
20

21
void consumer() { // 消费者线程的执行过程
22
    for (;;) {
23
        ...
24
    }
25
}

经过以上修改，当16个生产者和4个消费者处理了10万个事件后，内存碎片不会超过3M。这是近2000倍的改进！自然，实际使用的内存量并没有改变，改变的只是因碎片而浪费掉的部分。在消除了内存碎片以后，内存占用会在很长时间内保持稳定，系统可在数月甚至数年内持续、平稳地运行。

类似的技术在C++的早期阶段就已经被广泛地应用并获得很好的收益，但那个时候需要对每个特殊的容器重新编写代码。现在，标准库容器可以选择性地接受分配器参数。容器的默认分配器使用new和delete分配和释放内存。常用的多态分配器包括：

• synchronized_pool_resource：在多线程场景下使用的，基于内存池的分配器

• unsynchronized_pool_resource：在单线程场景下使用的，基于内存池的分配器

• monotonic_buffer_resource：在单线程场景下使用的，快速分配器，仅当分配器被销毁时，一次性释放所分配的内存

• memory_resource：所有内存分配器的公共基类，提供allocate、deallocate、is_equal等公有接口

C++17：多态分配器

12.8 容器概述

标准库提供了一些最通用也最具实用价值的容器类型：

程序员可以根据应用的需要选择最合适的容器。所有支持哈希查找的容器，也叫无序容器或者哈希容器，借助哈希表，对键（通常是字符串）的搜索进行了优化。

标准库容器都定义的std命名空间中，并通过<vector>、<deque>、<list>、<map>、<set>等头文件提供给使用者。此外，标准库还提供了一组适配器容器，如：stack<T>、queue<T>、priority_queue<T>等。标准库定义了两个仅用于特殊场合的容器：array<T,N>和bitset<N>。

站在使用者的角度，所有标准库容器都提供高度相似的基本操作，且具备一致的语义。下表列出的每一种基本操作，都可应用于多种容器：

形式和语义上的一致性，使程序员可以很容易地设计出自己的容器，并在使用方式上高度近似于标准库容器。另一方面，容器接口的一致性，还有助于设计出类型无关的泛型算法。但是，功能上的一致性，未必意味着性能上的一致性。例如在vector中插入或删除元素，往往伴随着元素的移动，相对于无需移动元素即可完成插入删除的list而言，效率差强人意。如果元素序列较短，元素对象本身也不大，那么vector通常比list更高效，即便是insert或erase操作亦是如此。一般的建议是，除非有足够的使用其它容器的理由，否则应尽量使用vector容器。

标准库还提供单向链表容器forward_list，这是一种针对空序列做了特别优化的容器。极端情况下，它只占用一个指针大小的内存空间，而即使是空vector，所占用的内存也不止一个指针。这种容器更适合存放那些经常为空，或只包含少量元素的序列。

就地（emplace）操作，比如emplace_back，只接受传递给元素类型构造函数的参数，并在容器中的恰当位置直接构建元素对象，而不是将容器外部的对象拷贝或转移一份到容器内部。例如：

xxxxxxxxxx
3
1
vector<pair<int, string>> v;
2
v.push_back(pair{ 1, "copy or move" }); // 在容器外部构建对象，再拷贝或转移到容器内部
3
v.emplace_back(1, "build in place");    // 直接在容器内部构建对象

当然，象上面这样的简单操作，优化器完全有能力将两种写法优化为同等性能。

C++11：哈希容器（unordered_map、unordered_multimap、unordered_set和unordered_multiset）

C++11：容器的emplace操作

12.9 建议

• STL标准库容器定义了一个序列

• STL标准库容器是资源句柄

• 将vector作为默认容器

• 对于容器的简单遍历，可以使用基于范围的for循环，或一对begin/end迭代器

• 使用reserve函数可以避免指向容器中元素的指针或迭代器，在容器内部发生结构性改变后失效

• 在未经测试的情况下，不要假定使用reserve函数一定能提升性能

• 在容器上使用push_back或resize操作，而不要在数组上使用realloc操作

• 不要在调整vector大小时使用迭代器

• 不要假定“[]”操作符有范围检查功能

• 如果范围检查是必须的，那就应该使用at成员函数，而非“[]”操作符

• 借助基于范围的for循环和标准库算法，可以零成本地避免对容器元素的越界访问

• 元素是被拷贝到容器中的

• 如要保持元素对象的多态行为，就不要在容器中保存对象本身，而要保存指向这些对象的指针

• vector执行insert或push_back操作的性能，可能会高于预期

• 对通常为空的序列，使用forward_list容器

• 任何事关性能的考虑，都不要相信直觉，而要实际测试

• map通常用红黑树实现

• unordered_map的内部结构是一张哈希表

• 将容器作为参数传递给函数时，应传引用，而从函数中返回容器时，则应返回值

• 初始化一个容器时，通过“( ... )”方式指定容器的初始元素个数，通过“{ ... }”方式指定容器的初始元素序列

• 优先选择紧凑型，连续存储元素的容器

• 遍历list的代价相对较高

• 如需在大量数据中做快速搜索，应优先选择无序容器

• 如需按顺序遍历容器中的元素，应优先选择有序容器

• 若容器中的元素类型没有自然顺序的概念，如无法为其定义“<”操作符，则不能选择有序容器

• 当需要在容器大小发生变化时，确保指向其中元素的指针始终有效，不要使用基于连续存储空间的容器

• 通过实验证明自定义的哈希函数足够令人满意

• 可将多个标准哈希函数返回的哈希值，用“^”操作符组合成新的哈希值

• 了解标准库容器，优先选择使用标准库容器，而不是自己实现容器

• 在遇到与内存相关的性能问题时，要么减少对自由存储的使用，要么考虑专门的分配器