stl容器区别: vector list deque set map [转]
转自:http://blog.csdn.net/lmh12506/article/details/8445025
在STL中基本容器有: vector、list、deque、set、map
set 和map都是无序的保存元素,只能通过它提供的接口对里面的元素进行访问
set:集合, 用来判断某一个元素是不是在一个组里面,使用的比较少
map:映射,相当于字典,把一个值映射成另一个值,如果想创建字典的话使用它好了
底层采用的是树型结构,多数使用平衡二叉树实现,查找某一值是常数时间,遍历起来效果也不错, 只是每次插入值的时候,会重新构成底层的平衡二叉树,效率有一定影响.
vector、list、deque是有序容器
1.vector
vector就是动态数组.它也是在堆中分配内存,元素连续存放,有保留内存,如果减少大小后,内存也不会释放.如果新值>当前大小时才会再分配内存.
它拥有一段连续的内存空间,并且起始地址不变,因此它能非常好的支持随即存取,即[]操作符,但由于它的内存空间是连续的,所以在中间进行插入和删除会造成内存块的拷贝,另外,当该数组后的内存空间不够时,需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。
对最后元素操作最快(在后面添加删除最快 ), 此时一般不需要移动内存,只有保留内存不够时才需要
对中间和开始处进行添加删除元素操作需要移动内存,如果你的元素是结构或是类,那么移动的同时还会进行构造和析构操作,所以性能不高 (最好将结构或类的指针放入vector中,而不是结构或类本身,这样可以避免移动时的构造与析构)。
访问方面,对任何元素的访问都是O(1),也就是是常数的,所以vector常用来保存需要经常进行随机访问的内容,并且不需要经常对中间元素进行添加删除操作.
相比较可以看到vector的属性与string差不多,同样可以使用capacity看当前保留的内存,使用swap来减少它使用的内存.
capacity()返回vector所能容纳的元素数量(在不重新分配内存的情况下) 测试push_back 1000个数据 capacity返回16384
总结
需要经常随机访问请用vector
2.list
list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随机存取变的非常没有效率,因此它没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除和插入。
list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存.
list在哪里添加删除元素性能都很高,不需要移动内存,当然也不需要对每个元素都进行构造与析构了,所以常用来做随机操作容器.
但是访问list里面的元素时就开始和最后访问最快
访问其它元素都是O(n) ,所以如果需要经常随机访问的话,还是使用其它的好
总结
如果你喜欢经常添加删除大对象的话,那么请使用list
要保存的对象不大,构造与析构操作不复杂,那么可以使用vector代替
list<指针>完全是性能最低的做法,这种情况下还是使用vector<指针>好,因为指针没有构造与析构,也不占用很大内存
3.deque
deque是一个双端队列(double-ended queue),也是在堆中保存内容的.它的保存形式如下:
[堆1]
...
[堆2]
...
[堆3]
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.
它支持[]操作符,也就是支持随即存取,可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度,和 vector的效率相差无几,它支持在两端的操作:push_back,push_front,pop_back,pop_front等,并且在两端操作 上与list的效率也差不多。
在标准库中vector和deque提供几乎相同的接口,在结构上它们的区别主要在于这两种容器在组织内存上不一样,deque是按页或块来分配存储器 的,每页包含固定数目的元素.相反vector分配一段连续的内存,vector只是在序列的尾段插入元素时才有效率,而deque的分页组织方式即使在 容器的前端也可以提供常数时间的insert和erase操作,而且在体积增长方面也比vector更具有效率
总结:
vector是可以快速地在最后添加删除元素,并可以快速地访问任意元素
list是可以快速地在所有地方添加删除元素,但是只能快速地访问最开始与最后的元素
deque在开始和最后添加元素都一样快,并提供了随机访问方法,像vector一样使用[]访问任意元素,但是随机访问速度比不上vector快,因为它要内部处理堆跳转
deque也有保留空间.另外,由于deque不要求连续空间,所以可以保存的元素比vector更大,这点也要注意一下.还有就是在前面和后面添加元素时都不需要移动其它块的元素,所以性能也很高。
因此在实际使用时,如何选择这三个容器中哪一个,应根据你的需要而定,一般应遵循下面
的原则:
1、如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector
2、如果你需要大量的插入和删除,而不关心随即存取,则应使用list
3、如果你需要随即存取,而且关心两端数据的插入和删除,则应使用deque。
相关推荐
stl_test STL中deque、list、vector、stack、map、set、hashmap的基本应用
标准STL序列容器:vector、string、deque和list。 标准STL关联容器:set、multiset、map和multimap。
c++ STL容器使用代码,方便学习 vector string deque queue list set map multiset multimap 容器的API使用方法等
第10章 bit_vector位向量容器 149 10.1 bit_vector技术原理 149 10.2 bit_vector应用基础 156 10.3 本章小结 161 第11章 set集合容器 162 11.1 set技术原理 162 11.2 set应用基础 181 11.3 本章小结...
STL中的容器按存储方式分为两类,一类是按以数组形式存储的容器(如:vector 、deque);另一类是以不连续的节点形式存储的容器(如:list、set、map)。在使用erase方法来删除元素时,需要注意一些问题。 1.list,set...
容器:各种数据结构,如vector,deque,list,stack,set,map等 (2).算法:各种常用的算法,如sort,find,copy,for_each等 (3).迭代器:用于连接容器和算法,,可初略理解为指针,用法相像 (4).仿函数:行为类似函数,...
# The following STL containers are currently supported: # # std::vector<T> -- via pvector command # std::list<T> -- via plist or plist_member command # std::map,T> -- via pmap or pmap_member command #...
顺序容器:vector,list,deque 顺序容器适配器:stack,queue 关联容器:set,map,multiset,multimap 无序关联容器:unordered_set,unordered_map,unordered_multiset,unordered_multimap 容器均支持列表初始...
本书共分5篇26章,以“C++编程技术→C++ STL泛化技术基础→C++ STL容器技术→C++ STL算法技术→C++ STL迭代器技术”为线索具体展开,通过大量的源码分析和应用实例,详细介绍了C++ STL的技术原理和使用方法。...
STL中的常用容器包括:顺序性容器(vector、deque、list)、关联容器(map、set)、容器适配器(queue、stac)。 1、顺序性容器 (1)vectorvector是一种动态数组,在内存中具有连续的存储空间,支持快速随机访问。...
侯捷 STL源码剖析:一本剖析下面内容的书籍:vector、list、heap、deque、red black tree、hash table、set、map等等
1、容器(containers):各种数据结构,如vertor,list,deque,set,map.从实现的角度来看,STL容器是一种class template 2、算法(algorithms):各种算法如sort,search,copy,earse。STL算法是一种 function ...
容器(Containers):各种数据结构,如Vector,Deque,List,Set,Map,用来存放数据,STL容器是一种Class Template,就体积而言,这一部分很像冰山载海面的比率。 算法(Algorithms):各种常用算法,如Sort,Search...
c++ std stl各容器的应用场合及性能 map hash_map unordered_map multimap list forward_list vector set hash_set multiset unsorted_set queue deque priority_queue
STL中的常用容器包括:顺序性容器(vector、deque、list)、关联容器(map、set)、容器适配器(queue、stac)。 1、顺序性容器 (1)vectorvector是一种动态数组,在内存中具有连续的存储空间,支持快速随机访问。...
该篇分为十一部分,分别是:vector类的主要成员、deque类的主要成员、list类的主要成员、 stack类的主要成员、queue类的主要成员、priority_queue类的组要成员、set类的主要成员、multiset类的主要成员、map类的主要...
STL的Vector、List、deque、set、map、queue、stack等的使用,包含了基本的用法
STL介绍 3 1、STL简介 3 2、算法 3 3、容器 3 4、迭代器 4 5、使用注意 4 一、stack 堆栈 5 成员函数: 5 实例程序: 5 二、queue 队列 6 成员函数: 6 实例程序: 6 三、Priority Queues 优先队列 7 成员函数: 7 ...
STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的...在C++标准中,STL被组织为下面的13个头文件:、<deque>、、、<vector>、<list>、<map>、 、、、<set>、和。