C++标准库容器类概述
基础概念
容器（container）：
- 容纳特定类型对象的集合。
- C++中所有的容器都是类模板。
- 所有容器类型都定义了默认构造函数，用于创建指定类型的空容器对象。容器默认构造函数不带参数。
- 为了使程序更清晰、简短，容器类型最常用的构造函数是默认构造函数。在大多数的程序中，使用默认构造函数能达到最佳运行时性能，并且使容器更容易使用。
容器都是类模板。它们实例化后就成为容器类。用容器类定义的对象称为容器对象。容器适配器（adaptors）：
- 适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。即通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要。
- 容器适配器本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。当然，如果必要的话，容器适配器中也可以自创新的成员函数。
- STL 中的容器适配器，其内部使用的基础容器并不是固定的，用户可以在满足特定条件的多个基础容器中自由选择。
- 什么是适配器，C++ STL容器适配器详解
顺序容器和关联容器
关联容器和顺序容器的根本不同在于：
- 关联容器中的元素是按关键字来保存和访问的
- 顺序容器中的元素则是按它们在容器中的位置来顺序保存和访问的。
顺序容器
顺序容器（sequential container）：
- 它将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。
- 顺序容器不是排序的：元素排列次序与元素值无关。
- 而是由元素添加到容器里的次序决定。
- 主要的有三种：
可变长动态数组 vector、双端队列 deque、双向链表 list。 - 汇总的有vector、deque、list、forward_list、array、string等。
表1. 顺序容器与顺序容器适配器:
| 顺序容器 | 用途 | 顺序容器适配器 | 用途 | 底层基础容器 |
|---|---|---|---|---|
| vector | 可变长动态数组，支持快速随机访问 | stack |
后进先出（LIFO）堆栈 | 默认使用deque。满足条件的基础容器有 vector、deque、list |
| list | 双向链表，支持快速插入/删除 | queue |
先进先出（FIFO）队列 | 默认使用deque。满足条件的基础容器有 deque、list |
| deque | 双端队列 | priority_queue |
有优先级管理的队列 | 默认使用vector。满足条件的基础容器有vector、deque。 |
除了上面的表格之外还存在forward_list顺序容器（单向链表，只支持单向顺序访问），请看文章链接
关联容器
关联容器（Associative containers）：
- 支持通过键（key）来高效地查找和读取元素。
- 关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。虽然关联容器的大部分行为与顺序容器相同，但其独特之处在于支持键的使用。
- 关联容器支持很多顺序容器也提供的相同操作，此外，还提供管理或使用键的特殊操作。关联容器共享大部分但并非全部的顺序容器操作。关联容器不提供front、 push_front、 pop_front、back、push_back 以及 pop_back 操作。
有序关联容器
有序关联容器有以下四种：set、multiset、map、multimap。
- 容器元素根据键的次序排列。插入元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插入元素时不能指定位置。
- 默认情况下，关联容器中的元素是从小到大排序（或按关键字从小到大排序）的，而且用<运算符比较元素或关键字大小。因为是排好序的，所以关联容器在查找时具有非常好的性能。
- 在迭代遍历关联容器时，我们可确保按键的顺序的访问元素，而与元素在容器中的存放位置完全无关。
map
- 以键－值（key-value）对的形式组织：键(key)用作元素在 map 中的索引，而值(value)则表示所存储和读取的数据。
- map 类型通常可理解为
关联数组（associative array）：可使用键作为下标来获取一个值，正如内置数组类型一样。
常用操作：
| map查询操作 操作 | 作用 |
|---|---|
| m.count(k) | 返回 m 中 k 的出现次数 |
| m.find(k) | 如果 m 容器中存在按 k 索引的元素，则返回指向该元素的迭代器。如果不存在，则返回超出末端迭代器 |
使用 count 检查 map 对象中某键是否存在:
1 | int occurs = 0; |
读取元素而不插入该元素:
1 | //find 操作返回指向元素的迭代器，如果元素不存在，则返回 end 迭代器： |
更好的请参考：《C++Primer》第十章-关联容器-学习笔记(1)-pair&map
multimap
- 支持同一个键多次出现的 map 类型
set
- set 容器只是单纯的键的集合。每个元素仅包含一个键(key)，并有效地支持关于某个键是否存在的查询。
- 适用条件：
- 如果希望有效地存储不同值的集合，那么使用 set 容器比较合适
- 当只想知道一个值是否存在时，使用 set 容器是最适合的。
- set 不支持下标操作符，而且没有定义 mapped_type 类型。在 set 容器中，value_type 不是 pair 类型，而是与 key_type 相同的类型。
- set 容器存储的键也必须唯一，而且不能修改（也体现了 set 存储的元素仅仅是键，而没有所关联的值）
multiset
- 支持同一个键多次出现的 map 类型
multimap和 multiset 类型与相应的单元素版本具有相同的头文件定义：分别是 map 和set 头文件。
multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同，只有一个例外：multimap 不支持下标运算。
无序关联容器
unordered_map
unordered_multimap
unordered_set
unordered_multiset
STL容器类库
<vector>：定义vector序列模板，是一个大小可以重新设置的数组类型，比普通数组更安全、更灵活。<list>：定义list序列模板，是一个序列的链表，常常在任意位置插入和删除元素。<deque>：定义deque序列模板，支持在开始和结尾的高效插入和删除操作。<queue>：为队列(先进先出)数据结构定义序列适配器queue和priority_queue。<stack>：为堆栈(后进先出)数据结构定义序列适配器stack。<map>：map是一个关联容器类型，允许根据键值是唯一的，且按照升序存储。multimap类似于map，但键不是唯一的。<set>：set是一个关联容器类型，用于以升序方式存储唯一值。multiset类似于set，但是值不必是唯一的。<bitset>：为固定长度的位序列定义bitset模板，它可以看作固定长度的紧凑型bool数组。类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。<array>：（TR1）固定大小数组，支持复制。<forward_list>：（c++11）单向列表，forward_list不提供随机访问，这一点跟list相同。forward_list是一个单向链表，只支持单向顺序访问，在链表的任何位置进行插入/删除操作都非常快。<unordered_set>：（TR1)无序容器set，其元素随机存放。唯一键的集合，按键散列。multiset类似于set，但是值不必是唯一的。<unordered_map>：（C++11）（TR1)无序容器map，其键值随机存放。键-值对的集合，由键散列，键是唯一的multimap类似于map，但键不是唯一的。
完整的看C++中常用的std标准容器
STL容器类底层实现
vector
底层数据结构为数组 ，支持快速随机访问
list
底层数据结构为双向链表，支持快速增删
deque
- 底层数据结构为一个中央控制器和多个缓冲区
- 支持首尾（中间不能）快速增删，也支持随机访问
- STL源码分析146页
forward_list
- 顺序容器，底层数据结构为单向链表。
- 只支持单向顺序访问，支持快速增删
stack
- 底层一般用list和deque实现，封闭头部即可。
- 不用vector的原因应该是容量大小有限制，扩容耗时。
queue
- 底层一般用list和deque实现，封闭头部即可
- 不用vector的原因应该是容量大小有限制，扩容耗时
priority_queue
底层数据结构：一般是vector为底层容器，堆heap为处理规则来管理底层容器实现
set
底层数据结构为红黑树，有序，不重复
multiset
底层数据结构为红黑树，有序，可重复
map
底层数据结构为红黑树，有序，不重复
multimap
底层数据结构为红黑树，有序，可重复
hash_set
底层数据结构为hash表，无序，不重复
hash_multiset
底层数据结构为hash表，无序，可重复
hash_map
底层数据结构为hash表，无序，不重复
hash_multimap
底层数据结构为hash表，无序，可重复
参考资料
C++容器（STL容器）
C++语言学习（九）——C++标准库简介
Containers library(cppreference.com)
C++中常用的std标准容器 //可以做查找表
C++中容易忘的知识点——list和forward_list（四）//可做查寻表
C++ STL 的底层实现
C++标准模板库（STL）的容器的底层实现
C++STL的容器的底层实现详解//可以做查找表