C++ STL CookBook 6：STL Containers （I）

目录

顺序容器

关联容器

容器适配器

使用统一擦除函数从容器中删除指定项

在恒定时间内对一个对排序不敏感的vector中删除项目

如果不确定自己访问容器会不会越界，那就使用.at方法而不是[]

---

在我们开始之前，先来回顾一下传统的经典的几个容器！

顺序容器

顺序容器提供了一个接口，其中元素按顺序排列。虽然您可以按顺序使用元素，但其中一些容器使用连续存储，而其他容器则不使用。STL 包括这些顺序容器：

• 数组是一个固定大小的序列，在连续存储中保存特定数量的元素。一旦分配，它就不能改变大小。这是最简单、最快的连续存储容器。

• 向量就像一个可以缩小和增大的数组。它的元素是连续存储的，因此更改大小可能涉及分配内存和移动数据的费用。向量可能会保留额外的空间以减轻这种成本。从向量后面以外的任何位置插入和删除元素将触发元素的重新对齐以保持连续存储。列表是一种双向链接列表结构，允许在常数（O(1)）时间内插入和删除元素。遍历列表的时间复杂度为线性 O(n)。

• 单链接变体可用作 forward_list，它仅向前迭代。forward_list 使用的空间较少，并且比双向链接列表更高效，但缺少一些功能。

• 双端队列（通常发音为 deck）是一种双端队列。它是一个可以在两端扩展或收缩的顺序容器。双端队列允许随机访问其元素，就像向量一样，但不保证连续存储。

关联容器

关联容器将一个键与每个元素关联。元素由其键引用，而不是其在容器中的位置。 STL 关联容器包括以下容器：

• 集合是一种关联容器，其中每个元素也是其自己的键。元素通常是按某种二叉树排序的。集合中的元素是不可变的，无法修改，但可以插入和删除。集合中的元素是唯一的，不允许重复。集合根据其排序运算符按顺序迭代。

• 多集类似于具有非唯一键的集合，其中允许重复。

• unordered_set 类似于不按顺序迭代的集合。元素不按任何特定顺序排序，而是根据其哈希值进行组织以便快速访问。

• unordered_multiset 类似于具有非唯一键的 unordered_set，其中允许重复。

• 映射是键值对的关联容器，其中每个键都映射到特定值（或有效负载）。键和值的类型可能不同。键是唯一的，但值不是。映射根据其排序运算符按其键的顺序进行迭代。 多映射类似于具有非唯一键的映射，其中允许重复的键。

• unordered_map 类似于不按顺序迭代的映射。

• unordered_multimap 类似于具有非唯一键的 unordered_map，其中允许重复。

容器适配器

容器适配器是封装底层容器的类。容器类提供一组特定的成员函数来访问底层容器元素。STL 提供以下容器适配器：

• 堆栈提供 LIFO（后进先出）接口，其中元素只能从容器的一端添加和提取。底层容器可以是向量、双端队列或列表之一。如果未指定底层容器，则默认为双端队列。

• 队列提供 FIFO（先进先出）接口，其中元素可以添加到容器的一端并从另一端提取。底层容器可以是双端队列或列表之一。如果未指定底层容器，则默认为双端队列。

• priority_queue 根据严格的弱排序将最大值元素保持在顶部。它提供对最大值元素的恒定时间查找，但插入和提取的时间对数为代价。底层容器可以是向量或双端队列之一。如果未指定底层容器，则默认为向量。

使用统一擦除函数从容器中删除指定项

在 C++20 之前，通常使用擦除-删除习语来有效地从 STL 容器中删除元素。这有点麻烦，但负担不大。通常使用这样的函数来完成任务：

template<typename Tc, typename Tv>
void remove_value(Tc & c, const Tv v) {auto remove_it = std::remove(c.begin(), c.end(), v);c.erase(remove_it, c.end());
}

嘿！实际上是这样的：

std::remove() 函数来自 <algorithms> 标头。std::remove()搜索指定的值并通过从容器末尾向前移动元素来删除它。它不会改变容器的大小。它返回一个超出移位范围末尾的迭代器。然后，我们调用容器的 erase() 函数来删除剩余元素。

现在，使用新的统一擦除函数，这个两步过程简化为一步：

std::erase(c, 5);    // 与 remove_value() 函数相同

这个函数调用与我们上面编写的 remove_value() 函数执行相同的操作。还有一个使用谓词函数的版本。例如，要从数字容器中删除所有偶数值：

std::erase_if(c, [](auto x) { return x % 2 == 0; });

当我们调用 remove(c.begin(), c.end(), 5) 时，算法会从 begin() 迭代器开始搜索匹配元素。对于找到的每个匹配元素，它会将下一个元素移到其位置。它会继续搜索和移动，直到到达 end() 迭代器。

结果是一个容器，其中所有剩余元素都在开头，没有被删除的元素，并且按其原始顺序排列。end() 迭代器保持不变，剩余元素未定义。我们可以像这样可视化操作：

如你所见，这就是remove_iterator的基本原理，那就是不停的拷贝元素覆盖。

在恒定时间内对一个对排序不敏感的vector中删除项目

使用统一擦除函数（或擦除-删除习语）从向量中间删除项目需要 O(n)（线性）时间。这是因为必须从向量末尾移动元素以填补已删除项目的间隙。

如果向量中项目的顺序不重要，我们可以优化此过程以花费 O(1)（常数）时间。方法如下。

template<typename T>
void quick_delete(T& v, size_t idx) {if (idx < v.size()) {v[idx] = move(v.back());v.pop_back();}
}

如你所见，其实很简单，就是简单的交换一下最后一个元素和目标元素然后直接使得长度减一，但是注意！必须是对那些排序不敏感的！

如果不确定自己访问容器会不会越界，那就使用.at方法而不是[]

是的，我们一直喜欢这样写来访问容器的元素：

vector v{ 19, 71, 47, 192, 4004 };
auto & i = v[2];

当然，一些人会争论我们应该这样写更好：

auto & i = v.at(2);

两者的区别何在呢？答案是：

at() 函数会进行边界检查，而 [] 运算符则不会。

这是有意为之，因为它允许 [] 运算符与原始 C 数组保持兼容性。让我们更详细地研究一下。

这里，我们来直接使用 [] 运算符直接访问向量中的第三个元素。与 C++ 中的大多数顺序对象一样，索引从 0 开始，因此第三个元素是数字 2。

向量有五个元素，编号为 0 到 4。如果我尝试访问元素编号 5，则会超出向量的边界：

vector v{ 19, 71, 47, 192, 4004 };
auto & i = v[5];
cout << format("element is {}\n", i);
element is 0

这个结果非常具有欺骗性。这是一个常见的错误，因为人类倾向于从 1 开始计数，而不是从 0 开始。但不能保证向量末尾之后的元素具有任何特定值。更糟糕的是，[] 运算符会默默地允许您写入超出向量末尾的位置：

vector v{ 19, 71, 47, 192, 4004 };
v[5] = 2001;
auto & i = v[5];
cout << format("element is {}\n", i);
element is 2001

现在已经写入不受我们控制的内存，对于MSVC的库，他会给我们惊喜：

越界内存访问是安全漏洞的主要原因之一。

解决方案是尽可能使用 at() 成员函数，而不是 [] 运算符：

vector v{ 19, 71, 47, 192, 4004 };
auto & i = v.at(5);
cout << format("element is {}\n", i);

现在我们得到一个运行时异常：

代码编译时没有错误，但 at() 函数会检查容器的边界，并在您尝试访问这些边界之外的内存时抛出运行时异常。 [] 运算符和 at() 成员函数执行相同的工作；它们根据容器元素的索引位置提供对容器元素的直接访问。 [] 运算符无需任何边界检查即可完成此操作，因此在某些迭代密集型应用程序中，它可能会稍微快一点。

好了，不说废话了：对于那些可以完全保证不会越界的代码段，使用[]无可厚非。但是笔者的态度是：总有人喜欢在酒吧里点炒饭，或者是-1杯啤酒，不要小看输入的多样性。所以，at() 函数应该是您的默认选择。

写过汇编的朋友都知道，比较两个数只需要几个CPU周期（啊哈！咱们不谈分支预测的事情，但是类似likely的操作总是好的，不是吗），但它是一种廉价的保险。对于大多数应用程序来说，其好处是值得的。

更加严肃的是，对于那些不允许因为内存overflow践踏而终止，或者希望程序自发的抛出异常传递而不是限制错误的编程理念的朋友更加应该使用at函数。他省去您做限制的心智负担。