第12章容器

南风2024年10月26日大约 24 分钟

第12章容器

简介
vector
元素；
范围检查
list
forward_list
map
unordered_map
分配器
容器概述
建议

12.1 简介

大多数计算涉及创建值的集合，然后对这些集合进行操作。将字符读入 字符串 并打印出 字符串 是一个简单的例子。一个类的主要目的是持有对象，通常被称为容器。为给定任务提供合适的容器，并支持有用的基本操作是构建任何程序的重要步骤。

为了说明标准库容器，考虑一个用于保存姓名和电话号码的简单程序。这种程序对于具有不同背景的人来说，会出现不同且看似“简单明了”的处理方式。可以使用第11.5节中的 Entry 类来保存一个简单的电话簿条目。在这里，我们故意忽略了许多现实世界的复杂性，例如许多电话号码无法简单地用32位 int 表示这一事实。

12.2 vector

最实用的标准库容器是 vector 。 vector 是一系列给定类型的元素。这些元素在内存中连续存储。 vector 的一个典型实现（参见§5.2.2, §6.2）将包括一个句柄，该句柄持有指向第一个元素、最后一个元素之后的位置以及最后一个已分配空间之后的位置（参见§13.1）的指针（或等效的以指针加偏移量表示的信息）：

此外，它还包含一个分配器（这里称为alloc）， vector 可以通过这个分配器为其元素获取内存，默认的分配器使用 new 和 delete 来获取和释放内存（§12.7）。使用稍微高级一点的实现技术，我们可以避免在 vector 对象中为简单的分配器存储任何数据。

我们可以使用元素类型的特定值的集合来初始化一个 vector ：

vector<Entry> phone_book = {
    {"流萤",123456},
    {"黄泉",234567},
    {"黑天鹅",345678}
};

可以通过下标访问元素。因此，假设我们已经为 Entry 定义了 << 运算符，我们可以这样写：

void print_book(const vector<Entry>& book)
{
    for (int i = 0; i != book.size(); ++i)
        cout << book[i] << '\n';
}

像往常一样，索引从 0 开始，所以 book[0] 保存的是流萤的条目。 vector 的成员函数 size() 给出元素的数量。

vector 的元素构成一个范围，因此我们可以使用范围 for 循环（参见§1.7）：

void print_book(const vector<Entry>& book)
{
    for (const auto& x : book) // §1.4
        cout << x << '\n';
}

当我们定义一个 vector 时，会给出它的初始大小（即初始元素数量）：

vector<int> v1 = {1, 2, 3, 4};       // 大小为 4
vector<string> v2;                  // 大小为 0
vector<Shape*> v3(23);             // 大小为 23；初始元素值：nullptr
vector<double> v4(32,9.9);         // 大小为 32；初始元素值：9.9

显式的初始大小被括在普通的圆括号中，比如 (23) ，默认情况下，元素会被初始化为元素类型的默认值（例如，指针为 nullptr ，数字为 0 ）。如果你不希望使用默认值，可以在第二个参数中指定一个（例如， v4 的32个元素初始化为 9.9 ）。

初始大小是可以改变的。 vector 上最有用的操作之一是 push_back() ，它在 vector 的末尾添加一个新的元素，使 vector 的大小增加一。例如，假设我们已经为 Entry 定义了 >> 运算符，我们可以这样写：

void input()
{
    for (Entry e; cin >> e; )
        phone_book.push_back(e);
}

这会从标准输入读取 Entrys 到 phone_book ，直到遇到输入结束（例如，文件结束）或输入操作遇到格式错误。

标准库中的 vector 被设计得通过重复调用 push_back() 扩容时效率很高。为了展示如何做到这一点，让我们基于第5章和第7章中的简单 Vector 类进行扩展，并使用上图所示的表示方法：

template<typename T>
class Vector {
    allocator<T> alloc;          // 标准库分配器，用于为T分配空间
    T* elem;                     // 指向第一个元素的指针
    T* space;                    // 指向第一个未使用（且未初始化）槽的指针
    T* last;                     // 指向最后一个槽的指针

public:
    // ...
    int size() const { return space - elem; }      // 元素数量
    int capacity() const { return last - elem; }   // 可供元素使用的槽数量
    // ...
    void reserve(int newsz);     // 将容量增加到newsz
    // ...
    void push_back(const T& t);  // 将t复制到Vector中
    void push_back(T&& t);       // 将t移动到Vector中
    // ...
};

标准库中的 vector 包含 capacity() 、 reserve() 和 push_back() 成员。用户使用 reserve() 来为 vector 预留更多元素的空间。它可能需要分配新的内存，当这样做时，它会将元素移动到新分配的内存上。当 reserve() 将元素移动到更大且新的空间时，任何指向这些元素的指针现在都会指向错误的位置；它们已经变得无效，不应再使用。

有了 capacity() 和 reserve() ，实现 push_back() 就很简单了：

template<typename T>
void Vector<T>::push_back(const T& t)
{
    if (capacity() <= size())     // 确保有空间存放t
        reserve(size() == 0 ? 8 : 2 * size()); // 容量翻倍
    construct_at(space, t);       // 初始化*space为t
    ++space;
}

现在，分配和重定位元素只发生在很少的情况下。我过去常常使用 reserve() 来尝试提高性能，但结果证明这是徒劳的： vector 所使用的启发式方法平均而言比我猜测的要好，因此现在我仅在需要避免元素重新分配而我又想要使用指向元素的指针时才明确使用 reserve() 。

vector 可以在赋值和初始化中被复制。例如：

vector<Entry> book2 = phone_book;

vector 的复制和移动通过构造函数和赋值运算符实现，如 §6.2 所述。赋值一个 vector 涉及到复制其元素。因此，在 book2 初始化后， book2 和 phone_book 分别持有电话簿中每个 Entry 的独立副本。当 vector 持有大量元素时，这种看似无辜的赋值和初始化可能会非常昂贵。在不希望进行复制的情况下，应使用引用或指针（参见 §1.7）或移动操作（参见 §6.2.2）。

标准库中的 vector 非常灵活且高效。将其作为你的默认容器使用；也就是说，除非你有充分的理由使用其他容器，否则请使用它。如果你因为对“效率”的模糊担忧而避免使用 vector ，那么请进行测量。在容器使用性能的问题上，我们的直觉最容易出错。

12.2.1 元素

与所有标准库容器一样， vector 是某种类型 T 的元素的容器，即 vector<T> 。几乎任何类型都可以作为元素类型：内置的数值类型（如 char 、 int 和 double ）、用户自定义类型（如 string 、 Entry 、 list<int> 和 Matrix<double,2> ）以及指针（如 const char* 、 Shape* 和 double* ）。当你插入一个新元素时，它的值会被复制到容器中。例如，当你将一个值为 7 的整数放入容器中时，生成的元素实际上具有值 7 。这个元素不是一个引用或指向某个包含 7 的对象的指针。这让容器变得简洁，访问速度快。对于关心内存大小和运行时性能的人来说，这是至关重要的。

如果你有一个依赖虚拟函数获得多态行为的类层次结构（参见 §5.5），不要直接在容器中存储对象。相反，应该存储一个指针（或智能指针；参见 §15.2.1）。例如：

vector<Shape> vs; // 不，不要这样做 - 没有空间存放 Circle 或 Smiley（§5.5）
vector<Shape*> vps; // 更好，但请参阅 §5.5.3（避免内存泄漏）
vector<unique_ptr<Shape>> vups; // 正确

12.2.2 范围检查

标准库中的 vector 并不保证进行范围检查。例如：

void silly(vector<Entry>& book)
{
    int i = book[book.size()].number;// book.size() 超出了有效范围
    // ...
}

这样的初始化很可能将某个随机值赋给 i ，而不是给出错误提示。这是不理想的，超出范围的错误是常见的问题。因此，我经常使用一个简单的、增加了范围检查功能的 vector 适配版：

template<typename T>
struct Vec : std::vector<T> {
    using vector<T>::vector; // 使用 vector 的构造函数（Vec名下）

    T& operator[](int i) { return vector<T>::at(i); } // 范围检查
    const T& operator[](int i) const { return vector<T>::at(i); } // 对常对象也进行范围检查  §5.2.1

    auto begin() { return Checked_iter<vector<T>>{*this}; } //  §13.1
    auto end() { return Checked_iter<vector<T>>{*this, vector<T>::end()}; }
};

对于 Vec ，超出范围的访问会抛出异常，用户可以捕获这个异常。例如：

void checked(Vec<Entry>& book)
{
    try {
        book[book.size()] = {"知更鸟", 999999};// 将会抛出异常并被捕获
        // ...
    }
    catch (out_of_range&) {
     	cerr << "范围错误\n";
    }
}

异常会被抛出并随后被捕获。如果用户没有捕获某个异常，程序将以一种明确定义的方式终止，而非以不确定的方式继续运行或失败。减少未捕获异常导致意外的一种方式是在 main() 函数中使用一个 try 块作为主体。例如：

int main()
    try {
        // 你的代码
    }
catch (out_of_range&) {
    cerr << "范围错误\n";
}
catch (...) {
    cerr << "未知异常被抛出\n";
}

这样提供了默认的异常处理器，即使未能捕获某些异常，也会在标准错误输出流 cerr 上打印错误消息（参见 §11.2）。

为什么标准库不保证范围检查呢？许多对性能敏感的应用程序使用 vector ，而对所有下标操作进行检查会引入大约 10% 的开销。显然，这一开销会根据硬件、优化器及应用程序对下标操作的使用情况而有很大差异。然而，经验表明，这样的开销可能会导致人们更倾向于使用远不安全的内置数组。即使只是担心这样的开销也可能导致不去使用 vector 。至少 vector 在调试时容易进行范围检查，并且我们可以在未经检查的默认版本之上构建检查过的版本。

使用范围 for 循环可以在不增加额外成本的情况下避免范围错误，因为它隐式地访问了范围内的所有元素。只要它们的参数是有效的，标准库算法也会做同样的事情来确保没有范围错误。

如果你直接在代码中使用 vector::at() ，则不需要我的 Vec 解决方案。此外，一些标准库提供了带有更完整检查功能的范围检查型 vector 实现，比 Vec 提供的功能更全面。

12.3 list

标准库提供了一种名为 list 的双向链表：

当我们使用链表时，往往不会像使用 vector 那样通过下标访问元素。相反，我们可能会搜索链表，寻找具有特定值的元素。为此，我们可以利用链表作为一种序列的事实，如第13章所述：

int get_number(const string& s)
{
    for (const auto& x : phone_book)
        if (x.name == s)
            return x.number;
    return 0; // 使用0表示“号码未找到”
}

对 s 的搜索从链表的开头开始，一直进行到找到 s 或到达 phone_book 的末尾。

有时，我们需要识别链表中的一个元素。例如，我们可能想删除一个元素或在其之前插入新元素。为此，我们使用 迭代器 ：链表迭代器标识链表中的一个元素，并可用于遍历链表（因此得名）。每个标准库容器都提供了 begin() 和 end() 函数，分别返回指向第一个元素和最后一个元素之后位置的迭代器（参见§13.1）。明确使用迭代器，我们可以不太优雅地这样编写 get_number() 函数：

int get_number(const string& s)
{
    for (auto p = phone_book.begin(); p != phone_book.end(); ++p)
        if (p->name == s)
            return p->number;
    return 0; // 使用0表示“号码未找到”
}

实际上，编译器大致就是这样实现更紧凑且不易出错的范围 for 循环的。给定迭代器 p ， *p 就是它所指的元素， ++p 使 p 前进到指向下一个元素，如果 p 指向一个具有成员 m 的类，则 p->m 等价于 *(p).m 。

向链表添加元素和从链表中移除元素很容易：

void f(const Entry& ee, list<Entry>::iterator p, list<Entry>::iterator q)
{
    phone_book.insert(p, ee);  // 在p所指元素之前添加ee
    phone_book.erase(q);       // 移除q所指的元素并销毁它
}

对于链表， insert(p, elem) 在由 p 指向的元素之前插入一个 elem 副本的值。这里， p 可以是指向链表末尾之外的迭代器。相反， erase(p) 移除 p 所指向的元素并销毁它。

这些链表示例也可以完全使用 vector 编写（令人惊讶的是，除非你了解机器架构，否则通常使用 vector 的性能会优于使用 list ）。当我们只需要一个元素序列时，可以在使用 vector 和 list 之间做出选择。除非有理由不这么做，否则使用 vector 。对于遍历（例如， find() 和 count() ）以及排序和搜索（例如， sort() 和 equal_range() ；§13.5, §15.3.3）， vector 通常表现更好。

12.4 forward_list

标准库还提供了一个称为 forward_list 的单向链表：

forward_list 与（双向链表） list 的区别在于仅允许向前迭代。这样做的目的是节省空间。没有必要在每个链接中保持一个前驱指针，空 forward_list 的大小仅是一个指针的大小。 forward_list 甚至不保存其元素的数量。如果你需要知道元素的数量，就去计数。如果无法承受计数的开销，那么你可能不应该使用 forward_list 。

12.5 map

在包含（ name,number） 对的列表中查找名称的代码编写相当繁琐。此外，对于除了最短列表之外的所有列表，线性搜索都是低效的。标准库提供了一种称为 map 的平衡二叉搜索树（通常是红黑树）：

在其他上下文中， map 也被称为关联数组或字典。

标准库中的 map 是一对值的容器，针对查找和插入进行了优化。我们可以使用与 vector 和 list 相同的初始化器（参见 §12.2, §12.3）：

map<string, int> phone_book {
    {"流萤",123456},
    {"黄泉",234567},
    {"黑天鹅",345678}
};

当通过其第一个类型（称为键）索引时， map 会返回第二个类型对应的值（称为值或 映射类型 ）。例如：

int get_number(const string& s)
{
    return phone_book[s];
}

换句话说，对 map 进行下标操作本质上就是我们之前称为 get_number() 的查找操作。如果找不到键，它将被输入到 map 中，并赋予其值类型的默认值。对于整数类型，默认值为 0 ，这正好是一个合理的值来表示无效的电话号码。

如果我们想避免将无效号码输入到电话簿中，我们可以使用 find() 和 insert() （参见 §12.8）代替下标操作。

12.6 unordered_map

map 查找的成本是 O(log(n)) ，其中 n 是 map 中的元素数量。这已经相当不错了。例如，在一个包含1,000,000个元素的映射中，我们只需进行大约20次比较和间接寻址就可以找到一个元素。然而，在许多情况下，我们可以通过使用更好的哈希查找而不是使用排序函数（如 < ）进行比较。标准库中的哈希容器因其不需要排序函数而被称为“无序”

例如，我们可以使用来自 <unordered_map> 的 unordered_map 来管理电话簿：

unordered_map<string, int> phone_book {
    {"流萤",123456},
    {"黄泉",234567},
    {"黑天鹅",345678}
};

和 map 一样，我们可以对 unordered_map 进行下标操作：

int get_number(const string& s)
{
    return phone_book[s];
}

标准库为 字符串 以及其他内置标准库类型提供了默认的哈希函数。如有必要，我们也可以提供自己的哈希函数。可能最常见的自定义哈希函数需求出现在我们想要一个自己类型的无序容器的时候。哈希函数通常实现为函数对象（参见 §7.3.2）。例如：

struct Record {
    string name;
    int product_code;
    // ...
};

struct Rhash {// 为Record类型提供的哈希函数
    size_t operator()(const Record& r) const
    {
        return hash<string>()(r.name) ^ hash<int>()(r.product_code);
    }
};

unordered_set<Record, Rhash> my_set; // 使用Rhash进行查找的Record集合

设计良好的哈希函数是一门艺术，通常需要了解将应用于的数据。通过 异或（^） 操作结合现有哈希函数创建新的哈希函数既简单又通常非常有效。但是，务必确保参与哈希的每个值都能真正有助于区分值。例如，除非同一个产品代码可以对应多个名称（或者同一个名称可以对应多个产品代码），否则将两个哈希值合并在一起并无益处。

我们可以通过定义为标准库 hash 的特化来避免显式传递哈希操作：

namespace std {// 为Record提供哈希函数
    template<> struct hash<Record> {
        using argument_type = Record;
        using result_type = size_t;

        result_type operator()(const Record& r) const
        {
            return hash<string>()(r.name) ^ hash<int>()(r.product_code);
        }
    };
}

注意 map 和 unordered_map 之间的区别：

map 需要一个排序函数（默认为 < ）并且产生有序序列。
unordered_map 需要一个相等性判断函数（默认为 == ）；它不对元素维护特定顺序。

对于大型容器，给定一个好的哈希函数， unordered_map 比 map 快得多。然而，如果哈希函数不好， unordered_map 的最坏情况行为远比 map 差。

12.7 Allocator

默认情况下，标准库容器使用 new 分配空间。操作符 new 和 delete 提供了一个通用的自由存储区（也称为动态内存或堆），可以容纳任意大小的对象以及用户控制的生命周期。这暗示了在许多特殊情况下可以消除的时间和空间开销。因此，标准库容器提供了在需要的地方安装具有特定语义的 分配器 的机会。这已被用来解决与性能（例如，池分配器）、安全（作为删除过程一部分清理内存的分配器）、线程间分配以及非统一内存架构（在特定内存中分配并使用匹配的指针类型）相关的广泛问题。这不是讨论这些重要但高度专业化且通常很高级技术的地方。然而，我将给出一个由现实世界问题驱动的例子，该问题的解决方案是使用池分配器。

一个重要的,长期运行的系统使用事件队列（参见第18.4节），其中事件是以 shared_ptr 传递的 vector 。这样，事件的最后一个使用者会隐式地删除它：

struct Event {
    vector<int> data = vector<int>(512); // 初始化一个包含512个整数的vector
};

list<shared_ptr<Event>> q; // 事件队列

void producer() {
    for (int n = 0; n != LOTS; ++n) {
        lock_guard lk {m}; // m是一个互斥锁（mutex §18.3）
        q.push_back(make_shared<Event>());
        cv.notify_one(); // cv是一个条件变量 §18.4
    }
}

从逻辑角度来看，这个设计工作得很好。逻辑简单，代码健壮且易于维护。不幸的是，这导致了严重的碎片化。在16个生产者和4个消费者之间传递了10万个事件后，消耗了超过6GB的内存。

解决碎片化问题的传统方法是重写代码以使用池分配器。池分配器是一种管理单一固定大小对象并一次性为多个对象分配空间的分配器，而不是使用单独的分配。幸运的是，C++直接支持这一点。池分配器定义在 std 命名空间的 pmr (“多态内存资源”)子命名空间中：

pmr::synchronized_pool_resource pool; // 创建一个内存池

struct Event {
    vector<int> data = vector<int>{512, &pool}; // 让Event使用池分配内存
}; 

list<shared_ptr<Event>> q {&pool}; // 让队列q使用池分配内存

void producer() {
    for (int n = 0; n != LOTS; ++n) {
        scoped_lock lk {m}; // m是一个互斥锁
        q.push_back(allocate_shared<Event, pmr::polymorphic_allocator<Event>>{&pool}); 
        cv.notify_one();
    }
}

现在，在同样的条件下，消耗的内存不到3MB。这是一个大约2000倍的改进！当然，实际使用的内存量（而非因碎片化浪费的内存）是不变的。消除碎片化后，内存使用量随时间稳定，系统可以连续运行数月。

像这样的技术自C++早期就被应用，并取得了良好效果，但通常需要重写代码以使用特殊化的容器。现在，标准容器可选择性地接受分配器参数，默认情况下容器使用 new 和 delete 。其他多态内存资源包括：

unsynchronized_polymorphic_resource ; 类似于 polymorphic_resource ，但只能被单个线程使用。
monotonic_polymorphic_resource ; 一个快速分配器，仅在其销毁时释放内存，并且也只能被单个线程使用。

多态资源必须从 memory_resource 派生并定义成员函数 allocate() 、 deallocate() 和 is_equal() 。目的是让用户构建自己的资源以调整代码性能。

12.8 容器概述

标准库提供了一些最通用和实用的容器类型，使程序员能够选择最适合应用程序需求的容器。这些容器主要包括：


vector<T>	可变大小的数组（§12.2）
list<T>	双向链表（§12.3）
forward_list<T>	单向链表
deque<T>	双端队列
map<K,V>	关联数组（§12.5）
multimap<K,V>	一个键可以出现多次的map
unordered_map<K,V>	使用哈希查找的map（§12.6）
unordered_multimap<K,V>	使用哈希查找的multimap
set<T>	集合（仅含键，无值）
multiset<T>	值可以出现多次的集合
unordered_set<T>	使用哈希查找的集合
unordered_multiset<T>	使用哈希查找的多重集合

无序容器针对使用键（通常是字符串）查找进行了优化；换句话说，它们是哈希表。

这些容器在 std 命名空间中定义，并在 <vector> 、 <list> 、 <map> 等头文件中介绍（§9.3.4）。此外，标准库还提供了容器适配器 queue<T> 、 stack<T> 和 priority_queue<T> 。如果你需要，可以查阅它们。标准库还提供了更专业化的类容器类型，比如 array<T,N> （§15.3.1）和 bitset<N> （§15.3.2）。

标准容器及其基本操作从符号表示的角度设计得十分相似。此外，这些操作对于各种容器的含义是等价的。基本操作适用于每种合乎逻辑且能高效实现的容器类型：


value_type	元素的类型
p=c.begin()	p 指向 c 的第一个元素；对于 const 迭代器可使用 cbegin()
p=c.end()	p 指向 c 的最后一个元素之后的位置；对于 const 迭代器可使用 cend()
k=c.size()	k 是 c 中元素的数量
c.empty()	c 是否为空？
k=c.capacity()	k 是 c 在不重新分配内存的情况下能容纳的元素数量
c.reserve(k)	将容量增加到 k ；如果 k<=c.capacity() ， c.reserve(k) 不做任何操作
c.resize(k)	将元素数量调整为 k ；新增的元素具有默认值 value_type{}
c[k]	c 中的第 k 个元素；从零开始计数；不保证范围检查
c.at(k)	c 中的第 k 个元素；如果越界，抛出 out_of_range 异常
c.push_back(x)	在 c 的末尾添加 x ； c 的大小增加一
c.emplace_back(a)	在 c 的末尾构造一个值为 value_type{a} 的元素； c 的大小增加一
q=c.insert(p,x)	在 c 中 p 之前的位置添加 x
q=c.erase(p)	从 c 中删除 p 所指向的元素
c=c2	赋值：将 c2 的所有元素复制给 c ，使得 c==c2
b=(c==c2)	比较 c 和 c2 中所有元素是否相等；相等则 b 为 true
x=(c<=>c2)	c 和 c2 的字典序比较： x<0 表示 c < c2 ， x==0 表示两者相等， 0<x 表示 c > c2 ； != , < , <= , > , 和 >= 操作符由 <=> 生成

这种符号表示和语义上的一致性使得程序员能够提供新的容器类型，这些新类型可以非常类似地用于标准容器。范围检查 vector （§4.3，第5章）就是这样一个例子。容器接口的一致性让我们能够在不依赖于个别容器类型的情况下指定算法。然而，每种容器都有其优势和劣势。例如， vector 的下标访问和遍历成本低廉且简单。另一方面，当我们插入或删除元素时， vector 中的元素会被移动到不同的位置；而链表则具有完全相反的特性。请注意，对于短序列的小元素而言， vector 通常比链表更有效率（即使是对于 insert() 和 erase() 操作）。我推荐使用标准库中的 vector 作为元素序列的默认类型：选择其他类型需要有充分的理由。

考虑单向链表, forward_list ，它是一种针对空序列优化的容器（§12.3）。一个空的 forward_list 仅占用一个字节，而一个空的 vector 则占用三个字节。空序列以及只包含一两个元素的序列出奇地常见且有用。

emplace 操作，如 emplace_back() ，会接受元素构造函数的参数，并在容器的新分配空间中构建对象，而不是将对象复制到容器中。例如，对于一个 vector<pair<int,string>> ，我们可以这样写：

v.push_back(pair{1,"copy or move"}); // 创建一个pair并将其移动到v中
v.emplace_back(1,"build in place");  // 直接在v中构建一个pair

对于像这样的简单示例，优化可能会导致两个调用的性能相当。

12.9 建议

STL容器定义了一个序列；§12.2。
STL容器是资源句柄；§12.2, §12.3, §12.5, §12.6。
将 vector 作为默认容器使用；§12.2, §12.8；[CG: SL.con.2]。
对容器进行简单遍历时，使用范围 for 循环或 begin/end 迭代器对；§12.2, §12.3。
使用 reserve() 来避免使指向元素的指针和迭代器失效；§12.2。
未经测量，不要假设 reserve() 带来的性能提升；§12.2。
在容器上使用 push_back() 或 resize() ，而不是在数组上使用 realloc() ；§12.2。
避免使用已调整大小的 vector 中的迭代器；§12.2 [CG: ES.65]。
不要假设 [ ] 进行范围检查；§12.2。
需要保证范围检查时，使用 at() ；§12.2；[CG: SL.con.3]。
利用范围 for 循环和标准库算法免费避免范围错误；§12.2.2。
元素被复制到容器中；§12.2.1。
为了保持元素的多态行为，存储指针（内置或用户定义）；§12.2.1。
在 vector 上，插入操作（如 insert() 和 push_back() ）通常效率惊人；§12.3。
当序列通常为空时，使用 forward_list ；§12.8。
关于性能，不要相信直觉：进行测量；§12.2。
map 通常实现为红黑树；§12.5。
unordered_map 是哈希表；§12.6。
通过引用传递容器，按值返回容器；§12.2。
对于容器，使用 () 初始化语法指定大小，使用 {} 初始化语法指定元素序列；§5.2.3, §12.2。
偏好紧凑且连续的数据结构；§12.3。
list 遍历相对昂贵；§12.3。
如果需要大量数据的快速查找，使用无序容器；§12.6。
如果需要按顺序迭代容器元素，使用有序容器（如 map 和 set ）；§12.5。
对于没有自然顺序（即，没有合理的 < ）的元素类型，使用无序容器（如 unordered_map ）；§12.5。
当需要元素指向在容器大小变化时保持稳定时，使用关联容器（如 map 和 list ）；§12.8。
实验验证哈希函数是否可接受；§12.6。
通过异或运算符( ˆ )组合元素的标准哈希函数获得的哈希函数通常是个好主意；§12.6。
熟悉标准库容器，并优先于手工制作的数据结构；§12.8。
如果应用程序遇到与内存相关的性能问题，最小化自由存储区的使用，或考虑使用专门的分配器；§12.7。

第12章 容器

第12章容器