神秘博客

STL中list,vector,deque,map,set区别、联系和使用场景

vector和built-in数组类似,它拥有一段连续的内存空间,并且起始地址不变,因此
它能非常好的支持随即存取,即[]操作符,但由于它的内存空间是连续的,所以在中间
进行插入和删除会造成内存块的拷贝,另外,当该数组后的内存空间不够时,需要重新
申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。

list就是数据结构中的双向链表(根据sgi   stl源代码),因此它的内存空间可以是不连续
的,通过指针来进行数据的访问,这个特点使得它的随即存取变的非常没有效率,因此它
没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除
和插入。

deque是一个double-ended   queue,它的具体实现不太清楚,但知道它具有以下两个特点:
它支持[]操作符,也就是支持随即存取,并且和vector的效率相差无几,它支持在两端的
操作:push_back,push_front,pop_back,pop_front等,并且在两端操作上与list的效率
也差不多。

Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性map内部的实现自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能。

set是集合,set中不会包含重复的元素,这是和vector的第一个区别,第二个区别是set内部用平衡二叉树实现,便于元素查找,而vector是使用连续内存存储,便于随机存取。
因此在实际使用时,如何选择这几个容器中哪一个,应根据你的需要而定,一般应遵循下面
的原则:
1、如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector
2、如果你需要大量的插入和删除,而不关心随即存取,则应使用list
3、如果你需要随即存取,而且关心两端数据的插入和删除,则应使用deque。

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

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

版权说明:
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

觉得文章有用就请我吃包辣条吧

微信扫一扫打赏