【C++杂货铺】探索vector的底层实现

一、STL

1.1 什么是STL?

STL(standard template libaray-标准模板库)：是C++标准库的一部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。

1.2 STL的版本

• 原始版本：Alexander Stepanov、Meng Lee在惠普实验室完成的版本，本着开源精神，它们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码，无需付费。唯一的条件就是也需要像原始版本一样做开源使用。HP版本是所有STL的祖先。

• P.J版本：由P. J. Plauger开发，继承自HP版本，被微软（Windows Visual C++）采用，不能公开或修改，缺陷：可读性比较低，符号命名比较怪异。

• RW版本：由Rouge Wage公司开发，继承自HP版本。被C++Builder采用，不能公开或修改，可读性一般。

• SGI版本：由Silicon Graphics Computer Systems，Inc公司开发，继承自HP版本。被GCC（Linux）采用，可移植性好，可公开、修改甚至贩卖，从命名风格和编程风格上看，阅读性非常高。建议大家在学习STL的过程中，可以参考这个版本的源代码。

1.3 STL的六大组件

二、vector的介绍及使用

2.1 vector的介绍

• vector 是表示可变大小数组序列容器。

• 就像数组一样，vector 也采用连续的存储空间来存储元素。也就意味着可以采用小标对 vector 的元素进行访问，和数组处理一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

• 本质讲，vector 使用动态分配数组来存储它的元素。当新元素插入时，为了增加存储空间，这个数组需要被重新分配大小。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价较高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。

• vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因此存储空间（容量）比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候实在常数时间复杂度完成的。

• 因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

• 与其它的动态序列容器相比（如：deque、list、forward_list），vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率会比较低。

2.2 vector的使用

vector 学习时一定要学会查看文档：vector的文档介绍，vector 在实际中非常重要，在实际中我们熟悉常用的接口就可以，下面列出了需要我们重点掌握的接口。

2.2.1 vector的定义

构造函数声明	接口说明
vector()	无参构造
vector(size_type n, const value_type& val = value_type())	构造并初始化 n 个 val
vector(const vector& x)	拷贝构造
vector(Inputlterator first, Inputiterator last)	使用迭代器区间进行初始化构造

小Tips：size_type 表示一个无符号整数类型，value_type 是第一个模板参数，也就是要存储的数据类型。使用迭代器区间的构造函数是函数模板，只要是满足 Input 类型的迭代器都可以使用该构造函数。

int TestVector1()
{vector<int> first;                                vector<int> second(4, 100);                       vector<int> third(second.begin(), second.end());  vector<int> fourth(third);                       int myints[] = { 16,2,77,29 };vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\n';return 0;
}

2.2.2 vector iterator

iterator的使用	接口说明
begin + end	获取第一个数据位置的 iterator / const_iterator，获取最后一个数据下一个位置的iterator / const_iterator
rbegin + rend	获取最后一个数据位置的 reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

void PrintVector(const vector<int>& v)
{// const对象使用const迭代器进行遍历打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

2.2.3 vector空间增长问题

容量空间	接口说明
size()	获取数据个数
capacity()	获取容量大小
empty()	判断是否为空
resize(size_type n); resize (size_type n, const value_type& val)	改变 vector 的 size
reserve(size_type n)	改变 vector 的 capacity

• vs 和 g++ 的扩容机制有所不同，vs 下 capacity 是按照 1.5 倍增长的，g++ 是按照 2 倍增长的。vs 是 PJ 版本 STL，g++ 是 SGI 版本 STL。

• reserve 只负责开辟空间，如果确定知道需要多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。

• resize 在开空间的同时还会进行初始化，影响 成员变量 _size。

void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

VS 下的结果：

Linux 下的结果：

小Tips：如果已经确定 vector 中要存储元素的大概个数，可以提前将空间设置足够，就可以避免边插入边扩容导致效率低下的问题。

void TestVectorExpandOP()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

2.2.4 vector增删查改

vector 增删查改	接口说明
push_back	尾插
pop_back	尾删
find	查找（这个是算法模块实现，不是 vector 的成员接口）
insert	在 position 之前插入 val
erase	删除 position 位置的数据
swap	交换两个 vector 的数据空间
operator[ ]	像数组一样访问，通过断言来检查，而 at 是通过抛异常

//经典的错误
void Testerro()
{vector<int> v1;v1.reserve(10);for (size_t i = 0; i < 10; i++){v1[i] = i;}
}

注意：上面的代码虽然给 v1 提前开了 10 个空间，但是 v1 中的有效元素个数还是 0，即 v1.size() 的返回值是0，这样一来我们就不能直接通过下标去访问 vector 对象中的每一个元素，因为 operator[ ] 实现中的第一步就是检查下标的合理性，防止越界访问，执行 assert(pos < _size)，而此时 _size 是 0，就会出错。上面的代码只需要把 reserve 改成 resize 就可以正常运行，因为 resize 会改变 _size 的大小。如果硬要使用 reserve 提前开空间，那么接下来要使用 push_back 来插入数据。

2.3 vector<char> 可以替代 string 嘛？

答案是不可以，虽然他们俩的底层本质上都是动态增长的数组，但是 string 字符串的结尾默认有 \0，可以更好的兼容 C 接口，而 vector<char> 的结尾默认是没有 \0 的，需要我们自己插入。

三、vector模拟实现

3.1 成员变量

public:typedef T* iterator;typedef const T* const_iterator;
private:iterator _start;iterator _finish;iterator _end_of_storage;

3.2 成员函数

3.2.1 构造函数

vector():_start(nullptr), _finish(nullptr),_end_of_storage(nullptr)
{}vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{resize(n, val);
}vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{resize(n, val);
}//迭代器区间初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

小Tips：迭代器区间初始化采用的是函数模板，因为它可能使用不同类型的迭代器。其次需要单独提供一个 vector(int n, const T& val = T())，因为迭代器区间初始化采用的是函数模板，如果不单独提供这种构造函数的话，vector<int> v1(10, 1) 这种情况会去走最匹配的，即和迭代器区间初始化函数匹配，而我们希望它走 vector(size_t n, const T& val = T()) 构造函数，但是 10 会被当做 int 型，和 size_t 匹配不上，因此就会去和迭代器区间初始化函数进行匹配，InputIterator 就会被实例化成 int 型，函数中会对 int 型解引用，就会报错，其次逻辑也不符。因此需要针对 int 单独提供一个构造函数。

3.2.2 拷贝构造

//方案一
vector(const vector<T>& V):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{iterator tmp = new T[V.capacity()];//memcpy(tmp, V._start, sizeof(T) * V.size());for (size_t i = 0; i < V.size(); i++){tmp[i] = V._start[i];}_start = tmp;_finish = _start + V.size();_end_of_storage = _start + V.capacity();
}//方案二
vector(const vector<T>& V):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(V.capacity());for (auto e : V){push_back(e);}
}

小Tips：这里设计深拷贝问题，在下文的 reserve 中会提到。

3.2.3 operator=

void swap(vector<T> v)
{std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _end_of_storage);
}vector<T>& operator=(vector<T> v)//调用拷贝构造函数
{swap(v);return *this;
}

3.2.4 size

size_t size() const
{return _finish - _start;
}

3.2.5 capacity

size_t capacity() const
{return _end_of_storage - _start;
}

3.3.6 迭代器相关

iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

3.2.7 reserve（深拷贝问题）

void reserve(size_t new_capacity)
{if (new_capacity > capacity()){iterator tmp = new T[new_capacity];if (_start)//如果原来的_start申请过空间，要先将源空间中的内容拷贝过来{memcpy(tmp, _start, sizeof(T)*size());delete[] _start;}size_t vsize = size();_start = tmp;_finish = tmp + vsize;//记得更新_finish_end_of_storage = _start + new_capacity;}
}

注意：这里需要更新 _finish 和 _end_ofstorage，因为他俩表示的是位置。要更新 _finish，首先要将 size() 保存一下，因为更新 _start 后，_start 指向新空间的开头，而 _finish 指向旧空间的结尾，此时去调用 size()，计算出来的个数是有问题的，因此需要再更新 _start 之前就将原来的元素个数，即 size() 保存一份。

小Tips：上面这种扩容逻辑，当 T 是内置类或者是无需进行深拷贝的自定义类型来说，是完全满足的。但是当 T 是需要进行深拷贝的内置类型时，上面这种扩容方式就会出现大问题。以 vector<string> 为例，即当 T 是 string 的时候。

如上图所示，如果简单的用 memcpy 将旧空间的数据拷贝到新空间，那么新旧空间中存储的 string 对象指向同一个堆区上的字符串，接着在执行 delete[] _start; 销毁旧空间的时候，由于该 _start 是一个 string* 的指针，所以会先调用 string 的析构函数，将对象中申请的空间释放，即释放 _str 指向的空间，接着再去调用 operator delete 函数释放 string 对象的空间。这样一来，新空间中存储的 string 对象就有问题了，它们的成员变量 _str 指向的空间已经被释放了。这里的问题就出在 memcpy 执行的是浅拷贝。我们可以对上述代码稍作修改即可：

void reserve(size_t new_capacity)
{if (new_capacity > capacity()){iterator tmp = new T[new_capacity];if (_start)//如果原来的_start申请过空间，要先将源空间中的内容拷贝过来{//memcpy(tmp, _start, sizeof(T)*size());for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}size_t vsize = size();_start = tmp;_finish = tmp + vsize;//记得更新_finish_end_of_storage = _start + new_capacity;}
}

修改后执行tmp[i] = _start[i]; 会去调用 string 对象的赋值运算重载，进行深拷贝。

3.2.8 resize

void resize(size_t n, const T& val = T())//缺省参数给的是一个匿名对象
{if (n > size()){//检查容量，扩容if (n > capacity()){reserve(n);}//开始填数iterator it = end();while (it < _start + n){*it = val;it++;}}_finish = _start + n;
}

3.2.9 operator[ ]

T& operator[](size_t pos)//读写版本
{assert(pos < size());return _start[pos];
}const T& operator[](size_t pos) const//只读版本
{assert(pos < size());return _start[pos];
}

3.2.10 insert（迭代器失效问题）

iterator insert(iterator pos, const T& val)
{assert(pos >= _start && pos <= _finish);size_t rpos = pos - _start;//保存一下pos的相对位置//检查容量if (_finish + 1 >= _end_of_storage){size_t old_capacity = capacity();reserve(old_capacity == 0 ? 4 : old_capacity * 2);}pos = _start + rpos;//更新pos//插入数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;
}

注意：在进行 insert 的时候，会引发一个著名的问题——迭代器失效。我们希望在 pos 位置插入一个数据，pos 是一个迭代器。在插入数据之前要先检查容量，进行扩容，如果执行了扩容逻辑，_start、_finish、_end_of_storage 都指向了新空间，旧空间已经被释放了，而 pos 指向的还是原来空间中的某个位置，此时 pos 就变成了野指针，再去 pos 指向的位置填入数据，就会造成非法访问。为了避免这个问题，我们可以先保存一下 pos 的相对位置，扩完容之后再去更新 pos。

小Tips：保存相对位置更新 pos，是 insert 函数内部的解决方式，由于是传值传参，形参的 pos 更新，并不会改变实参的 pos，因此为了解决外部的迭代器失效问题，这里采用返回值的方式，将更新后的 pos 返回。可能会有小伙伴觉得，直接把形参的 pos 变成引用不香嘛？这样对形参的更新就相当于是对实参的更新。想法很好，但是不现实，因为实参很有可能具有常性，例如实参如果用 begin()、end()，他俩都是传值返回，会产生一个临时变量，该临时变量具有常性，如果形参 pos 用引用的话，就需要加 const 进行修饰，但是！但是！！如果用 const 进行修饰，那在函数内部就不能对 pos 进行更新。因此形参 pos 不能用引用。

总结：会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、
push_back等。

3.2.11 erase（迭代器失效问题）

iterator erase(iterator pos)
{assert(pos >= _start && pos <= _finish);iterator cur = pos + 1;while (cur != _finish){*(cur - 1) = *cur;cur++;}_finish--;return pos;
}

注意：erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 _finish 的位置，而 _finish 位置是没有元素的，那么 pos 就失效了。因此，删除 vector 中任意位置上的元素时，VS 就认为该迭代器失效了（VS 是通过自己重写的 iterator 进行强制检查）。Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。为了解决外部的迭代器失效问题，这里还是采用返回值的方式，返回 pos 下一个位置元素的迭代器。

3.2.12 pop_back

//直接复用即可
void pop_back()
{erase(--end());
}

四、结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！