【STL源码剖析】系列四：序列式容器--vector

发表于 2023-10-19 更新于 2024-04-20 分类于 STL源码剖析阅读次数：本文字数： 1.2k 阅读时长 ≈ 4 分钟

前言

vector是STL中最常用的一种关联式容器，其对应的数据结构是采用顺序存储结构的线性表。

本篇主要内容：
1.vector迭代器介绍；
2.vector的底层存储结构和内存管理方式；
3.vector的一些常用操作实现解析，比如insert：

vector

概述

vector的数据安排和操作方式与array非常类似，均是采用一块连续的存储空间排列数据元素。

二者的差别在于空间的灵活性：
array是静态空间，一旦申请了就不能改变。如果想要更换空间，就需要用户申请一块新的空间，然后将旧空间中的元素全部移动到新申请的空间，最后把原来的空间释放。
vector是动态空间，随着元素加入，内部机制会自行扩充空间以容纳新元素。

vector实现的关键技术就是对于空间大小的控制以及重新申请空间时的雄数据移动效率。

vector源代码

书上列举了vector的实现源代码摘要，详情参看书中内容。

vector的迭代器

vector是一块连续线性空间，因此支持随机访问，又因为普通指针能够满足vector的迭代器要求，因此vector内部将原生指针声明为迭代器类型：

// 定义vector的迭代器
vector<int>::iterator ivite;
vector<Shape>::iterator svite;

// 实际上ivite的类型就是 int *，svite的类型就是 Shape *

vector的数据结构

vector的数据结构就是一段线性连续空间。以两个迭代器start和finish指向已经被使用的范围，以迭代器end_of_storage指向整块空间的尾端。

这也表明vector的实际大小要比已经使用的大小要大，这是为了以后添加元素时尽量不用重新申请空间。因此实际大小称为capacity，已经使用的大小称为size。

利用上述三个迭代器，很容易提供首尾标志、size、capacity、是否为空等接口：

vector的构造与内存管理

vector默认情况下以alloc作为空间配置器，基于此定义了一个data_allocator，以元素大小为申请空间单位。

对于默认配置器alloc的allocate函数来说，是以字节为单位申请n个字节的内存；而外层的simple_alloc提供了一层包装，以元素类型为单位申请 sizeof(value_type) * n个字节的内存。

以其中一个构造函数为例：指定空间大小（以元素为单位）和初始值

经过重重传递调用，最终：1.调用分配器的allocate(n)申请n个元素空间；2.调用uninitialized_fill_n(first, n, x)函数，即使用x对象为[first, first + n)迭代器范围内的空间进行初始化。这里会根据迭代器指向的元素类型是否为POD来决定使用高阶算法fill_n还是不断为每一个位置调用construc来完成构造任务。