STL源码剖析 4、序列式容器

阅读量：333 次

发布时间：2019-03-03

本文共 3001 字，大约阅读时间需要 10 分钟。

容器的分类

分为序列式容器和关联式容器

vector

vector与array

两者唯一差别在于空间的运用的灵活性，array是静态空间，一旦配置了就不能改变。vector是动态空间，随着新元素的加入，它的内部机制会自行扩充空间以容纳新元素。

vector源代码

见书p116

使用vector必须包括<vector>，但vector实现于更底层的<stl_vector.h>

vector迭代器

vector维护的是连续线性空间，所以不论元素型别，普通指针都可以满足作为vector的迭代器的所有必要条件（如operator*、operator->、operator++等）

vector的数据结构

在这里插入图片描述

vector的构造与内存管理：construct、push_back

具体函数见书4.2.5

vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位，于是data_allocator::allocate(n)配置n个元素

template
   
    class vector{   protected:	//simple_alloc是接口，见第二章	typedef simple_alloc
    
      data_allocator;	...	};

vector已满时插入：

●不是简单的在后面插入，所以插入后原迭代器可能失效

1.重新配置空间：新空间大小const size_type len = old_size != 0 ? 2 * old_size : 1

2.拷贝原数据

3.销毁原空间

●拷贝时要注意commit or rollback（try catch实现，如果捕捉到异常就析构元素且删除空间）

vector的元素操作：pop_back,erase,clear,insert

见书4.2.6

list

list 概述

缺点：相比于vector的连续线性空间，list更为复杂。

优点：不过好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此对空间运用很精准，不浪费。

list 的节点

在这里插入图片描述

list的迭代器

特点：

●不能和vector一样用普通指针作为迭代器，因为及诶点不保证在储存空间中连续存在

●list迭代器必须能指向list的节点，并可以递增（下一节点）、递减、取值等

●STL list是双向链表，迭代器为Bidirectional Iterators（双向，逐一）

●插入和接合（splice）都不会造成原迭代器失效，和vector不同

代码见书4.3.3

list的数据结构

SGI list是环状双向链表

●所以只需一个指针就可以表示整个环状双向链表（所有节点都可以表示）

●使用空白节点满足满足前闭后开的要求

list的构造与内存管理

在这里插入图片描述

List的构造函数：

push_back：

list的元素操作

见书4.3.6，

注意：

●merge、reverse、sort都调用了transfer

●STL sort只接受Ramdon迭代器，所以list的sort需要自己实现

deque

其余见书4.4

概述

deque与vector区别：

●vector是单向开口的连续线性空间，deque则是一种双向开口（头尾分别插入和删除）的“连续”线性空间

●deque允许常数时间对头端进行元素的插入或移除

●deque动态以分段连续空间组合而成，随时可以增加新的空间并链接，不用像vector满了要重新配置

●deque迭代器不是普通指针，代码很复杂，效率比vector差很多，所以尽量用vector。（deque的sort是复制到vector中sort再复制回来）

deque的中控器

概述：deque的连续空间是假象，是由一段一段的定量连续空间构成，随时可以增加新的空间

stack

概述

stack是一种先进后出的数据结构

stack定义

用deque（list也是双向开口，也可以用list）为底部结构并封闭其头端开口，便形成了一个stack。

stack是一种配接器，即修改某物接口，形成另一种样子

具体见书4.5.2

stack没有迭代器

stack不提供走访功能，不提供迭代器

stack的pop为什么不返回值？

●效率：当一个栈顶元素被弹出后，我们不得不返回这个元素的值（而不是引用），因此接收这个值的一方Object obj必然发生一次实例化。

而top函数不弹出元素，因此可以返回引用，也就不必发生实例化。

所以为了兼顾效率，pop不返回任何数据。

●异常安全：当我们执行Object obj=stack.pop() 时，Object的构造函数被调用，而这里是可以反生异常的，

假设这时候发生异常，丢生的栈顶元素就回不去了。

queue

概述

queue是一种先进先出的数据结构

queue定义

用deque（list也是双向开口，也可以用list）为底部结构并封闭其头端开口，便形成了一个stack

queue是一种配接器，即修改某物接口，形成另一种样子

具体见书4.6.2

queue没有迭代器

queue不提供走访功能，不提供迭代器

heap

heap概述

heap不属于STL容器组件，由priority queue调用

heap算法

代码见书4.7.2

push_heap

pop_heap

sort_heap

make_heap

#include
   
    #include 
    
     #include 
     
      using namespace std;int main(){   	vector
      
       ivec{    0,1,2,3,4,8,9,3,5 };	make_heap(ivec.begin(), ivec.end());	//9 5 8 3 4 0 2 3 1		//push_heap()要先将元素放入vector	ivec.push_back(7);	push_heap(ivec.begin(), ivec.end());	//9 7 8 3 5 0 2 3 1 4		pop_heap(ivec.begin(), ivec.end());		//ivec.back()为9，要再pop_back()一次	ivec.pop_back();				sort_heap(ivec.begin(), ivec.end());	//0 1 2 3 3 4 5 7 8}