《容器的优缺点及各种容器介绍》由会员分享，可在线阅读，更多相关《容器的优缺点及各种容器介绍（11页珍藏版）》请在金锄头文库上搜索。
1、Standard Template Language 提供了三个最基本的容器： vector,list,dequevector,deque,list 区别vector表示一段连续的内存区域每个元素被顺序存储在这段内存中对 vector 的随机访问比如先访问元素 5 然后访问 15 然后再访问 7 等等效率很高，因为每次访问离vector 起始处的位移都是固定的。但是在任意位置而不是在 vector 末尾插人元素则效率很低 ，因为它需要把待插入元素右边的每个元素都拷贝一遍。类似地删除任意一个而不是 vector 的最后一个元素效率同样很低。因为待删除元素右边的每个元素都必须被复制一遍这种代价对于
2、大型的复杂的类对象来说尤其大。deque一个 deque 也表示一段连续的内存区域但是与 vector 不同的是它支持高效地在其首部插入和删除元素它通过两级数组结构来实现一级表示实际的容器第二级指向容器的首和尾listList 表示非连续的内存区域并通过一对指向首尾元素的指针双向链接起来从而允许向前和向后两个方向进行遍历在 list 的任意位置插入和删除元素的效率都很高指针必须被重新赋值但是不需要用拷贝元素来实现移动另一方面它对随机访问的支持并不好，访问一个元素需要遍历中间的元素另外每个元素还有两个指针的额外空间开销 下面是选择顺序容器类型的一些准则 如果我们需要随机访问一个容器则 vecto
3、r 要比 list 好得多 。如果我们已知要存储元素的个数则 vector 又是一个比 list 好的选择。 如果我们需要的不只是在容器两端插入和删除元素则 list 显然要比 vector 好 除非我们需要在容器首部插入和删除元素否则 vector 要比 deque 好1 vector 向量 相当于一个数组在内存中分配 一块连续的内存空间进行存储。支持不指定 vector 大小的存储。STL 内部实现时，首先分配一个非常大的内存空间预备进行存储，即 capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以 vector 可以不指定 vector 即一个
4、连续内存 的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。优点：(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在 push_back() pop_back()(2) 随机访问方便，即支持 操作符和 vector.at()(3) 节省空间。缺点：(1) 在内部进行插入删除操作效率低。(2) 只能在 vector 的最后进行 push 和 pop，不能在 vector 的头进行 push 和pop。(3) 当动态添加的数据超过 vector 默认分配的大小时要进行整体的重新分配、拷贝与释放2 list 双向链表每一个结点都包括一个
5、信息快 Info、一个前驱指针 Pre、一个后驱指针 Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。优点：(1) 不使用连续内存完成动态操作。(2) 在内部方便的进行插入和删除操作(3) 可在两端进行 push、pop缺点：(1) 不能进行内部的随机访问，即不支持 操作符和 vector.at()(2) 相对于 verctor 占用内存多3 deque 双端队列 double-end queuedeque 是在功能上合并了 vector 和 list。优点：(1) 随机访问方便，即支持 操作符和 vector.at()(2) 在内部方便的进行插入
6、和删除操作(3) 可在两端进行 push、pop缺点：(1) 占用内存多使用区别：1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用 vector2 如果你需要大量的插入和删除，而不关心随即存取，则应使用 list3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用 dequevector 和 built-in 数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此 它能非常好的支持随即存取，即操作符，但由于它的内存空间是连续的，所以在中间 进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新 申请一块足够大的内存并进行内存的拷贝。这些都大大影响
7、了 vector 的效率。 list 就是数据结构中的双向链表(根据 sgi stl 源代码)，因此它的内存空间可以是不连续 的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它 没有提供操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除 和插入。 deque 是一个 double-ended queue，它的具体实现不太清楚，但知道它具有以下两个特点： 它支持操作符，也就是支持随即存取，并且和 vector 的效率相差无几，它支持在两端的 操作：push_back,push_front,pop_back,pop_front 等，并且在两端操作上与l
8、ist 的效率 也差不多。 因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面 的原则： 1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用 vector 2、如果你需要大量的插入和删除，而不关心随即存取，则应使用 list 3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。Vector：C+容器模板中的大哥大，就像是一个加强版的队列，之所以这样说，是因为它不但有队列形式的索引，还能动态的添加扩充。特点：把被包含的对象以数组的形式存储，支持索引形式的访问（这种访问速度奇快无比）。但由此也产生了一个问题，由于数据存储形式的固定化，你
9、如果想在他中间部位 insert 对象的话，搞不好会让你吃尽头。因为他在分配空间的时候，可是成块分配的连续空间。Deque:英文“double-ended-queue”。名如其人，这是 C+有序容器中闻名遐迩的双向队列。他在设计之初，就为从两端添加和删除元素做了特殊的优化。同样也支持随即访问，也有类似 vector 的 操作符，但不要因此就把他和 vector混为一潭。特点：从本质上讲，他在分配内存的时候，使用了 MAP 的结构和方法。化整为零，分配了许多小的连续空间，因此，从 deque 两端添加、删除元素是十分方便的。最重要的一点：如果在不知道内存具体需求的时候，使用 deque 绝对是比
10、 vector 好的。List：模板中的 双向链表。设计他的目的可能就是为了在容器中间插入、删除吧，所以有得比有失，他的随机访问速度可不敢恭维。而且没有 操作。特点：随机的插入、删除元素，在速度上占有明显的优势。并且，由于内存分配不连续，他对插入的要求也十分的低。所以在使用大对象的时候，这可是一个不错的选择。“vector 和 deque 的区别主要在于他们底层的实现不同，特别是在插入和删除操作的实现机制不同。对于 vector 来说，不管其大小是多少，在头部插入的效率总是比在尾部插入的效率低。在尾部插入将耗费固定的时间。在头部进行插入时，耗费的时间与 vector 的大小成正比，vector
11、 越大，耗费的时间越多。例如，在一个大小为 1000 的 vector 头部插入一个元素，与在一个大小为 10 的 vector 头部插入一个元素相比，将耗费 100 倍的时间。删除操作的情形也与插入类似。因此，vector 适合于插入和删除操作都在尾部进行的情况。deque 和 vector 不同，不管进行的插入还是删除操作，也不管这些操作时在头部还是尾部进行，算法的效率是固定的。例如：不管deque 的大小是 10，100，还是 1000.deque 在头部和尾部插入删除的时间是一样的。因此要在对于两端进行插入或者删除操作时。deque 要优于 vector。STL 中: string、v
12、ector、list、deque 、set、map 的区别 博客分类： c/c+在 STL 中基本容器有: string、vector、list、deque 、set 、mapset 和 map 都是无序的保存元素,只能通过它提供的接口对里面的元素进行访问set:集合, 用来判断某一个元素是不是在一个组里面, 使用的比较少map:映射 ,相当于字典,把一个值映射成另一个值,如果想创建字典的话使用它好了string、 vector、list、deque、set 是有序容器 1.string string 是 basic_string 的实现,在内存中是连续存放的 .为了提高效率,都会有保留内存,
13、如 string s= abcd,这时 s 使用的空间可能就是 255, 当 string 再次往 s 里面添加内容时不会再次分配内存.直到内容255 时才会再次申请内存,因此提高了它的性能.当内容255 时,string 会先分配一个新内存, 然后再把内容复制过去 ,再复制先前的内容.对 string 的操作,如果是添加到最后时 ,一般不需要分配内存,所以性能最快;如果是对中间或是开始部分操作,如往那里添加元素或是删除元素,或是代替元素, 这时需要进行内存复制,性能会降低.如果删除元素,string 一般不会释放它已经分配的内存,为了是下次使用时可以更高效 .由于 string 会有预保留内
14、存,所以如果大量使用的话, 会有内存浪费,这点需要考虑.还有就是删除元素时不释放过多的内存,这也要考虑.string 中内存是在堆中分配的,所以串的长度可以很大, 而 char是在栈中分配的,长度受到可使用的最大栈长度限制.如果对知道要使用的字符串的最大长度,那么可以使用普通的 char,实现而不必使用string.string 用在串长度不可知的情况或是变化很大的情况.如果 string 已经经历了多次添加删除,现在的尺寸比最大的尺寸要小很多,想减少 string 使用的大小,可以使用:string s = abcdefg;string y(s); / 因为再次分配内存时,y 只会分配与 s
15、 中内容大一点的内存 ,所以浪费不会很大s.swap(y); / 减少 s 使用的内存如果内存够多的话就不用考虑这个了 capacity 是查看现在使用内存的函数大家可以试试看 string 分配一个一串后的 capacity 返回值,还有其它操作后的返回值2.vector vector 就是动态数组.它也是在堆中分配内存,元素连续存放,有保留内存, 如果减少大小后内存也不会释放.如果新值当前大小时才会再分配内存 对最后元素操作最快(在后面添加删除最快 ), 此时一般不需要移动内存 ,只有保留内存不够时才需要对中间和开始处进行添加删除元素操作需要移动内存,如果你的元素是结构或是类,那么移动的同
16、时还会进行构造和析构操作，所以性能不高 （最好将结构或类的指针放入 vector中，而不是结构或类本身，这样可以避免移动时的构造与析构)。 访问方面,对任何元素的访问都是 O(1),也就是是常数的,所以 vector 常用来保存需要经常进行随机访问的内容,并且不需要经常对中间元素进行添加删除操作.相比较可以看到 vector 的属性与 string 差不多, 同样可以使用 capacity 看当前保留的内存,使用 swap 来减少它使用的内存.总结需要经常随机访问请用 vector 3.list list 就是链表 ,元素也是在堆中存放 ,每个元素都是放在一块内存中 list 没有空间预留习惯,所以每分配一个元素都会从内存中分配, 每删除一个元素都会释放它占用的内存,这与上面不同,可要看好了list 在哪里添加删除元素性能都很高, 不需要移动内存,当然也不需要对每个元素都进行构造与析构了,所以常用来做随机操作容器.但是访问 list 里面
