STL 容器
在 C++ 标准模板库（STL）中，有几种常见的容器，每种都有其特定的用途和实现原理。
总揽
STL容器是用来存储和管理数据的数据结构，它们都提供了一些通用的成员函数，如插入元素、删除元素、查找元素等。STL容器主要分为三大类：序列容器、关联容器和无序关联容器。
-
序列容器：序列容器是元素的线性排列，元素的位置取决于插入的位置和顺序。主要包括
vector、deque、list、forward_list和array。vector：动态数组，支持快速随机访问。deque：双端队列，支持快速随机访问，可以在头部和尾部插入或删除元素。list：双向链表，只支持双向顺序访问，但在任何位置插入和删除元素都非常快速。forward_list：单向链表，只支持单向顺序访问。array：静态数组，支持快速随机访问，但大小固定。
-
关联容器：关联容器中的元素是按关键字来保存和访问的。主要包括
set、multiset、map和multimap。set：集合，内部元素按照特定顺序排序，每个元素只能出现一次。multiset：集合，内部元素按照特定顺序排序，每个元素可以出现多次。map：映射，保存键值对，按照键排序，每个键只能出现一次。multimap：映射，保存键值对，按照键排序，每个键可以出现多次。
-
无序关联容器：无序关联容器中的元素不按特定的顺序排序，而是根据元素的哈希值放在不同的位置，主要包括
unordered_set、unordered_multiset、unordered_map和unordered_multimap。unordered_set：无序集合，元素在内部并不以任何特定顺序排序，而是根据元素的哈希值组织在一起，每个元素只能出现一次。unordered_multiset：无序集合，元素在内部并不以任何特定顺序排序，而是根据元素的哈希值组织在一起，每个元素可以出现多次。unordered_map：无序映射，保存键值对，元素在内部并不以任何特定顺序排序，而是根据键的哈希值组织在一起，每个键只能出现一次。unordered_multimap：无序映射，保存键值对，元素在内部并不以任何特定顺序排序，而是根据键的哈希值组织在一起，每个键可以出现多次。
这些容器都有各自的优点和适用场景，选择哪种容器取决于你的具体需求，如插入和删除的效率、是否需要快速随机访问等。
选择容器时需要考虑哪些问题？
这个问题本质上是在考察数据结构。下面是一个简要的参考：
-
数据插入和删除的位置：如果你需要在容器的任意位置插入或删除数据，那么应该选择顺序容器，如
vector、deque、list等。关联容器和无序关联容器通常不支持在任意位置插入或删除数据。 -
元素排序：如果你需要元素按某种特定顺序存储，那么应该选择关联容器，如
set、map等，它们会自动按键值对进行排序。如果你不关心元素的排序，那么无序关联容器，如unordered_set、unordered_map等，可能是更好的选择。 -
查找效率：如果你需要频繁地查找元素，那么应该选择关联容器或无序关联容器，因为它们提供了基于键的快速查找。而顺序容器的查找通常需要遍历整个容器，效率较低。
-
空间效率：如果内存空间有限，那么应该选择空间效率高的容器。例如，
list和forward_list比vector和deque更节省内存，因为它们不需要预分配额外的内存空间。 -
迭代器类型：不同的容器提供了不同类型的迭代器，如前向迭代器、双向迭代器、随机访问迭代器等。你需要根据你的需求选择提供了合适迭代器的容器。
-
是否需要频繁改变容器大小：如果你需要频繁地添加或删除元素，那么
vector或string可能不是最好的选择，因为这可能导致频繁的内存分配和释放。在这种情况下，list、deque或forward_list可能是更好的选择。 -
元素类型：不同的容器对元素类型有不同的要求。例如，
array要求所有元素的类型相同，而map和set则要求元素类型可以进行比较操作。你需要选择能够满足你的元素类型要求的容器。