3.md

三、容器

C++ 标准库提供了一系列不同的数据结构，称为容器，可以用来存储数据。容器与算法协同工作，如第 4 章所述。容器和算法是以这样一种方式设计的，它们不需要相互了解。它们之间的交互是通过迭代器完成的。所有容器都提供迭代器，算法只需要迭代器就能执行工作。

本章首先解释迭代器的概念，然后描述所有容器。因为这本书是快速参考，所以不可能深入讨论所有的容器。与其他容器相比，std::vector容器的解释更加详细。一旦你知道如何使用一个容器，你就知道如何使用其他容器。

迭代程序

迭代器是容器和算法之间的粘合剂。它们提供了一种以统一的方式枚举容器中所有元素的方法，而不必知道容器的任何细节。下面的列表简要地提到了标准提供的最重要的迭代器类别，后面的表格解释了所有可能的操作:

• Forward (F):支持正向迭代的输入迭代器
• 双向(B):可以向前和向后移动的前向迭代器
• Random (R):一个双向迭代器，支持跳转到任意索引的元素

下表中，T是迭代器类型，a和b是T的实例，t是T指向的类型的实例，n是整数。

| 操作 | 描述 | F | B | 稀有 | | --- | --- | --- | --- | --- | | `T a`、`T()`、`T b(a)`、`b = a` | 默认构造函数，析构函数，复制构造函数，复制赋值。 | ■和 | ■和 | ■和 | | `a == b`，`a != b` | 等式和不等式运算符。 | ■和 | ■和 | ■和 | | `*a`、`a->m, *a = t`、`*a++ = t` | 取消引用。 | ■和 | ■和 | ■和 | | `++a`、`a++`、`*a++` | 递增运算符。 | ■和 | ■和 | ■和 | | `--a`、`a--`、`*a--` | 递减运算符。 | □ | ■和 | ■和 | | `a[n]` | 随机存取。 | □ | □ | ■和 | | `a + n`、`n + a`、`a - n`、`a += n`、`a -= n` | 算术运算符。向前或向后移动迭代器。 | □ | □ | ■和 | | `a - b` | 计算迭代器之间的距离。 | □ | □ | ■和 | | `a < b`、`a > b`、`a <= b`、`a >= b` | 不等式运算符。 | □ | □ | ■和 |

由此可见，随机迭代器和 C++ 指针非常相似。事实上，指向常规 C 风格数组的指针满足了随机迭代器的所有要求，因此也可以用于第 4 章中的算法。同样，某些容器，尤其是顺序容器，可能将它们的迭代器定义为常规指针的typedef。然而，对于更复杂的数据结构，这是不可能的，迭代器是作为小类实现的。

所有标准库兼容容器必须提供一个iterator和const_iterator成员类型。此外，支持反向迭代的容器必须提供reverse_iterator和const_reverse_iterator成员类型。例如，整数的vector的反向迭代器类型是std::vector<int>::reverse_iterator。

迭代器标签

迭代器标签是一种空类型，用于区分前面提到的不同迭代器类别。该标准为以下类别值定义了std::类别_iterator_tag类型:forward、bidirectional、random_access。类型特征表达式std::iterator_traits<Iter>::iterator_category计算给定迭代器类型Iter的迭代器标签类型。这可以被通用算法用来根据迭代器参数的类别优化它们的实现。例如，在下一节中解释的std::distance()方法使用迭代器标签在线性计算两个迭代器之间距离的实现和简单减去两个迭代器的更有效的实现之间进行选择。

如果你实现了你自己的迭代器，你应该指定它的标签。你可以通过添加一个typedef Tag iterator_category到你的实现中，其中Tag是迭代器标签之一，或者通过为你的类型专门化std::iterator_traits来提供正确的标签类型。

获取迭代器的非成员函数

所有容器都支持返回各种迭代器的成员函数。然而，该标准还提供了非成员函数，可用于获得这种迭代器。此外，这些非成员函数在容器、C 风格数组和initializer_lists上的工作方式是一样的。提供的非成员函数如下:

| 非成员函数 | 描述 | | --- | --- | | `begin()` / `end()` | 返回第一个元素的迭代器，或者最后一个元素之后的迭代器 | | `cbegin()` / `cend()` | `begin()`和`end()`的`const`版本 | | `rbegin()` / `rend()` | 分别返回到最后一个或第一个元素之前的一个反向迭代器 | | `crbegin()` / `crend()` | `const`版本或者`rbegin()`和`rend()` |

解引用由const版本返回的迭代器，也称为常量迭代器，会导致const引用，因此不能用于修改容器或数组中的元素。反向迭代器允许以相反的顺序遍历容器的元素:从最后一个元素开始，到第一个元素。当你增加一个反向迭代器时，它实际上会移动到底层容器中的前一个元素。

下面是一个如何在 C 风格数组中使用这种非成员函数的示例:

int myArray[] = { 1,2,3,4 };
auto beginIter = std::cbegin(myArray);
auto endIter = std::cend(myArray);
for (auto iter = beginIter; iter != endIter; ++iter) {
   std::cout << *iter << std::endl;
}

然而，我们建议您使用基于范围的for循环来遍历 C 风格数组或标准库容器的所有元素。它更短、更清晰。例如:

int myArray[] = { 1,2,3,4 };
for (const auto& element : myArray) {
   std::cout << element << std::endl;
}

但是，您不能总是使用基于范围的for循环版本。例如，如果您想循环遍历元素并删除其中一些元素，那么您需要迭代器版本。

迭代器上的非成员操作

以下非成员操作用于对所有类型的迭代器执行随机访问操作。当在不支持随机访问的迭代器上调用时(也参见前面的内容)，实现会自动退回到适用于该迭代器的方法(例如，线性遍历):

• std::distance(iter1, iter2):返回两个迭代器之间的距离。
• std::advance(iter, dist):将迭代器向前移动给定的距离，不返回任何内容。如果迭代器是双向的或随机访问的，距离可以是负的。
• std::next(iter, dist):相当于advance(iter, dist)，返回iter。
• std::prev(iter, dist):相当于advance(iter, -dist)，返回iter。仅适用于双向和随机访问迭代器。

顺序容器

以下部分描述了五个连续的容器:vector、deque、array、list和forward_list。最后是这些容器支持的所有可用方法的参考。

标准::矢量<vector>

一个vector在内存中连续存储它的元素。它类似于堆分配的 C 风格数组，除了它更安全和更容易使用，因为vector自动释放它的内存并增长以容纳新元素。

建筑

像所有标准的库容器一样，vector是基于存储在其中的对象类型的模板。下面这段代码显示了如何定义整数的vector:

std::vector<int> myVector;

可以使用有支撑的初始化器来指定初始元素:

std::vector<int> myVector1 = { 1,2,3,4 };
std::vector<int> myVector2{ 1,2,3,4 };

也可以构造一个有一定大小的vector。例如:

std::vector<int> myVector(100, 12);

这将创建包含值为12的100元素的myVector。第二个参数是可选的。如果你省略它，新元素被零初始化，这是整数情况下的0。

迭代程序

支持随机访问迭代器。使用begin()或cbegin()成员获得一个非const或const迭代器，指向vector中的第一个元素。end()和cend()方法用于获取一个迭代器，使其超过最后一个元素。rbegin()和crbegin()返回一个反向迭代器到最后一个元素，rend()和crend()返回一个反向迭代器到第一个元素之前。

和往常一样，也可以使用前面解释过的等价非成员函数，比如std::begin()、std::cbegin()等等。

访问元素

可以使用operator[]访问vector中的元素，它返回对特定的从零开始的索引处的元素的引用，使其行为与 C 风格的数组完全一样。例如:

使用operator[]时不执行边界检查。如果需要边界检查，使用at()方法，如果给定的索引超出边界，该方法会抛出std::out_of_range异常。

front()可以用来获取对第一个元素的引用，back()返回对最后一个元素的引用。

添加元素

向vector添加元素的一种方法是使用push_back()。例如，将两个整数加到myVector上可以如下完成:

std::vector<int> myVector;
myVector.push_back(11);
myVector.push_back(2);

另一种选择是使用insert()方法，这需要一个迭代器来定位应该插入新元素的位置。例如:

就像任何修改操作一样，插入通常会使现有的迭代器失效。所以在循环中插入时，应该使用下面的习惯用法:

这是可行的，因为insert()返回一个指向插入元素的有效迭代器(更一般地，指向第一个插入元素，稍后讨论)。如果使用循环，确保不缓存结束迭代器，因为insert()可能会使它无效。

insert()也可以用来在vector的任何地方插入一系列元素，或者连接(附加)两个向量。使用insert()时，您不必自己调整vector的大小。例如:

insert()的两个额外的重载提供了初始化列表的插入或者某个元素的给定数量的副本。使用与之前相同的v1:

除了构造一个新元素然后将其传递给insert()或push_back()之外，元素也可以使用就位方法就地构造，例如emplace()或emplace_back()。前者emplace()，是单元素insert()的对应，后者push_back()。假设你有一个vector的Person对象。你可以用这两种相似的方法在后面添加一个新的人:

persons.push_back(Person("Sheldon", "Cooper"));
persons.emplace_back("Leonard", "Hofstadter");

定位函数的参数被完美地转发给元素的构造函数。如前例所示，如果避免产生临时物体，安放通常会更有效。如果复制的代价很高，或者如果不能复制的话，这可能是添加元素的唯一方式，那么这就特别有趣了。

另外，容器的添加和插入成员通常完全支持将元素移动到容器中，这也是为了避免创建不必要的副本(移动语义在第 2 章中解释)。例如:

Person person("Howard", "Wolowitz");
persons.push_back(std::move(person));

尺寸和容量

一个vector有一个大小，由size()返回，是vector中包含的元素个数。使用empty()检查vector是否为空。但是，注意不要混淆empty()和clear():前者返回一个布尔值，后者删除所有元素。

一个vector可以用resize()调整大小。例如:

std::vector<int> myVector;
myVector.resize(100, 12);

这将vector的大小设置为 100 个元素。如果必须创建新元素，它们用 12 初始化。第二个参数也是可选的；省略时，新元素从零开始初始化。

一个vector除了大小，还有一个容量，由capacity()返回。容量是它可以存储的元素总数(包括已经在vector中的元素)，而不必分配更多的内存。如果添加的元素比容量允许的多，vector必须执行重新分配，因为它需要在内存中连续存储所有元素。重新分配意味着分配一个新的、更大的内存块，并且vector中的所有当前元素都被转移到新的位置(如果支持移动并且知道不要抛出，则它们被移动；否则它们被复制；参见第 2 章。

如果您知道要添加多少元素，那么预先分配足够的容量以避免重新分配对性能至关重要。如果不这样做，将会导致严重的性能下降。这可以通过使用reserve()来完成:

myVector.reserve(100);

注意，这没有为 100 个额外的元素预留容量；它只是确保myVector的总容量至少为 100。为非空的vector预留容量以存储 100 个额外的元素应该按如下方式进行:

myVector.reserve(myVector.size() + 100);

移除元素

使用pop_back()可以删除vector中的最后一个元素，使用erase()可以删除其他元素。erase()有两种过载:

• erase(iter):删除给定迭代器指向的元素
• erase(first, last):删除两个迭代器给出的元素范围，所以[ first，last]

当您删除元素时，vector的大小会改变，但其容量不会改变。如果想回收未使用的内存，可以使用shrink_to_fit()。不过，这只是一个提示，实现可能会忽略它:例如，出于性能原因。

要删除所有元素，使用clear()。这同样不会影响容量。在保证回收内存的同时清空容器的一个经典习惯用法是与空容器交换:

先前空的容器随后被销毁，其中包含所有元素，剩下原来的容器为空。这个成语也经常被更简短地写成如下:

删除-擦除习惯用法

如果您需要从一个vector中删除一些元素，您可以编写自己的循环来迭代所有的元素。下面的示例从 vector 中删除所有等于 2 的元素:

如果你使用了这里显示的循环，确保你没有缓存结束迭代器，因为erase()会使它无效。为了避免这样或那样的错误，我们总是建议您使用标准算法，而不是手写的循环。当您想要删除多个元素时，您可以使用删除-擦除习惯用法。这种模式首先使用std::remove()或std::remove_if()算法。正如第 4 章所解释的，这些算法实际上并不删除元素。相反，它们将所有需要保留的元素移至开头，保持这些元素的相对顺序。该算法返回一个迭代器，使其超过最后一个要保留的元素。下一步通常是调用容器上的erase()来真正删除从remove()或remove_if()返回的迭代器开始到结束的元素。例如:

对第二行中的remove()的调用将所有元素移向vector的开头。根据编译器的不同，其他元素(即要移除的元素)的内容可能会有所不同。

之前的remove()和erase()通话也可以合并成一条线路:

vec.erase(std::remove(begin(vec), end(vec), 2), end(vec));

Caution

在 remove-erase 习惯用法中，不要忘记将结束迭代器指定为erase()的第二个参数，就像前面例子中用粗体标记的那样。否则只会删除一个元素！

标准::矢量

vector<bool>是vector<T>对布尔元素的特化。它允许 C++ 标准库实现以节省空间的方式存储布尔值，但这不是必需的。它与vector<T>有相同的接口，增加了一个flip()方法来翻转vector<bool>中的所有位。

这种专门化与后面讨论的std::bitset相似。区别在于bitset的大小是固定的，而vector<bool>可以根据需要动态增减。

建议使用vector<bool>和bitset只是为了节省内存；否则，使用vector<std::uint_fast8_t>:这通常在访问、遍历或赋值时有更好的性能。

复杂性

对vector的常见操作的复杂程度如下:

• 插入:末尾摊销常数 O(1)；否则从插入点到向量末尾的距离为线性，O(N)
• 删除:O(1)在末端，否则在到向量 O(N)末端的距离上是线性的
• 访问:O(1)

尽管后面讨论的list和forward_list在理论上有更好的插入和删除复杂度，但是vector在实践中通常更快，因此应该是默认的顺序容器。如果有疑问，请始终使用分析器来比较它们在您的应用程序中的性能。

STD::deque〔t0〕

一个deque是一个双端队列，一个类似于vector的容器，支持在开始和结束时的高效插入和删除。该标准不要求deque元素在内存中连续存储，因此由deque完成的重新分配可能比由vector完成的更便宜。然而，deque支持随机访问和随机访问迭代器。

deque上的操作与vector上的操作几乎相同，只有一些细微的差别。deque没有容量的概念，因为它不需要连续存储它的元素，所以与容量相关的方法都不可用。而且，deque除了push_back()和pop_back()之外，还提供了push_front()和pop_front()。

下面是一个使用deque的例子:

复杂性

对deque的常见操作的复杂程度如下:

• 插入:期初和期末的摊余常数 O(1)；否则从插入点到起点或终点 O(N)的距离是线性的
• 删除:O(1)在开头或结尾；否则在到 O(N)的开始或结束的距离上是线性的
• 访问:O(1)

标准::数组<array>

一个array是一个具有固定大小的容器，在编译时被指定为模板参数，支持随机访问迭代器。对于一个array，size()和max_size()返回相同的结果。

下面定义了一个由三个整数组成的数组:

std::array<int, 3> myArray;

这些整数没有初始化。这与所有其他容器不同，默认情况下，这些容器对其元素进行零初始化。这是因为std::array被设计成尽可能接近 C 数组。当然，你也可以在定义一个array的时候初始化元素。初始化值的数量必须等于或小于array的大小。如果指定更多的值，会出现编译错误。没有指定值的元素被初始化为零。例如:

这也意味着下面的零初始化所有元素:

有一个特殊的方法，fill()，用某个值填充array。例如:

对于数组，这可能比第 4 章中解释的通用std::fill()算法更有效。

复杂性

• 插入:不可能
• 删除:不可能
• 访问:O(1)

std::list 和 std::forward_list ，<forward_list></forward_list>

A list将其元素存储为双向链表，而 a forward_list将其存储为单向链表。因此，两者都在内存中不连续地存储元素。

第一个缺点是随机访问因此在恒定时间内是不可能的。正因为如此，不支持operator[]。要访问一个特定的元素，你必须使用迭代器执行线性搜索。list支持双向迭代器，可以从开头开始，也可以从结尾开始；forward_list只支持正向迭代器，所以你总是需要从头开始。但是，一旦您在容器中的正确位置，在该位置的插入和删除是有效的，因为它们只需要修改几个链接。

第二个缺点是，元素可能会分散在内存中，这不利于局部性，并且会由于缓存未命中次数的增加而影响性能。

Tip

由于前面提到的缺点，如果剖析器显示对于您的用例来说使用list或forward_list比使用vector更有效，那么只使用list或forward_list。

list和forward_list支持的操作与vector类似，略有不同。list或forward_list没有容量，因此不支持任何与容量相关的方法。两者都支持front()，返回对第一个元素的引用。一个list也支持back()返回对最后一个元素的引用。

复杂性

list和forward_list都有相似的复杂性:

• 插入:O(1)一旦你在正确的位置
• 删除:O(1)一旦你在正确的位置
• Access: O(1)访问第一个(对于list和forward_list)或最后一个(仅对于list)元素；否则为 O(N)

列表特定算法

由于list和forward_list存储元素的方式，它们提供了几个实现特定算法的成员函数。下表列出了为list (L)和forward_list (F)提供的算法:

| 操作 | L | F | 描述 | | --- | --- | --- | --- | | `merge()` | ■和 | ■和 | 合并两个排序列表。合并的列表将被清空。 | | `remove()` | ■和 | ■和 | 从列表中移除与给定值匹配的元素。 | | `remove_if()` | ■和 | ■和 | 从列表中移除满足给定谓词的元素。 | | `reverse()` | ■和 | ■和 | 反转列表的内容。 | | `sort()` | ■和 | ■和 | 对元素进行排序。 | | `splice()` | ■和 | □ | 将另一个列表中的元素移动到给定位置之前。 | | `splice_after()` | □ | ■和 | 将另一个列表中的元素移动到给定位置之后。 | | `unique()` | ■和 | ■和 | 用单个元素替换连续的重复项。 |

对于除splice()和splice_after()之外的所有算法，通用版本均可用，详见第 4 章。这些通用版本适用于所有类型的容器，但是列表容器提供了更有效的特殊实现。

下面是使用这些列表算法的一个例子:

顺序容器参考

以下各小节对vector(V)deque(D)array(A)list(L)forward_list(F)支持的所有操作进行了分类概述。

迭代程序

| 操作 | V | D | A | L | F | 描述 | | --- | --- | --- | --- | --- | --- | --- | | `begin()` `end()` | ■和 | ■和 | ■和 | ■和 | ■和 | 返回第一个元素或最后一个元素之后的迭代器 | | `cbegin()` `cend()` | ■和 | ■和 | ■和 | ■和 | ■和 | `begin()`和`end()`的`const`版本 | | `rbegin()` `rend()` | ■和 | ■和 | ■和 | ■和 | □ | 返回最后一个元素或第一个元素之前的一个元素的反向迭代器 | | `crbegin()` `crend()` | ■和 | ■和 | ■和 | ■和 | □ | `rbegin()`和`rend()`的`const`版本 | | `before_begin()` | □ | □ | □ | □ | ■和 | 将迭代器返回到由`begin()`返回的元素之前的元素 | | `cbefore_begin()` | □ | □ | □ | □ | ■和 | `before_begin()`的`const`版本 |

尺寸和容量

| 操作 | V | D | A | L | F | 描述 | | --- | --- | --- | --- | --- | --- | --- | | `size()` | ■和 | ■和 | ■和 | ■和 | □ | 返回元素的数量 | | `max_size()` | ■和 | ■和 | ■和 | ■和 | ■和 | 返回容器中可以存储的最大元素数量 | | `resize()` | ■和 | ■和 | □ | ■和 | ■和 | 调整容器的大小 | | `empty()` | ■和 | ■和 | ■和 | ■和 | ■和 | 如果容器是空的，返回`true`，否则返回`false` | | `capacity()` | ■和 | □ | □ | □ | □ | 返回容器的当前容量 | | `reserve()` | ■和 | □ | □ | □ | □ | 储备能力 | | `shrink_to_fit()` | ■和 | ■和 | □ | □ | □ | 提示减少容器的容量以匹配其大小 |

接近

| 操作 | V | D | A | L | F | 描述 | | --- | --- | --- | --- | --- | --- | --- | | `operator[]` | ■和 | ■和 | ■和 | □ | □ | 返回给定索引位置的元素的引用。不对索引执行边界检查。 | | `at()` | ■和 | ■和 | ■和 | □ | □ | 返回给定索引位置的元素的引用。如果给定的索引位置超出界限，就会抛出一个`std::out_of_range`异常。 | | `data()` | ■和 | □ | ■和 | □ | □ | 返回一个指向`vector`或`array`数据的指针。这有助于将数据传递给传统的 C 风格数组 API。在旧代码中，你经常会看到等价的`&myContainer[0]`。 | | `front()` | ■和 | ■和 | ■和 | ■和 | ■和 | 返回对第一个元素的引用。空容器上未定义的行为。 | | `back()` | ■和 | ■和 | ■和 | ■和 | □ | 返回对最后一个元素的引用。空容器上未定义的行为。 |

修饰语

| 操作 | V | D | A | L | F | 描述 | | --- | --- | --- | --- | --- | --- | --- | | `assign()` | ■和 | ■和 | ■和 | ■和 | ■和 | 用给定值的 N 个副本，或给定范围的元素的副本，或给定`initializer_list`的元素替换容器的内容 | | `clear()` | ■和 | ■和 | □ | ■和 | ■和 | 删除所有元素；大小变为零。 | | `emplace()` | ■和 | ■和 | □ | ■和 | □ | 在给定迭代器指向的元素之前的位置构造一个新元素。迭代器参数后面是零个或多个参数，这些参数将被转发给元素的构造函数。 | | `emplace_back()` | ■和 | ■和 | □ | ■和 | □ | 在末尾的适当位置构造一个新元素。 | | `emplace_after()` | □ | □ | □ | □ | ■和 | 在现有元素之后就地构造一个新元素。 | | `emplace_front()` | □ | ■和 | □ | ■和 | ■和 | 在开始的地方构造一个新元素。 | | `erase()` | ■和 | ■和 | □ | ■和 | □ | 擦除元素。 | | `erase_after()` | □ | □ | □ | □ | ■和 | 删除现有迭代器位置后的元素。 | | `fill()` | □ | □ | ■和 | □ | □ | 用给定元素填充容器。 | | `insert()` | ■和 | ■和 | □ | ■和 | □ | 在给定迭代器指向的元素前插入一个或多个元素。 | | `insert_after()` | □ | □ | □ | □ | ■和 | 在给定迭代器指向的元素后插入一个或多个元素。 | | `push_back()` `pop_back()` | ■和 | ■和 | □ | ■和 | □ | 在末尾添加一个元素，或者分别移除最后一个元素。 | | `push_front()` `pop_front()` | □ | ■和 | □ | ■和 | ■和 | 在开头添加一个元素，或者移除第一个元素。 | | `swap()` | ■和 | ■和 | ■和 | ■和 | ■和 | 在常数时间内交换两个容器的内容，除了`array` s，它需要线性时间。 |

非成员函数

所有顺序容器都支持以下非成员函数:

| 操作 | 描述 | | --- | --- | | `==`、`!=`、`<`、`<=`、`>`、`>=` | 比较两个容器中的值(按字典顺序) | | `std::swap()` | 交换两个容器的内容 |

<array>头定义了一个额外的非成员函数std::get<Index>()，以及助手类型std::tuple_size和std::tuple_element，它们等同于在第 2 章中解释的为元组和对定义的相同函数和类型。

std::bitset <bitset>

bitset是存储固定位数的容器。位数被指定为模板参数。例如，以下代码创建了一个 10 位的bitset,全部初始化为 0:

std::bitset<10> myBitset;

可以通过向构造函数传递一个整数或者传入位的字符串表示来初始化各个位的值。例如:

std::bitset<4> myBitset("1001");

一个bitset可以用to_ulong()、to_ullong()和to_string()转换成整数或字符串。

复杂性

• 插入:不可能
• 删除:不可能
• 访问:O(1)

参考

接近

| 操作 | 描述 | | --- | --- | | `all()``any()`T2】 | 如果所有位、至少一个位或没有位被置位，则返回`true`。 | | `count()` | 返回设置的位数。 | | `operator[]` | 访问给定索引处的位。不执行边界检查。 | | `test()` | 访问给定索引处的位。如果给定的索引超出界限，抛出`std::out_of_range`。 | | `==, !=` | 如果两个`bitset`相等或不相等，则返回`true`。 | | `size()` | 返回位集可以容纳的位数。 | | `to_string()``to_ulong()`T2】 | 将一个`bitset`分别转换为一个`string`、`unsigned long`或`unsigned long long`。 |

操作

| 操作 | 描述 | | --- | --- | | `flip()` | 翻转所有位的值 | | `reset()` | 将所有位或特定位置的位设置为`false` | | `set()` | 将所有位设置为`true`或将特定位置的位设置为特定值 |

另外，bitset支持所有的按位运算符:∼、&、&=、^、^=、|、|=、<<、<<=、>>、>>=。

容器适配器

容器适配器构建在其他容器之上，以提供不同的接口。它们阻止您直接访问底层容器，并强迫您使用它们的特殊接口。接下来的三个小节给出了可用容器适配器的概述— queue、priority_queue和stack—后面的一个小节给出了一个例子和一个参考小节。

STD::queue<queue>

一个queue表示一个具有先进先出(FIFO)语义的容器。你可以把它比作夜总会的排队。在你之前到达的人将被允许在你之前进入。

一个queue需要访问前端和后端，所以底层容器必须支持back()、front()、push_back()和pop_front()。标准的list和deque支持这些方法，可以用作底层容器。默认的容器是deque。下面是queue的模板定义:

template<class T, class Container = std::deque<T>>
class queue;

queue的复杂度如下:

• 插入:list的 O(1)作为底层容器；deque的摊销 O(1)
• 删除:list和deque的 O(1)作为底层容器
• 进入:不可能

标准::优先级 _ 队列<queue>

一个priority_queue类似于一个queue，但是根据优先级存储元素。优先级最高的元素位于队列的最前面。在夜总会的情况下，贵宾会员获得更高的优先权，并被允许在非贵宾之前进入。

A priority_queue需要对底层容器进行随机访问，并且只需要能够在后面修改容器，而不是在前面。因此，底层容器必须支持随机访问、front()、push_back()和pop_back()。vector和deque是可用选项，vector是默认的底层容器。下面是priority_queue的模板定义:

template<class T,
   class Container = std::vector<T>,
   class Compare = std::less<typename Container::value_type>>
class priority_queue;

为了确定优先级，使用被指定为Compare模板类型参数的类型的仿函数对象来比较元素。默认情况下，这是std::less，在第 2 章中有解释，除非特别说明，否则它会转发到元素类型T的operator<。一个Compare实例可以选择性地提供给priority_queue构造函数；如果没有，则默认构造一个。

priority_queue的复杂度如下:

• 插入:作为底层容器的vector或deque的摊销 O(log(N))
• 删除:vector和deque作为底层容器的 O(log(N))
• 进入:不可能

标准::堆栈<stack>

一个stack表示一个具有后进先出(LIFO)语义的容器。你可以把它比作自助餐厅里的一堆盘子。在顶部添加板块，向下推动其他板块。顾客从顶部拿走一个盘子，这是堆叠中最后添加的盘子。

为了实现 LIFO 语义，stack要求底层容器支持back()、push_back()和pop_back()。vector、deque和list是底层容器的可用选项，deque是默认选项。下面是stack的模板定义:

template<class T, class Container = std::deque<T>>
class stack;

stack的复杂度如下:

• 插入:list的 O(1)作为底层容器，vector和deque的摊销 O(1)
• 删除:list、vector和deque作为底层容器的 O(1)
• 进入:不可能

例子

以下示例演示了如何使用容器适配器。代码后的表格显示了当容器cont分别被定义为queue、priority_queue或stack时程序的输出:

| `queue` | `priority_queue` | `stack` | | --- | --- | --- | | 道格 b 菲尔 w 斯图 p 艾伦 g | stu p[](#Fn1)Doug b Phil w Alan g | 艾伦·g·斯图·p·菲尔·w·道格·b |

参考

| 操作 | 描述 | | --- | --- | | `emplace()` | Queue:在后面的地方构造一个新元素。优先级队列:就地构造一个新元素。Stack:在顶部构建一个新元素。 | | `empty()` | 如果为空，则返回`true`，否则返回`false`。 | | `front()` `back()` | Queue:返回对第一个或最后一个元素的引用。优先级队列:不适用堆栈:不适用 | | `pop()` | Queue:从队列中移除第一个元素。优先级队列:删除优先级最高的元素。Stack:移除顶部元素。 | | `push()` | Queue:在队列后面插入一个新元素。优先级队列:插入新元素。Stack:在顶部插入新元素。 | | `size()` | 返回元素的数量。 | | `swap()` | 交换两个队列或堆栈的内容。 | | `top()` | Queue: n/a Priority queue:返回对具有最高优先级的元素的引用。Stack:返回对顶部元素的引用。 |

queue和stack支持与顺序容器相同的一组非成员函数:==、!=、<、<=、>、>=、std::swap(). priority_queue只支持std::swap()非成员函数。

有序关联容器

标准::地图和标准::多重地图<map>

一个map是存储键值pair的数据结构，使用在第 2 章中解释的pair实用程序类。元素根据键进行排序。也就是说，当遍历一个有序关联容器中包含的所有元素时，它们是按照键值递增的顺序被枚举的，而不是按照这些元素被插入的顺序。对于一个map，不能有重复的键，而一个multimap支持重复的键。

当定义一个map时，您需要指定键类型和值类型。你可以立即用一个支撑初始化器初始化一个map:

std::map<Person, int> myMap{ {Person("Jenne"), 1}, {Person("Bart"), 2} };

一个map<Key,Value>或multimap<Key,Value>的迭代器是双向的，指向一个pair<Key,Value>。例如:

operator[]可以用来访问map中的元素。如果请求的元素不存在，它是默认构造的，因此它也可用于插入元素:

myMap[Person("Peter")] = 3;

您可以使用insert()向map添加更多元素:

myMap.insert(std::make_pair(Person("Marc"), 4));

insert()方法有几种版本:

• 插入给定的键值pair。返回一个pair,迭代器指向插入的元素(一个键-值对)或者已经存在的元素，如果插入了新元素，返回一个布尔值true,否则返回false。

std::pair<iterator, bool> insert(pair)

• 插入给定的键值对。实现可以使用给定的提示来开始搜索插入位置。返回一个迭代器，指向插入的元素或阻止插入的元素。

iterator insert(iterHint, pair)

• 插入范围[ iterFirst，iterLast]中的键值对。

void insert(iterFirst, iterLast)

• 从给定的initializer_list插入键值对。

void insert(initializerList)

还有一个emplace()方法，允许您就地构造一个新的键值对。它返回一个类似于前面列表中第一个insert()方法的pair<iterator, bool>。例如:

myMap.emplace(Person("Anna"), 4);

然而，为了避免创建所有的临时对象，你必须使用所谓的分段构造，正如在第 2 一章的pair一节中所解释的:

myMap.emplace(std::piecewise_construct,
              std::forward_as_tuple("Anna"), std::forward_as_tuple(4));

std::set 和 std::multiset <set>

一个set类似于一个map，但是它不存储对，只存储没有值的唯一键(这是标准对它的定义，我们也将这样定义:有些人可能更愿意认为它是没有键的值)。一个multiset支持重复键。

只有一个模板类型参数:键类型。insert()方法采用单个键，而不是一个pair。例如:

insert()有类似于map和multimap的过载。

set或multiset的迭代器是双向的，指向实际的键，而不是像map和multimap那样指向pair。键总是排序的。

搜索

如果您想知道某个键是否在关联容器中，您可以使用这些:

• find():返回一个迭代器到找到的元素(映射的键值对)，如果没有找到给定的键，则返回结束迭代器。
• count():返回与给定键匹配的键的个数。对于map或set，只能是 0 或 1，而对于multimap或multiset，可以大于 1。

元素的顺序

有序关联容器以有序的方式存储它们的元素。默认情况下，std::less<Key>用于这种排序，除非特别指定，否则它依赖于Key类型的operator<。您可以通过指定一个Compare模板类型参数来更改比较仿函数类型。除非将一个具体的Compare仿函数实例传递给容器的构造函数，否则它是默认构造的。以下是所有有序关联容器的更完整的模板定义:

template<class Key, class Value, class Compare = std::less<Key>>
class map;
template<class Key, class Value, class Compare = std::less<Key>>
class multimap;

template<class Key, class Compare = std::less<Key>>
class set;
template<class Key, class Compare = std::less<Key>>
class multiset;

Tip

与有序关联容器一起使用的首选函子是所谓的透明运算符函子(参见第 2 章)，例如std::less<>(是std::less<void>的缩写)，因为这可以提高异构查找的性能。一个经典的例子是用字符串查找std::string键:std::less<>，然后避免创建临时的std::string对象。例如，带有string键和一个透明运算符的set声明如下:std::set<std::string, std::less<>> mySet;。

复杂性

所有四个有序关联容器的复杂性是相同的:

• 插入:O(log(N))
• 删除:O(log(N))
• 访问:O(log(N))

参考

以下小节按类别概述了map (M)、multimap (MM)、set (S)和multiset (MS)支持的所有操作。

迭代程序

所有有序关联容器都支持与vector容器相同的一组迭代器相关方法:begin()、end()、cbegin()、cend()、rbegin()、rend()、crbegin()和crend()。

大小

所有关联容器都支持以下方法:

| 操作 | 描述 | | --- | --- | | `empty()` | 如果容器是空的，返回`true`，否则返回`false` | | `max_size()` | 返回可以存储的最大元素数 | | `size()` | 返回元素的数量 |

访问和查找

| 操作 | M | 梅智节拍器 | S | 女士 | 描述 | | --- | --- | --- | --- | --- | --- | | `at()` | ■和 | □ | □ | □ | 返回具有给定键的元素的引用。如果给定的键不存在，抛出一个`std::out_of_range`异常。 | | `operator[]` | ■和 | □ | □ | □ | 返回具有给定键的元素的引用。如果一个元素还不存在，它默认用给定的键构造一个元素。 | | `count()` | ■和 | ■和 | ■和 | ■和 | 返回与给定键匹配的元素数量。 | | `find()` | ■和 | ■和 | ■和 | ■和 | 查找与给定键匹配的元素。 | | `lower_bound()` | ■和 | ■和 | ■和 | ■和 | 返回第一个元素的迭代器，该元素的键不小于给定的键。 | | `upper_bound()` | ■和 | ■和 | ■和 | ■和 | 返回第一个元素的迭代器，该元素的键大于给定的键。 | | `equal_range()` | ■和 | ■和 | ■和 | ■和 | 以一对迭代器的形式返回与给定键匹配的一系列元素。范围相当于调用`lower_bound()`和`upper_bound()`。对于`map`或`set`，该范围只能包含 0 或 1 个元素。 |

修饰语

所有关联容器都支持以下方法:

| 操作 | 描述 | | --- | --- | | `clear()` | 清空容器。 | | `emplace()` | 就地构造一个新元素。 | | `emplace_hint()` | 就地构造一个新元素。一个实现可以使用给定的提示来开始搜索插入位置。 | | `erase()` | 移除特定位置的元素、某个范围的元素或与给定键匹配的所有元素。 | | `insert()` | 插入新元素。 | | `swap()` | 交换两个容器的内容。 |

观察者

所有有序关联容器都支持以下观察器:

| 操作 | 描述 | | --- | --- | | `key_comp()` | 返回键比较仿函数 | | `value_comp()` | 返回用于根据键值对的键来比较键值对的函子 |

非成员函数

所有有序关联容器都支持与顺序容器相同的一组非成员函数:operator==、!=、<、<=、>、>=和std::swap()。

无序关联容器<unordered_map>，</unordered_map>

有四个无序关联容器:unordered_map、unordered_multimap、unordered_set和unordered_multiset。它们类似于有序关联容器(map、multimap、set和multiset)，只是它们不对元素进行排序，而是将它们存储在哈希映射的桶中。这些接口类似于相应的有序关联容器，只是它们公开了与哈希策略和桶相关的哈希特定的接口。

哈希映射

哈希映射或哈希表是一种高效的数据结构，它将其元素存储在桶中。 ² 从概念上讲，map 包含一个指向桶的指针数组，这些桶依次是元素的数组或链表。通过一个称为哈希的数学公式，计算出一个哈希整数，然后将其转换为桶索引。导致相同桶索引的两个元素存储在同一个桶中。

哈希映射允许非常快速地检索元素。要检索一个元素，需要计算它的哈希值，这会产生桶号。如果该存储桶中有多个元素，则在单个存储桶中执行快速(通常是线性)搜索，以找到正确的元素。

模板类型参数

无序关联容器允许您指定自己的哈希函数，以及自己的定义，即如何通过指定额外的模板类型参数来决定两个键是否相等。以下是所有无序关联容器的模板定义:

template<class Key, class Value, class Hash = std::hash<Key>,
   class KeyEqual = std::equal_to<Key>> class unordered_map;
template<class Key, class Value, class Hash = std::hash<Key>,
   class KeyEqual = std::equal_to<Key>> class unordered_multimap;

template<class Key, class Hash = std::hash<Key>,
   class KeyEqual = std::equal_to<Key>> class unordered_set;
template<class Key, class Hash = std::hash<Key>,
   class KeyEqual = std::equal_to<Key>> class unordered_multiset;

哈希函数

如果太多的键导致相同的哈希(桶索引)，哈希映射的性能会下降。在最坏的情况下，所有元素都在同一个桶中结束，所有查找和插入操作都变成线性的。编写合适的散列函数的细节超出了本书的范围。

该标准提供了以下std::hash模板(基础模板在<functional>中定义，但也包含在<unordered_xxx>标题中):

template<class T> struct hash;

提供了几种类型的专门化，如bool、char、int、long、double和std::string。如果你想计算你自己的对象类型的散列，你可以实现你自己的散列函子类。然而，我们建议您实现一个专门化的std::hash。

下面是一个例子，说明如何为简介一章中定义的Person类实现一个std::hash专门化。它对string对象使用标准的std::hash专门化来计算名和姓的散列。然后，通过 XOR 运算将两个哈希值组合起来。简单的异或值通常不会给出足够随机分布的整数，但是如果两个操作数都已经是散列，则可以认为是可接受的:

Note

尽管通常不允许向std名称空间添加类型或函数，但是添加专门化是完全合法的。还要注意，我们在第 2 章中提出的在类型自身的名称空间中专门化std::swap()的建议并没有扩展到std::hash:因为std::hash是一个类而不是一个函数(就像swap())，ADL 并不适用(参见第 2 章中的讨论)。

复杂性

所有四个无序关联容器的复杂性是相同的:

• 插入:平均 O(1)，最坏情况 O(N)
• 删除:平均 O(1)，最坏情况 O(N)
• 访问:平均 O(1)，最坏情况 O(N)

参考

所有无序关联容器都支持与有序关联容器相同的方法，除了反向迭代器、lower_bound()和upper_bound()。以下小节将对unordered_map (UM)、unordered_multimap (UMM)、unordered_set(美国)和unordered_multiset (UMS)支持的所有额外操作进行概述，分为几类。

观察者

所有无序关联容器都支持以下观察器:

| 操作 | 描述 | | --- | --- | | `hash_function()` | 返回用于哈希键的哈希函数 | | `key_eq()` | 返回用于对键执行相等测试的函数 |

桶接口

所有无序关联容器都支持以下桶接口:

| 操作 | 描述 | | --- | --- | | `begin(int)` `end(int)` | 返回给定索引的桶中第一个或最后一个元素的迭代器 | | `bucket()` | 返回给定键的桶的索引 | | `bucket_count()` | 返回桶的数量 | | `bucket_size()` | 返回桶中具有给定索引的元素数量 | | `cbegin(int)` `cend(int)` | `begin(int)`和`end(int)`的`const`版本 | | `max_bucket_count()` | 返回可以创建的最大存储桶数 |

哈希策略

所有无序关联容器都支持以下哈希策略方法:

| 操作 | 描述 | | --- | --- | | `load_factor()` | 返回存储桶中元素的平均数。 | | `max_load_factor()` | 返回或设置最大负载系数。如果负载系数超过此最大值，则会创建更多的存储桶。 | | `rehash()` | 将存储桶的数量设置为一个特定的值，并重新散列所有当前元素。 | | `reserve()` | 保留一定数量的存储桶以容纳给定数量的元素，而不超过最大负载系数。 |

非成员函数

所有无序关联容器只支持operator==、operator!=和std::swap()作为非成员函数。

分配器

除了array和bitset之外的所有容器都支持另一个我们还没有展示的模板类型参数——一个允许您指定分配器类型的参数。不过，这总是有一个默认值，您通常应该忽略它。当你想对容器的内存分配有更多的控制时，它就出现了。因此，理论上，您可以编写自己的分配器并将其传递给容器。这是一个超出本书范围的高级话题。

例如，vector模板的完整定义如下:

template<class T, class Allocator = allocator<T>>
class vector;

Footnotes 1

引言章节中为Person定义operator<的方式导致了priority_queue中的 VIP 和非 VIP 人员按相反的字母顺序排列:姓名按字母顺序排列的人拥有更高的优先级。

  2

从技术上讲，您可以很容易地实现没有桶的散列映射:例如，使用所谓的开放寻址。但是，标准无序容器的定义方式强烈建议使用单独的链接方法，这就是我们在这里描述的。