C++——STL容器

2022-03-12 16:11:41

序列式容器：vector，list，deque；stack，queue（容器适配器），heap，priority_queue，slist

关联式容器：（底层都是红黑树）set，map，multiset，multimap，hashtable，hash_set，hash_map，hash_multiset，hash——multimap

综合对比：

	array	vector	list	deque
存储空间	静态	动态	动态	动态分段连续空间（没用容量的概念）
迭代器		普通指针+,-,++,--,+=,-=,->,*	节点（向前指针，向后指针，数据）	非普通指针，非常复杂故非必要不要用deque
数据结构		单向开口的线性连续空间（头部也可以插入，但操作效率低，无法接受）	非连续空间，靠每个元素点的前后指针来串联起来——双向链表，甚至是双向环形链表	双向开口的线性连续空间（头尾均可插入、删除元素） star,finish两个迭代器， map指针， map大小
空间增加		1.原大小的2倍增加空间； 2.拷贝原空间内容并构造新元素 3.释放原空间 4.指向原vector的迭代器失效，要小心	插入一个元素，配置一个空间；删除一个元素，释放一个空间	随时增加新的分段空间并连接起来没有空间保留
任意位置插入数据		见下图1	插入，贴合，删除任意元素不会对其他元素/迭代器造成任何影响	操作复杂

选择原则：

1、如果你需要高效的随机存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随机存取，则应使用list
3、如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque。

4、如果你要存储一个数据字典，并要求方便地根据key找value，那么map是较好的选择

5、如果你要查找一个元素是否在某集合内存中，则使用set存储这个集合比较好

一、vector：简单，允许随机存储，数据的存取十分灵活，在缺省情况下应该使用。
二、deque：经常在头部和尾部安插和移除元素，并且存储的容量也比vector大得多。
三、list：如果经常在容器的中段执行安插，移除和移动元素。但是不支持随机存储。 list容器中尽量不要使用删除操作，比插入操作多消耗近百倍
四、set和multiset：经常以某个准则寻找元素，可以使用“以这个准则为排序准则”的set和multiset，在大量的数据情况下，对数复杂度比线性复杂度的效果要好的多。
五、map和multimap：使用（key、value）的pair，使用字典，使用关联式数组 e.g“map[key] = value”。

迭代器：类别、前进、后退、成员访问、取值dereference(*操作符）