C++——STL容器

2021年11月24日 阅读数:4
这篇文章主要向大家介绍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
存储空间 静态 动态  动态

动态分段连续空间数据结构

(没用容量的概念)spa

 

迭代器   普通指针+,-,++,--,+=,-=,->,*  节点(向前指针,向后指针,数据)

非普通指针,很是复杂.net

故非必要不要用deque3d

数据结构  

单向开口的线性连续空间(头部也能够插入,但操做效率低,没法接受)指针

可变大小数组htm

 非连续空间,靠每一个元素点的先后指针来串联起来——双向链表,甚至是双向环形链表

双向开口的线性连续空间(头尾都可插入、删除元素)blog

star,finish两个迭代器,

map指针,

map大小

空间增长  

1.原大小的2倍增长空间;

2.拷贝原空间内容并构造新元素

3.释放原空间

4.指向原vector的迭代器失效,要当心

插入一个元素,配置一个空间;

删除一个元素,释放一个空间

 

随时增长新的分段空间并链接起来

没有空间保留

 任意位置插入数据    见下图1  插入,贴合,删除任意元素不会对其余元素/迭代器形成任何影响  操做复杂

 

 

 

选择原则:

一、若是你须要高效的随机存取,而不在意插入和删除的效率,使用vector
二、若是你须要大量的插入和删除,而不关心随机存取,则应使用list
三、若是你须要随机存取,并且关心两端数据的插入和删除,则应使用deque。

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

五、若是你要查找一个元素是否在某集合内存中,则使用set存储这个集合比较好

六、除非有更好的理由,不然用vector

七、不少很小的元素,额外开销——不要用list/forward_list

八、随机访问,vector/deque

九、只有头尾插入/删除,没有中间,用deque

十、输入时须要插入中间,随后访问随机

  • 肯定是否须要中间插入(能够先vector,后sort)
  • 确实须要,输入阶段使用list,完成后将list拷贝到vector

 

 

1、vector:简单,容许随机存储,数据的存取十分灵活,在缺省状况下应该使用。
2、deque:常常在头部和尾部安插和移除元素,而且存储的容量也比vector大得多。
3、list:若是常常在容器的中段执行安插,移除和移动元素。可是不支持随机存储。 list容器中尽可能不要使用删除操做,比插入操做多消耗近百倍
4、set和multiset:常常以某个准则寻找元素,可使用“以这个准则为排序准则”的set和multiset,在大量的数据状况下,对数复杂度比线性复杂度的效果要好的多。
5、map和multimap:使用(key、value)的pair,使用字典,使用关联式数组 e.g“map[key] = value”。
 

 

 

 

迭代器:类别、前进、后退、成员访问、取值dereference(*操做符)

 

1.序列式容器

1.1 vector

插入数据操做:

 

图1 Vector任意位置插入数据

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

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

 3.vector.capacity(); vector.reserve(n);vector.shrink_to_fit();

 1.2 list

 

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

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

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

 

 1.3 deque

 

 

 

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

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

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

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

 

2.容器适配器

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

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

2 新增、移除、得到顶端数据,除此以外,没法得到其余数据。

3 没有迭代器

4 deque、list均可以做为底层容器

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

 

2.2 queue(队列)

1 新增、移除,从尾端加入元素,从首端取出数据,此外,没法得到其余数据。不容许遍历

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

3 没有迭代器

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

 

3.关联性容器

 底层:红黑树

map:有序的key-word对

set:有序的key=word

multimap,multiset:有序的可重复出现的map/set

 

底层:哈希表

unordered_map:无序的key-word对

unordered_set:无序的key=word

unordered_multimap,unordered_multiset:无序的可重复出现的map/set

 

3.0 迭代器

 

单旋转和双旋转操做:

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

 单旋转:

 

双旋转:

 

3.1 红黑树

规则:

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

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

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

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

 

 

3.2 Set

1.元素的键值就是实值,迭代器只读

2.值自动排序

3.不容许相同的值

4.底层是红黑树

 

3.3 map

1.全部的元素都是键值和实值的pair,迭代器可读写word,但key只读

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

上一篇: cache-control 缓存
下一篇: 2019-1-2作业练习