在STL中基本容器有: string、vector、list、deque。
set 和map都是无序的保存元素,只能通过它提供的接口对里面的元素进行访问;
set: 集合, 用来判断某一个元素是不是在一个组里面,使用的比较少;
map: 映射,相当于字典,把一个值映射成另一个值,如果想创建字典的话使用它好了;
底层采用的是树型结构,多数使用平衡二叉树(RB-Tree)实现,查找某一值是常数时间,遍历起来效果也不错, 只是每次插入值的时候,会重新构成底层的平衡二叉树,效率有一定影响.
string、vector、list、deque、set 是有序容器。
1.string
string 是basic_string<char> 的实现,在内存中是连续存放的.为了提高效率,都会有保留内存,如string s= "abcd",这时s使用的空间可能就是255,当string再次往s里面添加内容时不会再次分配内存.直到内容>255时才会再次申请内存,因此提高了它的性能.
当内容>255时,string会先分配一个新内存,然后再把内容复制过去,再复制先前的内容.
对string的操作,如果是添加到最后时,一般不需要分配内存,所以性能最快;
如果是对中间或是开始部分操作,如往那里添加元素或是删除元素,或是代替元素,这时需要进行内存复制,性能会降低.
如果删除元素,string一般不会释放它已经分配的内存,为了是下次使用时可以更高效.
由于string会有预保留内存,所以如果大量使用的话,会有内存浪费,这点需要考虑.还有就是删除元素时不释放过多的内存,这也要考虑.
string中内存是在堆中分配的,所以串的长度可以很大,而char[]是在栈中分配的,长度受到可使用的最大栈长度限制.
如果对知道要使用的字符串的最大长度,那么可以使用普通的char[],实现而不必使用string.
string用在串长度不可知的情况或是变化很大的情况.
如果string已经经历了多次添加删除,现在的尺寸比最大的尺寸要小很多,想减少string使用的大小,可以使用:
string s = "abcdefg";
string y(s); // 因为再次分配内存时,y只会分配与s中内容大一点的内存,所以浪费不会很大
s.swap(y); // 减少s使用的内存
如果内存够多的话就不用考虑这个了。
capacity是查看现在使用内存的函数,
大家可以试试看string分配一个一串后的capacity返回值,还有其它操作后的返回值。
2.vector
vector就是动态数组.它也是在堆中分配内存,元素连续存放,有保留内存,如果减少大小后内存也不会释放.如果新值>当前大小时才会再分配内存.
它拥有一段连续的内存空间,并且起始地址不变,因此它能非常好的支持随即存取,即[]操作符,但由于它的内存空间是连续的,所以在中间进行插入和删除会造成内存块的拷贝,另外,当该数组后的内存空间不够时,需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。
对最后元素操作最快(在后面添加删除最快 ), 此时一般不需要移动内存,只有保留内存不够时才需要;
对中间和开始处进行添加删除元素操作需要移动内存,如果你的元素是结构或是类,那么移动的同时还会进行构造和析构操作,所以性能不高 (最好将结构或类的指针放入vector中,而不是结构或类本身,这样可以避免移动时的构造与析构)。
访问方面,对任何元素的访问都是O(1),也就是是常数的,所以vector常用来保存需要经常进行随机访问的内容,并且不需要经常对中间元素进行添加删除操作.
相比较可以看到vector的属性与string差不多,同样可以使用capacity看当前保留的内存,使用swap来减少它使用的内存.
总结
需要经常随机访问请用vector。
3.list
list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随即存取变的非常没有效率,因此它没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除和插入。
list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存.
list在哪里添加删除元素性能都很高,不需要移动内存,当然也不需要对每个元素都进行构造与析构了,所以常用来做随机操作容器.
但是访问list里面的元素时就开始和最后访问最快
访问其它元素都是O(n) ,所以如果需要经常随机访问的话,还是使用其它的好
总结
如果你喜欢经常添加删除大对象的话,那么请使用list;
要保存的对象不大,构造与析构操作不复杂,那么可以使用vector代替;
list<指针>完全是性能最低的做法,这种情况下还是使用vector<指针>好,因为指针没有构造与析构,也不占用很大内存。
4.deque
deque是一个双端队列(double-ended queue),也是在堆中保存内容的.它的保存形式如下:
[堆1]
...
[堆2]
...
[堆3]
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品,不过确实也是如此;
deque可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度;
它支持[]操作符,也就是支持随即存取,可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度,和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。
分享到:
相关推荐
c++ STL容器使用代码,方便学习 vector string deque queue list set map multiset multimap 容器的API使用方法等
详细介绍标准库STL中的容器:vector、list、forward_list、deque、string、array,讲解常用函数,并举例说明常见的用法和原理。
本例程提供了C++的STL常用数据结构及其算法的使用范例,比如vector、string、list、forward_list、deque、queue、stack、map、set、multimap、multiset、tuple、bitset的使用范例,以及algorithm常….zip
第17章 string基本字符序列容器 243 17.1 string技术原理 243 17.2 string应用基础 258 17.3 本章小结 264 第18章 stack堆栈容器 265 18.1 stack技术原理 265 18.2 stack应用基础 266 18.3 本章小结...
标准STL序列容器:vector、string、deque和list。 标准STL关联容器:set、multiset、map和multimap。
介绍STL设计原理和使用 STL概览 迭代器 迭代器适配器 容器 序列式容器-vector、list、deque、string 关联式容器-map、set、multimap、multiset 算法和函数对象 函数对象适配器 STL使用注意事项
组成的库来说提供了更好...在C++标准中,STL被组织为下面的几个头文件:<string>、<vector>、<list>、<deque>、、、、、、、、、和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。
组成的库来说提供了更好...在C++标准中,STL被组织为下面的几个头文件:<string>、<vector>、<list>、<deque>、、、、、、、、、和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。
第17章 string基本字符序列容器 243 17.1 string技术原理 243 17.2 string应用基础 258 17.3 本章小结 264 第18章 stack堆栈容器 265 18.1 stack技术原理 265 18.2 stack应用基础 266 18.3 本章小结...
VC6.0中STL库的BUG修复补丁,一共修复了9个头文件,包括deque、fstream、list、sstream、string、vector、xmemory、xstring和xtree。 直接覆盖到相关头文件所在目录下即可,如:X:\Program Files\Microsoft Visual ...
组成的库来说提供了更好...在C++标准中,STL被组织为下面的几个头文件:<string>、<vector>、<list>、<deque>、、、、、、、、、和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。
第17章 string基本字符序列容器 243 17.1 string技术原理 243 17.2 string应用基础 258 17.3 本章小结 264 第18章 stack堆栈容器 265 18.1 stack技术原理 265 18.2 stack应用基础 266 18.3 本章小结...
6.7 其它STL容器 57 6.7.1 HashTable 59 6.7.2 引用计数 59 6.8 各种容器的运用时机 61 6.8.1 各种容器的使用时机 61 7 STL迭代器 64 7.1 迭代器头文件 64 7.2 迭代器类型 64 7.2.1 Input迭代器 64 7.2.2 Output迭代...
# 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 #...
10.2.1 STL的string 86 10.2.2Vector容器 90 10.2.3Deque容器 96 10.2.4stack容器 101 10.2.5Queue容器 103 10.2.6List容器 105 10.2.7优先级队列priority_queue 110 10.2.8Set和multiset容器 111 10.2.9Map和...
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 位集容器 #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> //复数类 #include <cstdio> #include <cstdlib> #...
1-3-2 在派生类中实现类的基本函数,................... _ ............... 29 1-3-3 内联函数技术,........ ................................... 30 3133 ..... .. .. .. .. .. .. .. .. .. .. .. .. .....
STL本例程提供了C++的STL常用数据结构及其算法的使用范例,为面试笔试编程题提供便利