容器的优缺点及各种容器介绍.docx

Standard Template Language提供了三个最基本的容器：vector,list,dequevector,deque,list区别vector表示一段连续的内存区域每个元素被顺序存储在这段内存中对vector的随机访问比如先访问元素5?然后访问15然后再访问7等等效率很高，因为每次访问离vector起始处的位移都是固定的。但是在任意位置而不是在vector末尾插人元素则效率很低?，因为它需要把待插入元素右边的每个元素都拷贝一遍。类似地删除任意一个而不是vector?的最后一个元素效率同样很低。因为待删除元素右边的每个元素都必须被复制一遍这种代价对于大型的复杂的类对象来说尤其大。deque一个deque?也表示一段连续的内存区域但是与vector不同的是它支持高效地在其首部插入和删除元素它通过两级数组结构来实现一级表示实际的容器第二级指向容器的首和尾listList表示非连续的内存区域并通过一对指向首尾元素的指针双向链接起来从而允许向前和向后两个方向进行遍历在list的任意位置插入和删除元素的效率都很高指针必须被重新赋值但是不需要用拷贝元素来实现移动另一方面它对随机访问的支持并不好，访问一个元素需要遍历中间的元素另外每个元素还有两个指针的额外空间开销??下面是选择顺序容器类型的一些准则???如果我们需要随机访问一个容器则vector要比list好得多?。?如果我们已知要存储元素的个数则vector?又是一个比list好的选择。??如果我们需要的不只是在容器两端插入和删除元素则list显然要比vector好???除非我们需要在容器首部插入和删除元素否则vector要比deque好1?vector向量?相当于一个数组在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。优点：(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在push_back() pop_back()(2) 随机访问方便，即支持[ ]操作符和vector.at()(3) 节省空间。缺点：(1) 在内部进行插入删除操作效率低。(2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放2?list双向链表每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。优点：(1) 不使用连续内存完成动态操作。(2) 在内部方便的进行插入和删除操作(3) 可在两端进行push、pop缺点：(1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()(2) 相对于verctor占用内存多3?deque双端队列?double-end queuedeque是在功能上合并了vector和list。优点：(1) 随机访问方便，即支持[ ]操作符和vector.at()(2) 在内部方便的进行插入和删除操作(3) 可在两端进行push、pop缺点：(1) 占用内存多使用区别：1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector2 如果你需要大量的插入和删除，而不关心随即存取，则应使用list3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用dequevector和built-in数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此?它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间?进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新?申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。?list就是数据结构中的双向链表(根据sgi ? stl源代码)，因此它的内存空间可以是不连续?的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它?没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除?和插入。?deque是一个double-ended ? queue，它的具体实现不太清楚，但知道它具有以下两个特点：?它支持[]操作符，也就是支持随即存取，并且和vector的效率相差无几，它支持在两端的?操作：push_back,push_fro