面试总结-C++常见模板内部实现及特性
C++常见模板类的内部实现以及特性总结
前言：面试官总是喜欢问数据结构的具体实现，所以今晚总结下，争取下次不会再回答不出来！唉，悲剧的我~
1. vector
（1）实现方式：
vector内部由数组实现，使用连续的内存存储，属于顺序存储结构。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacity()函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储。通常此默认的内存分配能完成大部分情况下的存储。
（2）优点：
- 不需要指定内存大小，即可以像数组一样操作，但可以进行动态操作，如：push_back()，pop_back()，insert()等。
- 随机访问方便,可以随机访问vector内任意一个元素，即支持[ ]操作符和vector.at()。
- 节省空间。
（3）缺点：
- 在内部进行插入删除操作效率低，尤其是在头部进行插入。
- 只能在vector的最后进行push和pop操作，不能在vector的头进行push和pop。
- 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放。
2. list
（1）实现方式：
list内部使用双向链表实现，使用的是非连续的内存空间进行存储，每一个结点都包括一个信息块Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。
（2）优点：
- 不使用连续内存完成动态操作。
- 在内部进行插入和删除操作方便，不需要拷贝和移动数据，只需要改变指针即可。
- 可在list的两端进行push、pop操作。
（3）缺点：
- 不能进行内部的随机访问，即不支持[ ]操作符和at()操作。
- 相对于verctor占用内存多
3. deque
（1）实现方式：
deque基于双端队列来实现，内部由一段一段（分块）的连续空间构成。vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。
（2）优点：
- deque在队列的两端放置元素和删除元素是高效的，而向量vector只是在插入序列的末尾时操作才是高效的。
- deque没有所谓的capacity观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
- deque容器支持对所有元素的随机访问，即可以进行[]和at()操作。
（3）缺点：
- 在deque容器的中间insert或erase元素效率比较低。
- deque内部数据结构比较复杂。
4. set和multiset
（1）实现方式：
set和multiset的内部均使用一种非常高效的平衡检索二叉树：红黑树来实现。
（2）特性：
- set中每个元素必须是唯一的，不允许出现键值重复，内部所有的元素都会被自动按照升序来排序，每个元素的值不能用迭代器来改变，可以理解为一个集合。可以进行insert()，erase()，find()，count()，clean()等操作，注意set的count()只能返回0或者1。
- multiset和set的区别在于multiset的元素可以相同，即内部可以出现重复的键值。multiset内部所有的元素同样自动按照升序来排序。multiset的基本操作和set类似，需要注意的是multiset的count()操作返回值可以大于1。而进行删除操作erase()时会删除所有值相同的key，如对{1,1,2}进行erase(1)后会变成{2}。
- set和multiset都引用<set>的头文件，时间复杂度均为
，效率非常高。
5. map和multimap
（1）实现方式：
map和multimap同样采用红黑树来实现。
（2）特性：
- map提供键和值一对一的映射关系，每个键不允许重复，不允许修改，但是键对应的值是可以修改的。map的内部元素自动按照键进行升序排序，因此不能对map用sort函数。map提供下标操作符，可直接存取元素，即可以使用[]和at()操作。
- multimap提供键和值一对多的映射关系，但multimap的键可以多次出现。multimap的内部元素同样会根据key自动对元素进行排序，但是multimap不支持使用[]和at()操作。multimap可以通过count()函数计算一个key值包含多少个值。
6. hash_map
（1）实现方式：
hash_map内部基于hash table（哈希表）来实现。 最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间，但代价是消耗比较多的内存。相当于用空间换时间。
（2）与map对比：
- 构造函数。hash_map需要hash函数（等于函数）；map只需要比较函数（小于函数）。
- 存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
总结
- 如果需要高效的随机存取，不在乎插入和删除的效率，使用vector
- 如果需要大量的插入和删除元素，不关心随机存取的效率，使用list
- 如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque
- 如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset
- 如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap
参考文献：
- https://blog.csdn.net/alex_xhl/article/details/37692297
- https://blog.csdn.net/terence1212/article/details/52487656
- https://blog.csdn.net/wl_ss/article/details/78065182
- https://blog.csdn.net/aa4790139/article/details/20617023
- https://blog.csdn.net/xiajun07061225/article/details/7459206
- http://www.cnblogs.com/hdk1993/p/5811577.html
- https://blog.csdn.net/weixin_35909255/article/details/70757138
- https://blog.csdn.net/wl_ss/article/details/78072909
- https://blog.csdn.net/chen134225/article/details/81744367
- https://www.cnblogs.com/SWiper/p/6617774.html
- https://blog.csdn.net/hero_myself/article/details/52312644
- https://blog.csdn.net/sinat_36165006/article/details/55803329
- https://www.cnblogs.com/engineerLF/p/5393006.html
