C++——STL容器

序列式容器: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  插入,贴合,删除任意元素不会对其他元素/迭代器造成任何影响  操作复杂

C++——STL容器

选择原则:

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(*操作符)

1.序列式容器

1.1 vector

C++——STL容器

插入数据操作:

C++——STL容器

C++——STL容器

C++——STL容器

图1 Vector任意位置插入数据

①vector不适合push_front(效率很低)

②vector不适合中间插入删除操作。中间插入删除操作会引起内存拷贝。

1.2 list

C++——STL容器

C++——STL容器

list采用非线性的空间存储数据。

①list适合插入删除频繁的场所。不管插入还是删除,时间基本上都是常数。

②list不适合随机线性访问。

1.3 deque

C++——STL容器

C++——STL容器

C++——STL容器

deque采用类似文件系统的方式存储数据。其中有数个连续空间的缓冲区存储数据。这些缓冲区连接起来,给上层用户一个假象就是,存储的数据空间是连续的。

deque是list和vector的折中方案。兼有list的优点,也有vector随机线性访问效率高的优点。

①deque仍旧不适合中间插入删除操作。

②deque适合线性随机访问数据。

2.容器适配器

2.1 stack(栈,垛)先进,后出

1 继承自deque(封闭头部开口)——更像一个adapter而不是container

C++——STL容器

2 新增、移除、获得顶端数据,除此之外,无法获得其他数据。

3 没有迭代器

4 deque、list都可以作为底层容器

stack是deque的一种变种,优缺点不变。

2.2 queue(队列)

C++——STL容器

1 新增、移除,从尾端加入元素,从首端取出数据,此外,无法获得其他数据。不允许遍历

2 SGI STL 以deque为底部容器,封闭其前端入口和后端出口,前端只允许出,后端只允许入,即为queue

3 没有迭代器

4.queue是deque的一种变种,优缺点不变。

3.关联性容器

单旋转和双旋转操作:

C++——STL容器

对1和4用单旋转操作,2和3用双旋转操作

单旋转:

C++——STL容器

双旋转:

C++——STL容器

3.1 红黑树

规则:

C++——STL容器

1. 节点:颜色,父节点指针,左右节点指针,值

2. 迭代器:基本迭代器和继承的迭代器两层组成

3. 插入操作:1. 插入值:——对比节点键值(遇大往左,遇小往右)——得到新值的插入点、父节点——插入值(维护leftmost和rightmost,设定父节点、左右子节点)

      2. 更新树:更改颜色,旋转树使其平衡

3.2 Set

1.元素的键值就是实值

2.值自动排序

3.不允许相同的值

4.底层是红黑树

3.3 map

1.所有的元素都是键值和实值的pair

2.不允许相同键值

3.键值自动排序

4.底层是红黑树

3.3 multiset

set(insert_unique)+允许键值重复:insert_equal

3.4 multimap

map(insert_unique)+允许键值重复:insert_equal

4.hashtable

参考:

原文:https://blog.csdn.net/u013299585/article/details/78323973

https://blog.csdn.net/caojunhao123/article/details/11907857

上一篇:Zabbix探索:网络设备监控2


下一篇:使用john破解ubuntu(linux)9.10密码