# 第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`。