STL顺序容器详解

int32位 posted @ Nov 01, 2013 12:53:28 PM in c/cpp , 2360 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

STL中定义了三种顺序容器类型,分别是vector, list, deque(双向队列),它们都是线性表,区别在于操作和作用于各种操作的开销上。另外STL还提供了三种容器适配器,分别是stack,queue,priority_queue,它们都是deque的重新封装。下面将分别介绍三种顺序容器,包括它们的性能分析和实现方式。注意本文不是讲解容器的使用方法,具体使用方法可以,可以google或者查看文档。

首先是vector,vector的实现方式是动态数组。显然既然是数组,那所有元素必然是连续存储的。vector主要靠不断维护三个指针(迭代器,vector中的迭代器本质就是指针,参考我的另一篇博客:浅谈cpp中vector中的迭代器来工作的,它们分别是:_M_start, _M_finish, _M_end_of_storage 。_M_start指向第一个元素,_M_finish指向最后一个元素的下一个位置,即哨兵。_M_end_of_storage指向当前已分配地址的最后一个单元。其他两个都容易理解,主要看看_M_end_of_storage,为什么会有这个指针呢?这是因为vector为了减少分配内存的次数,会预先分配比已容纳元素更大的空间。在插入元素时,如果当前不够空间,则会重新分配内存,一般为原来空间的2倍关系分配。注意由于vector必须是连续存储,当重新分配内存时,就会破坏原来的连续性(谁能够保证一定在原来的位置的末端分配呢?),因此重新分配内存时开销是巨大的,首先需要分配足够的内存,然后要把原来的元素逐一拷贝到新分配的内存上,然后还需要释放掉原来已经不需要的内存。如果存储的元素都是基本数据类型还好点,如果是类,则无论是类的拷贝还是调用析构函数释放内存,开销都可能很大。因此为了提高性能,vector总是尽一切可能减少内存分配次数,而同时又要兼顾不能过多分配内存造成空间浪费。注意这三个指针均是动态变化的,会随着容器的变化而自动更新,当调用begin()方法时,其实返回的正是_M_start,而end()方法返回的是_M_finish,当计算capacity时,就需要用到_M_end_of_storage。

    下面讨论vector的性能。首先访问,由于本质是数组,而数组本身是支持随机访问的,因此访问元素开销很小,O(1)的时间完成,比如返回v[n],则只需要返回 *(begin() + n)即可。再看看插入元素,如果在尾部追加元素,如果已分配的内存还足够大,则只需在尾部追加即可,即*_M_finish++ = new_item; 如果_M_finish已移到_M_end_of_storage,则表示已分配内存不足,需要重新分配,这个开销很大,前面已经解释。注意,虽然在尾部追加元素时遇到分配内存时开销巨大,但这种情况往往很少发生,因为大多数情况,内存都是足够的。如果需要在最前面添加元素,则不仅需要考虑内存问题,还需要移动元素,这个开销更大,因此vector不直接提供push_front方法,如果确实需要这样的操作,可以使用insert方法实现。但使用之前,一定要想想,真的有这个必要吗?你考虑了其中的开销吗?如果有100W个元素,需要移动100W次,你考虑过这样的成本吗?有没有其他的容器可供选择呢?删除元素和插入元素类似,只是不用考虑内存问题,当移除最后一个元素时,只需移动_M_finish指针并释放掉删除的元素即可(调用元素的析构函数),而移除中间元素,需要移动元素,O(n)的时间复杂度)。

    因此总结下,vector是连续存储的,适合随机访问,适合在尾部增删操作元素(这种情况,性能甚至优于list,因为list追加元素每次都需要分配一个元素节点的内存,而vector预先分配好了),但不适合在中间进行增删操作。

接下来讨论list,list实现方式是环形双向链表,学过数据结构的一定非常熟悉了,每个节点不仅保存着元素(data),还分别有两个指针(prev,next)分别指向前一个节点和后一个节点,而最后一个节点的next指向第一个节点,第一个节点的prev指向最后一个节点。节点每次都是动态分配的,即每增加一个节点,需要new一个。存储方式显然不是连续的。节点定义如下:

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};

 

不难看出,节点和我们数据结构上的节点定义类似,只不过_List_node_base没有data,然后_List_node继承并添加了data,这样的目的是为了使移动和迭代器分离。迭代器不再是vector中简单的指针,而是一个相对复杂的struct,不过我们仍然可以看作是指向节点指针的指针。由于本质是一个双向链表,因此只需要一个指针就可以访问所有元素,list中是_M_node,它指向最后一个节点。那第一个节点就是_M_node->_M_next。因此begin()方法返回_M_node->_M_next, end()方法返回_M_node,当_M_node->_M_next == _M_node时,即_M_node指向自己时,说明链表为空。list正是通过不断维护_M_node这个节点指针来进行各种操作的。另外还有两个指针,分别是_M_put_node 和_M_put_get,这两个指针是临时指针,主要用于新建指针或删除指针时使用。原理就是这样,下面讨论性能:

首先是访问节点,访问最后一个节点或者第一个节点不需要移动指针,即最后一个节点返回_M_node -> _M_data即可,而第一个节点,只需要返回_M_node_->_M_next->_M_data,因此开销很小。但要访问中间节点时就必须通过移动节点了,至于向前还是向后移动,取决于节点的位置。因此list访问节点的时间复杂度是O(n),相对于vector来说性能下降,因此list没有实现[ ]运算符重载。而插入和删除指定位置的节点,只需要修改指针,而不需要移动指针,性能比vector大大提高。

总结一下,list本质就是双向环形链表,不支持随机访问,插入删除操作开销小。另外,由于每次加入新节点时都需要分配内存,然后拷贝元素,如果是在尾部操作元素,则性能反而比vector要低。

最后剩下deque了,deque可以大致认为是vector和list的混合体。如果学过操作系统内存管理,那么就很容易理解了。vector类似于分区存储管理方式,list类似链式存储方式,而deque则类似于分页式存储管理方式(当然由于deque是整用整取,因此不存在内部碎片问题)。deque就像是分页式存储,首先需要一个map表(相当于页表),存储各个node的指针,每个node都是一个连续的缓冲区,用于实际保存元素,并且还有一些预留空间。需要查找某一个元素时,首先需要计算这个元素处于哪个node缓冲区,然后计算offset从该缓冲区中定位。逻辑上看起来deque也是连续存储的,但事实是由一段段连续的空间组合起来的。deque上的迭代器主要依靠_M_cur,_M_first,_M_last,_M_node四个指针来操作,_M_cur指向当前元素,_M_first指向缓冲区头,_M_last指向缓冲区尾,_M_node指向map表,为了逻辑上看起来是连续的,deque迭代器实现了各种运算符重载, 比如++ / + / --/ -等,虽然++看起来简单,实际需要一些计算,如果_M_cur所在缓冲区还有元素,则直接移动_M_cur即可,若移到该缓冲区尾部,则需要找到下一个缓冲区,然后指向第一个元素。其他操作类似。而要访问任意一个位置的元素时,需要先计算该元素在哪个缓冲区,然后计算offset偏移量找到该元素。由于已经实现了+ -操作,则只需要简单调用*(begin() + n)即可。这就非常类似vector了。因此deque逻辑上实现了和vetor一样的随机访问,时间复杂度也是O(1),不过相对于vector,由于需要一些计算,效率上有点损失,不过这可以忽略不计。下面看看性能方面。

首先访问,上面已经说了,逻辑上支持随机访问。插入元素到指定位置,所在缓冲区还有预留空间,直接插入,并且该缓冲区需要移动元素,这比vector效率大大提高,因为不需要移动整个列表,而只是所在的缓冲区node。而如果所有缓冲区都满了,需要重新分配一个缓冲区,并把新元素放到新的缓冲区中,不需要额外的拷贝操作,只需修改map即可。如果只需要在头尾新增元素,尾部类似vector,看看还有没有预留空间,首部的话也类似,看看前面有没有预留空间,没有再分配一个缓冲区。因此deque在首部增删操作优于vector。

总结一下,deque可以看作是vector和list的折中方案,逻辑上实现了随机访问,在首尾操作开销很小。因此如果既要随机访问,又要各种插入删除操作,deque是一种不错的选择。

注意所有容器存储的都是原来元素的副本,而不是本身,因此不支持复制和赋值的元素类型不能放入容器中,比如IO类型对象就不能放入容器中,数组也不应该放入数组中,因此数组不支持直接赋值运算,即int a[5];int b[5] = a是非法的如果容器放入的元素类型拷贝和析构开销都比较大,则应该考虑下放入元素的指针或许更好。

只有知道容器的内部实现原理,才能真正明智的选择容器的类型。

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter