C++——STL容器

2019/01/04 18:42
阅读数 49

 

序列式容器: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存储这个集合比较好

6、除非有更好的理由,否则用vector

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

8、随机访问,vector/deque

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

10、输入时需要插入中间,随后访问随机

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

 

 

一、vector:简单,允许随机存储,数据的存取十分灵活,在缺省情况下应该使用。
二、deque:经常在头部和尾部安插和移除元素,并且存储的容量也比vector大得多。
三、list:如果经常在容器的中段执行安插,移除和移动元素。但是不支持随机存储。 list容器中尽量不要使用删除操作,比插入操作多消耗近百倍
四、set和multiset:经常以某个准则寻找元素,可以使用“以这个准则为排序准则”的set和multiset,在大量的数据情况下,对数复杂度比线性复杂度的效果要好的多。
五、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

展开阅读全文
c++
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部