一、容器的分类
1、序列容器
（1）vector
典型的序列容器，任意元素的读取、修改具有O(1)，在序列尾部进行插入、删除是O(1)，但在序列的头部插入、删除的时间复杂度是O(n)，可以在任何位置插入新元素，有随机访问功能，插入删除操作需要考虑。
（2）deque
序列容器，内存也是连续的，和vector相似，区别在于在序列的头部插入和删除操作也是O(1), 可以 在任何位置插入新元素，有随机访问功能。
（3）list
序列容器，内存是不连续的，任意元素的访问、修改时间复杂度是O(n)，插入、删除操作是O(1), 可以在任何位置插入新元素。
2、关联容器
（1）set
关联容器，元素不允许有重复，数据被组织成一棵红黑树，查找的速度非常快，时间复杂度是O(logN)
（2）multiset
关联容器，和set一样，是允许有重复的元素，具备时间复杂度O(logN)查找功能。
（3）map
关联容器，按照{键，值}方式组成集合，按照键组织成一棵红黑树，查找的时间复杂度O(logN)，其中键不允许重复。
（4）multimap
和map一样，区别是键可以重复
3、容器适配器
二、使用中需要考虑的一些因素
1、需要添加大量元素
不适合用vector，因为vector底层是数组，当前容量不足时就要扩容，将所有旧元素全部拷贝到新内存中，开销太大
适合用list
deque是vector和list的折中，内存不够时需要申请新内存但不用拷贝旧数据
2、查找速度
对于序列容器需要分两种情况，区分依据是元素是否排序
1)对于已经排序的序列容器，使用binary_search可以获得对数时间复杂度的查找速度(O(logN));
2)而未排序的序列容器二分查找肯定是用不了，能达到的最好的时间复杂度是线性的(O(n))。
对于关联容器，存储的时候存储的是一棵红黑树，总是能达到对数时间复杂度(O(logN))的效率，因为关联容器是按照键值排好序的。
3、内存是否连续
vector、deque是连续内存的，其中vector是完全连续内存，而deque是vector和list的折中实现，是多个内存块组成的，每个块中存放的元素连续内存，而内存块又像链表一样连接起来。所以需要考虑在操作的过程中是否有在任意位置插入元素的需求，有这种需求的话尽量避免使用连续内存的vector、deque
4、元素的排序
序列容器是不会自动排序的，而关联容器通过键值对根据某种关系进行排序；所以默认情况下序列容器中的元素是无序的，而关联容器中的元素是有序的。
三、具体使用
在实际使用过程中，到底选择这几种容器中的哪一个，可以根据以下原则：
1、如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；
2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；
3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；
4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；
5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
