STL源码--序列式容器

时间:2021-08-02 15:39:20

1. vector:

  vector的内存管理,动态分配内存,不需要程序员来维护存储空间,是与array最大的区别,程序员只需从逻辑上关注代码,而不需要对内部的存储空间的分配和回收分心。首先,vector会分配一个合适的空间给使用者,当不断的产生push_back()等插入操作时,原有空间就不足了,需要增加存储,如果当前的容量小于vector存储的总量,则直接分配下一个位置给新加入的元素,当当前的容量已经达到了vector存储的总量时,则需要重新分配内存。首先vector会从新的内存区申请两倍于当前总量大小的空间,然后将原来的存储的内容复制到新区域的前半段,然后加入新元素,如此,保证相对较少的申请次数,和相对较大的内存空间。注意,一旦引起空间的重新配置,则原指向vector的所有迭代器就都失效了

2.list:

  list类似链表结构,不会浪费存储空间,list是一个双向循环链表,表结构中有个node指向最后一个节点,这样就保证了双向循环链表的各个操作的可用性。list的操作基本和链表操作类似,没有什么特别之处,在此就不在赘述。

3. deque:

  与vector类似,deque也是一段连续的线性空间,与vector的区别在于:

  1). deque是双向开口的,vector是单向开口的。虽然vector也可以在头尾两端操作,但正如第一部分介绍的,在尾端操作时是向后直接添加元素,在前面加元素时,势必要移动大量元素,因此效率极低。

  2). deque没有所谓容量的概念,因为他是动态的增加连续的空间,随时可以增加一段连续空间并链接起来。而不是像vector那样,因空间不足而重新申请空间并复制,再释放原有空间。

  3). deque虽然提供随机访问元素,但是迭代器并不是普通指针,效率相对于vector要差很远,因此,能使用vector尽量使用vector,对deque的排序,为了提高效率,可以将deque复制到vector后,进行排序,然后再复制回deque。

  deque的数据结构比较复制,使用一个map来维护一个指向缓冲区的指针的表,而缓冲区就是真实的连续的存储空间了。因此迭代器的++或--就显的相当麻烦了。

迭代器示意:

  template <class T, class Ref, class Ptr, size_t BufSiz>

  struct __deque_iterator

  {

    ...

    T* cur;  // 指向所指的缓冲区的当前元素

    T* first;  // 指向所指缓冲区的头

    T* last;  // 指向所指缓冲区的尾  

    map_pointer node;  // 指向管控中心

  };

4. stack:

  stack是先进先出的单出口的结构,底层是以deque实现的,因此stack一般不称为容器,而被称为适配器。另外,stack只能访问栈顶元素,因此不能遍历,没有迭代器。

5. queue:

  queue是先进后出的两个出口的结构,底层页是deque实现的,因此queue也是一种适配器,只能进队和出队,不能遍历队列中元素,不具有迭代器。

6. heap:

  heap不算是STL容器组件,但是扮演着优先队列的助手。heap底层是vector,vector元素类似数组实现二叉树的结构,形成一个完全二叉树,可以是大根堆,也可以是小根堆。heap是特殊的排列规则,因此也没有迭代器。

7. priority_queue:

  默认情况下,priority_queue底层是max_heap实现完成的,这种以底部容器实现的,叫做适配器。priority_queue也和queue类似,只能在顶端进出,因此不能遍历,也没有迭代器。

8. slist:

  slist是一个单向链表。它与list的区别主要有:slist的迭代器属于单向型的Forward Iterator, list的迭代器属于双向型的Bidirectional Iterator。slist消耗空间更小,某些操作更快,是另一种优势。slist的插入操作,是极其费事的,因为一般插入操作都是在指定元素前面插入,而slist是单向的,要找到这个元素位置,需要从头遍历,因此,插入是一个缺点。