C++顺序容器与关联容器的部分基础知识
一、基本概念
1-1 概述
1 容器：类模板，通用数据结构（容器元素的组织方式）
2 迭代器：类似于指针，可依次存取容器中的元素(访问容器元素的媒介)
3 算法：函数模板，操作容器中的元素（操作方法）。
注意点：
- 算法模板实现了对元素类型的无视
- 如果容器中元素是类的对象，被插入的对象往往是复制品
- 许多容器往往需要对元素进行排序，此时往往要对相关的类重载==和<运算符
1-2 容器的分类
顺序容器(sequential container)
- 顺序容器中元素的顺序不受元素的值影响，而是与元素添加到容器中的位置对应。
关联容器(associative container)
- 关联容器中元素的顺序取决于键值（key value）
容器适配器(container adaptors )
- 与容器显著区别：容器适配器是没有迭代器的，也就是说STL中的算法模板是无法对容器适配器使用的。
二、顺序容器
2-1 顺序容器简介
顺序容器的特点：
共同点：
- 顺序访问容器中的元素都非常快
不同点：
- 在容器中插入与删除元素时间
- 随机的访问容器中元素的时间
使用方法：包含与容器名称一样的头文件名
| 容器名称 | 随机访问元素 | 特点 |
|---|---|---|
| vector | 支持 | 连续存储，增添元素可能需要重新分配内存 |
| string | 支持 | 连续存储，增添元素可能需要重新分配内存 |
| deque | 支持 | 头尾添加删除与元素特别快 |
| list | 不支持 | 双向链表，删除与添加元素快 |
| forward_list(C++11) | 不支持 | 单链表，删除与添加元素快 |
| array(C++11) | 支持 | 替换内置的数组 |
vector(动态数组):大部分时间尾部增删元素具有较佳性能（O（1）），序列变长由于内部空间不够，重新分配
deque(双端队列):大部分时间二端增删元素具有较佳性能。
list(双端链表)：任何位置增删元素都是常数时间
2-2 顺序容器的容器适配器
适配器是库中一个通用的概念，除了容器适配器，还有函数适配器以及函数适配器以及迭代器适配器等。
简单讲，适配器使得某种东西表现的像另外一个东西。
例：stack adaptor takes a sequential container (other than array or forward_list) and makes it operate as if it were a stack.
three sequential container adaptors （3种顺序容器适配器）
- stack（栈）
- queue（队列）
- priority_queue (优先队列)
- 在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有*先出 的行为特征。
注意点：
-
默认stack与queue适配器使用的容器时deque, priority_queue使用的容器时vector，当然也可以自己改变容器适配器的第二个参数指定使用的顺序容器，比如下面stack容器适配器使用的是vector，而不是默认的deque。
- stack<string, vector
>
- stack<string, vector
- 与容器相比，容器适配器是没有迭代器的，也就是说STL中的算法模板是无法对容器适配器使用的。
2-3 顺序容器的用法查询
std::array
三、关联容器
3-1 关联容器简介
关联容器与顺序容器的主要区别：
- 关联容器中元素的检索与存储都是通过key实现。
关联容器的特点：
共同点：
- 通过key能够实现高效的查找
不同点：
-
关联容器是 set 或者map
- set是只有key，没有value。可以理解为只有单词表没有单词的解释的的字典。
- map则是既有key，也有value。可以理解为一个字典既有单词也有每个单词的解释
-
关联容器的key是唯一或者key是可以重复的(multiple keys)
-
关联容器的元素是有序的 或者无序的
| 关联容器名称 | 特点 |
|---|---|
| map | 容器中的元素是键值对（key-value pair） |
| set | key就是value |
| multimap | key可以重复出现 |
| multiset | key可以重复出现 |
| unordered_map | 使用hash函数实现 |
| unordered_set | 使用hash函数实现 |
| unordered_multimap | 使用hash函数实现，key可以重复出现 |
| unordered_multiset | 使用hash函数实现，key可以重复出现 |
从表格中可以看到
- 关联容器只能是map或者key
- 通过名称中是否带有multi可以看出key是否重复
- 默认的关联容器元素是按照key进行排序的，底层的数据结构是红黑树，从而保证有效性，但是如果名称中带有unordered时，则元素存储是无序的，使用hash表实现，查询效率高。
注意点：
- 有序的关联容器再使用时，指定的key的类型必须时可比较的。如果使用个对象作为key,那么必须去重载<使得key是可比较的。
参考资料
C++ primer 5th charpter9 & charpter 10
吐槽：时间过得真快，上次看C++的还是2年前。好多东西都忘光了。
-----20200704