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数据结构是不一样的。

总结

1. 如果需要高效的随机存取，不在乎插入和删除的效率，使用vector
2. 如果需要大量的插入和删除元素，不关心随机存取的效率，使用list
3. 如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque
4. 如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset
5. 如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap

参考文献：

1. https://blog.csdn.net/alex_xhl/article/details/37692297
2. https://blog.csdn.net/terence1212/article/details/52487656
3. https://blog.csdn.net/wl_ss/article/details/78065182
4. https://blog.csdn.net/aa4790139/article/details/20617023
5. https://blog.csdn.net/xiajun07061225/article/details/7459206
6. http://www.cnblogs.com/hdk1993/p/5811577.html
7. https://blog.csdn.net/weixin_35909255/article/details/70757138
8. https://blog.csdn.net/wl_ss/article/details/78072909
9. https://blog.csdn.net/chen134225/article/details/81744367
10. https://www.cnblogs.com/SWiper/p/6617774.html
11. https://blog.csdn.net/hero_myself/article/details/52312644
12. https://blog.csdn.net/sinat_36165006/article/details/55803329
13. https://www.cnblogs.com/engineerLF/p/5393006.html