|
在stl中提供了vector, list,deque几种可当作列表使用的数据结构,他们都是动态增长的，在这三者之中选择的准则主要是关注插入特性以及对元素的后续访问要求。 vector表示一段连续的内存区域每个元素被顺序存储在这段内存中。对vector 的随机访问效率很高 。但是在任意位置而不是在vector 末尾插人元素则效率很低，因为它需要把待插入元素右边的每个元素都拷贝一遍。类似地删除任意一个而不是vector的最后一个元素效率同样很低,简而言之,删除非末尾元素效率比较低 deque也表示一段连续的内存区域但是与vector 不同的是它支持高效地在其首部插入和删除元素它通过两级数组结构来实现一级表示实际的容器第二级指向容器的首和尾 list表示非连续的内存区域并通过一对指向首尾元素的指针双向链接起来从而允许向前和向后两个方向进行遍历在list 的任意位置插入和删除元素的效率都很高指针必须被重新赋值但是不需要用拷贝元素来实现移动，另一方面它对随机访问的支持并不好访问一个元素需要遍历中间的元素另外每个元素还有两个指针的额外空间开销 对这几种容器类型选择的一些准则如果我们需要随机访问一个容器则vector 要比list 好得多 这几个标准容器类和数据结构对应关系vector => 数组、list => 链表、deque => 队列 实际上对于小的对象vector 在实践中比list效率更高 容量是指在容器下一次需要增长自己之前能够被加入到容器中的元素的总数容量只与 长度size 是指容器当前拥有元素的个数为了获得容器的当前长度我们调用它的size()操作 vector 的动态自我增长越频繁元素插入的开销就越大。一种解决方案是当vector 的开销变得非常大时把vector 转换成list 另一种经常使用的方案是通过指针间接存储复杂的类对象.reserve()操作允许程序员将容器的容量设置成一个显式指定的值，但通常会导致性能退化 vector 类似于数组的存储结构，线性存储，只是大小可以根据需要扩大，不过开销比较大，通常情况下如果涉及到比较少的插入，删除操作时候用它比较好 vector是序列容器,内存分配时占用连续空间,因为采用的是随机迭代器,所以得到某一位置的值非常快 但是插入和删除比较慢,因为涉及到大块内存的赋值粘贴. |