STL常见容器实现原理——vector,list等

Array

连续存储结构,每个元素在内存上是连续的

array是一个固定大小的顺序容器,不能动态改变大小,它的大小在定义后就不能被改变。由于array具有固定的大小,它不支持添加和删除元素或改变容器大小等其他容器拥有的操作。在定义一个array容器的时候必须指定大小。

Defined in header :
<array>
template<class T, std::size_t N> struct array;

内存分配策略

在内存分配策略上,array也与C-style数组类似。编译器在哪里为array分配内存,取决于array定义的位置和方式。

  • 若作为函数的局部对象,则将从栈上获得内存,与之对比是的vector,vector底层数据结构是动态数组,从自由存储区上分配内存:
  • 若使用new操作符分配内存,则是在自由存储区上分配内存。
  • 若作为全局变量或局部静态变量,则是在全局/静态存储区上分配的内存。

Array使用优劣

(1)array比数组更安全。它提供了opeartor[]与at()成员函数,后者将进行数组越界检查。   

(2)与其他容器相似,array也有自己的迭代器,因此array能够更好地与标准算法库结合起来。

(3)通过array::swap函数,可以实现线性时间内的两个数组内容的交换。

另外,不像C-style数组,array容器类型的名称不会自动转换为指针。对于C++程序员来说,array要比C-style数组更好用。

vector

vector的底层数据结构是动态数组,因此,vector的数据安排以及操作方式与std::array十很相似,它们间的唯一差别在于对空间的运用灵活性上。array为静态数组,有着静态数组最大的缺点:每次只能分配一定大小的存储空间,当有新元素插入时,要经历 “找到更大的内存空间”->“把数据复制到新空间” ->“销毁旧空间” 三部曲, 对于std::array而言,这种空间管理的任务压在使用它的用户身上,用户必须把握好数据的数量,尽量在第一次分配时就给数据分配合理的空间(这有时很难做到),以防止“三部曲”带来的代价,而数据溢出也是静态数组使用者需要注意的问题。

而vector用户不需要亲自处理空间运用问题。vector是动态空间,随着新元素的插入,旧存储空间不够用时,vector内部机制会自行扩充空间以容纳新元素,当然,这种空间扩充大部分情况下(几乎是)也逃脱不了“三部曲”,只是不需要用户自己处理,而且vector处理得更加安全高效。vector的实现技术关键就在于对其大小的控制以及重新配置时数据移动效率。

标准库的实现者使用了这样的内存分配策略:以最小的代价连续存储元素。为了使vector容器实现快速的内存分配,其实际分配的容量要比当前所需的空间多一些(预留空间),vector容器预留了这些额外的存储区用于存放添加的新元素,于是不必为每个新元素进行一次内存分配。当继续向容器中加入元素导致备用空间被用光(超过了容量 capacity),此时再加入元素时vector的内存管理机制便会扩充容量至两倍,如果两倍容量仍不足,就扩张至足够大的容量。容量扩张必须经历“重新配置、元素移动、释放原空间”这个浩大的工程。按照《STL源码剖析》中提供的vector源码,vector的内存配置原则为:

  • 如果vector原大小为0,则配置1,也即一个元素的大小。
  • 如果原大小不为0,则配置原大小的两倍。

当然,vector的每种实现都可以自由地选择自己的内存分配策略,分配多少内存取决于其实现方式,不同的库采用不同的分配策略。

迭代器失效问题

  (1)vector管理的是连续的内存空间,在容器中插入(或删除)元素时,插入(或删除)点后面的所有元素都需要向后(或向前)移动一个位置,指向发生移动的元素的迭代器都失效。这里以插入操作示例:

  (2)随着元素的插入,原来分配的连续内存空间已经不够且无法在原地拓展新的内存空间,整个容器会被copy到另外一块内存上,此时指向原来容器元素的所有迭代器通通失效。

(3)删除元素后,指向被删除元素的迭代器失效,这是显而易见的。

vector使用优劣

优点:

(1) 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组进行动态操作。通常体现在push_back() pop_back()

(2) 随机访问方便,即支持[ ]操作符和vector.at()

(3) 节省空间。

缺点:

(1) 在内部进行插入删除操作效率低。

(2) 只能在vector的最后进行push和pop,不能在vector的头进行push和pop。

(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放

list

底层数据结构

list同样是一个模板类,它底层数据结构为双向循环链表。因此,它支持任意位置常数时间的插入/删除操作,不支持快速随机访问。

迭代器类型:

list的迭代器具备前移、后移的能力,所以list提供的是Bidirectional iterator(双向迭代器)。由于采用的是双向迭代器,自然也很方便在指定元素之前插入新节点,所以list很正常地提供了insert()操作与push_back()/pop_back()操作。

内存分配策略:

list的空间配置策略,自然是像我们普通双向链表那样,有多少元素申请多少内存。它不像vector那样需要预留空间供新元素的分配,也不会因找不到连续的空间而引起整个容器的内存迁移。

迭代器失效问题

list 有一个重要性质:插入操作(insert)与接合操作(splice)都不会造成原有的list迭代器失效。这在vector是不成立的,因为vactor的插入可能引起空间的重新配置,导致原来的迭代器全部失效。list的迭代器失效,只会出现在删除的时候,指向删除元素的那个迭代器在删除后失效。

通常来说,forward_list在使用灵活度上比不上list,因为它只能单向迭代元素,且提供的接口没有list多。然而,在内存的使用上,它是比list占优势的。当对内存的要求占首要位置时,应该选择forward_list。

list使用优劣

优点:

  (1) 不使用连续内存完成动态操作。

  (2) 在内部方便的进行插入和删除操作

  (3) 可在两端进行push、pop

缺点:

  (1) 不能进行内部的随机访问,即不支持[ ]操作符和vector.at()

  (2) 相对于verctor占用内存多

deque

底层数据结构:

vector是单向开口的线性连续空间,deque则是一种双向开口的连续数据空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作。当然vector也可以在头尾两端进行操作,但是其头部操作效果奇差,所以标准库没有为vector提供push_front或pop_front操作。与vector类似,deque支持元素的快速随机访问。deque的示意图如下:

现在问题来了:如果deque以数组来实现,如何做到在头部的常数时间插入?如果是采用链表来实现,又如何做到快速随机访问?deque的内部数据结构到底如何?想必你已经猜到了,要实现如上需求,需要由一段一段的连续空间链接起来的数据结构才能满足。

内存分配策略:

deque由一段一段的连续空间所链接而成,一旦需要在deque的前端或尾端增加新空间,便配置一段定量的连续空间,并将该空间串接在deque的头部或尾部。deque复杂的迭代器架构,构建出了所有分段连续空间”整体连续“的假象。
既然deque是由一段一段定长的连续空间所构成,就需要有结构来管理这些连续空间。deque采用一块map(非STL中的map)作为主控,map是一块小的连续空间,其中每个元素都是指针,指向一块较大的线性连续空间,称为缓冲区。而缓冲区才是存储deque元素的空间主体。示例图:

map本身也是一块固定大小的连续空间,当缓冲区数量增多,map容不下更多的指针时,deque会寻找一块新的空间来作为map。

deque的迭代器

为了使得这些分段的连续空间看起来像是一个整体,deque的迭代器必须有这样的能力:它必须能够指出分段连续空间在哪里,判断自己所指的位置是否位于某一个缓冲区的边缘,如果位于边缘,则执行operator– 或operator++时要能够自动跳到下一个缓冲区。因此,尽管deque的迭代器也是Ramdon Access Iterator 迭代器,但它的实现要比vector的复杂太多。

迭代器失效问题

  (1)在deque容器首部或者尾部插入元素不会使得任何迭代器失效。

  (2)在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。

  (3)在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

deque使用优劣

deque是在功能上合并了vector和list。

优点:(1) 随机访问方便,即支持[ ]操作符和vector.at()

(2) 在内部方便的进行插入和删除操作

(3) 可在两端进行push、pop

缺点:(1) 占用内存多

Map

Map是关联容器,以键值对的形式进行存储,方便进行查找,关键词起到索引的作用,值则表示与索引相关联的数据,以红黑树的结构实现,插入删除等操作都可以在O(log n)时间内完成

Map基本操作:

1.map a; map;支持多种类型

2.添加数据:

map1.insert(pair<int,string>   (102,"wobeitianjia")); 
map1.insert(map<int,string>::value_type(102,"tianjia"));
map1[102]="string";

3.元素查找:map1.find(key) 返回一个迭代器指向键值为key的元素,如果没有找到,返回指向map尾部的迭代器

4.元素删除:先查找元素,map::iterator it=map1.find(key); 找到之后map1.erase(it);

5.map中的swap函数,交换的是两个容器而不是一个容器中的元素交换

6.sort函数,因为map中key按照升序进行排列的,所以不能使用sort函数

set

Set是关联容器,set中每个元素都只包含一个关键字,set支持高效的关键字查询操作—检查每一个给定的关键字是否在set中,set是以红黑树的平衡二叉检索树结构实现的,支持高效插入删除,插如元素的时候会自动调整二叉树的结构,使得每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值,另外还得保证左子树和右子树的高度相等

平衡二叉检索树使用中序遍历算法,检索效率高于vector,deque,list等容器,另外使用中序遍历可将键值按照从小到大遍历出来

构造set集合的主要目的是为了快速检索,不可直接去修改键值

常用操作:

  1.元素插入:insert

  2.中序遍历:类似vector遍历(用迭代器)

  3.反向遍历:利用反向迭代器reverse_iterator

set<int> s;  
set<int>::reverse_iterator rit; 
for(rit=s.rbegin();rit!=s.rend();rit++)

  4.元素的删除:s.erase(2); s.clear();

  5.元素的检索:find(),若找到,返回该值迭代器的位置,否则返回最后一个元素后面一个位置s.end()

it=s.find(5); 
if(it==s.end()) 
cout<<"not find"<<endl;
else cout<<*it<<endl;

参考:http://www.cnblogs.com/DswCnblog/p/5676017.html