总结在先：
１、如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；
2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；
3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；
4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；
5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset。
一、顺序容器
vector 底层：动态开辟的二维数组
优点：
内存连续，支持指针偏移
1、直接访问速度任何元素 特别快 O(1)
2、尾部快速插入和删除O(1)
缺点：
在除尾部插入以外，O(n)，此外当被插入的空间不够时，需要重新申请一块足够大的内存并进行内存拷贝，vector每次扩容为原来的两倍，对小对象来说执行效率高，对大对象来说效率就低了
list 底层：双向循环链表
优点：
支持任意位置快速插入和删除 （因为传入迭代器）插入时间复杂度O(1)
缺点：
链表随机访问效率低
deque 底层：双端队列
合并了 vector和list 的优点
优点：
1、支持在头部和尾部快速插入和删除，、
2、直接访问任意元素（迭代器里面已经把不同部分的数据之间的差距屏蔽掉了）
缺点：
中部插入和删除还需要挪动数据
二、关联容器 底层：红黑树
set ：类似于数学中的集合，不包含重复的元素，底层用红黑树实现，是一种二叉平衡树，便于元素查找
multi_set ：支持重复元素的集合
map：映射表，一个键只出现一次 提供一对一的数据数据能力，这种特性使得map 类似于一颗红黑树，
multi_map：允许键重复
三、容器适配器 stack queue priority_queue
stack：栈，先进后出 ,底层封装了deque
queue：队列，先进先出， 底层封装了deque
priority_queue：优先级队列， 底层是最小堆
根据容器选择数据结构，容器的优缺点就是底层数据结构的优缺点
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
