Question

STL中vector，list，deque和map的区别

Answer 1

　　在STL中基本容器有: string、vector、list、deque、set、map

　　set 和map都是无序的保存元素,只能通过它提供的接口对里面的元素进行访问

　　set:集合, 用来判断某一个元素是不是在一个组里面,使用的比较少
　　map:映射,相当于字典,把一个值映射成另一个值,如果想创建字典的话使用它好了
　　底层采用的是树型结构,多数使用平衡二叉树实现,查找某一值是常数时间,遍历起来效果也不错, 只是每次插入值的时候,会重新构成底层的平衡二叉树,效率有一定影响.

　　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。