第2章 STL容器

C++标准库中有大量的标准容器。容器通常包含一组数据或对象的集合。容器的厉害之处在于几乎可以和任何类型的对象一起使用，所以我们只需要为程序选择合适的容器即可。STL带给我们栈、自动增长的vector、map等等。这样我们就可以集中精力于我们的应用，而不用重复制作轮子。了解所有容器，对于C++开发者来说至关重要。

STL容器的分类如下，会在各节中进行详细描述：

• 连续存储

• 列表存储

• 搜索树

• 哈希表

• 容器适配器

连续存储

想要存储一组对象最简单的方式，就是将其一个接一个的存在一块比较大的内存当中。内存可以使用随机访问的方式进行，其时间复杂度为O(1)。

最简单的方式就是使用std::array，其就是对C风格数组的一种包装。不过，std::array要比C风格数组要先进的多，因为其没有运行时开销，而且进行元素添加时，也会十分舒适和安全。还有一点和C风格数组一样，一旦创建，其长度就是固定的，创建过后无法改变长度。

std::vector和std::array很类似，不过std::vector的长度可变。其会使用堆上的内存来存储对象。当新元素添加到vector中后，当前长度超过了原始的长度，那么std::vector会自动新分配一段更大的内存，用来放置包括新插入元素的所有元素，并且释放之前所占用的内存。此外，当新元素需要插入到两个旧元素之间时，std::vector会移动当前已有的元素。当要删除vector中间的一个已存在元素，那么vector类会自动地移动其他对象，将删除后的缝隙填补起来。

如果有大量元素在std::vector的头部或尾部进行插入或删除，那么为了填补空隙和移动已有元素，将会耗费很多时间。如遇到这样的情况，建议你考虑使用std::deque。对象集合会存储在多段固定长度的连续内存中，这些内存段是相互独立的。这就使得双向队列变得很简单，并且增长也很容易，因为不同的内存段相对独立，只需要将新分配的内存段加入就可以了，无需对其他已存在的内存段进行移动。减少的场景也是一样的。

列表存储

std::list是一个典型的双向链表。如果是单向列表，那就需要进行遍历，所以std::forward_list的优势在维护的复杂性上，因为其指针方向只有一个方向。列表遍历的时间复杂度是线性的O(n)。其在特定位置上插入和删除元素的时间复杂度为O(1)。

搜索树

当对象集具有可进行排序的自然属性时，可以使用小于的关系将这些元素进行排序，我们就可以使用搜索树来保存这个排序关系。从名字就可以看出，搜索树可以帮助我们很容易的通过一个关键字查找到对应元素，其搜索的时间复杂度为O(log(n))。

STL提供了不同种类的树，std::set是其中最简单的一种，保存元素不重复，存储的元素是可排序的(用一种树的结构)。

std::map使用的是另一种方式，将存储的数据使用组对进行存储。一个组对有一个key值和一个对应值构成。搜索树会对key值部分进行排序，使组对能作为std::map的一种关联容器。std::map的key值和std::set的值一样，在整个树中只能存在一个。

std::multiset和std::multimap是被特化的，key对象可以是重复的。

哈希表

讨论关联容器时，搜索树并不是唯一的方式。使用哈希表查找元素的时间复杂度只有O(1)，不过这就会忽略其自然序，所以不能简单的使用排序的方式进行遍历。哈希表大小可由用户控制，并且可以单独选择哈希函数，这是一项很重要的特性，因为其性能与空间复杂度依赖于此。

std::unordered_set和std::unordered_map具有很多接口与std::set和std::map一样，它们之间几乎可以相互替换。

搜索树的实现中，容器都具有多个变种： std::unordered_multiset和std::unordered_multimap，这两种方法都取消了对象/键的唯一性，因此我们可以用相同的键存储多个元素。

容器适配器

数组、列表、树和哈希表并不是存储和访问数据的唯一方式，这里还有栈、队列等其他的方式也可以存储和访问数据。类似的，越复杂的结构可以使用越原始的方式实现，并且STL使用以下形式的容器适配器进行操作：std::stack、std::queue和std::priotity_queue。

最牛X的是当我们需要这样的数据结构时，我们可以选择一种适配器。然后，当我们觉得到它们性能较差时，就可以改变一个模板参数，以便让适配器使用不同的容器实现。实践中，这也就意味着我们可以将std::stack实例中的元素类型从std::vector切换成std::deque。