【C++】vector 的使用及其模拟实现

一、vector 的使用

vector 是我们学习的第一个真正的 STL 容器，它接口的使用方式和 string 有一点点的不同，但大部分都是一样的，所以这里我们就只演示其中一些接口的使用，大家如果有疑惑的地方直接在 cplusplus 是上面查看对应的文档即可。

1、构造函数

vector 提供了四种构造方式 – 无参构造、n 个 val 构造、迭代器区间构造以及拷贝构造：

其中构造函数的最后一个参数 alloc 是空间配置器，它和内存池有关，作用是提高空间分配的效率；我们日常使用时不用管这个参数，使用它的缺省值即可，但是可能有极少数的人想要用自己实现的空间配置器来代替 STL 库提供的，所以留出了这一个参数的位置。

需要注意的是，迭代器区间构造是一个函数模板，即我们可以用其他类来构造 vector 对象：

同时，上面还有一个非常重要的细节：

在 n 个 val 的构造中，val 的缺省值是 T 的匿名对象，该对象使用 T 的默认构造来初始化，而不是以 0 作为缺省值，这是因为 T 不仅仅可能是内置类型，也可能是自定义类型，比如 string、list、vector；

当 T 为自定义类型时，0 就不一定能够对 val 进行初始化，所以我们需要使用 T 的匿名对象来调用默认构造完成初始化工作；当 T 为内置类型时，我们仍然可以以这种方式进行初始化，因为 内置类型也具有构造函数，你没听错，内置类型也是有构造函数的，大家可以理解为，为了解决上面这种情况，编译器对内置类型进行了特殊处理；

利用匿名对象调用默然构造函数来作为缺省值的方法在下面 resize、insert 等接口中也有体现。

2、扩容机制

vector 的扩容机制和 string 的扩容机制是一样的，因为它们都是动态增长的数组：VS 下大概是 1.5 被扩容，Linux g++ 下是标准的二倍扩容，测试用例如下：

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';
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3、三种遍历方式

和 string 一样，vector 也支持三种遍历方式 – 下标加[]遍历、迭代器遍历、范围for遍历：

需要注意的是，vector 和 string 之所以支持 下标 + [] 的方式遍历，是因为它们底层都是数组，而数组支持随机访问，但是像我们后面要学习的 list set map 等容器，它们的底层不是数组，不支持随机访问，就只能通过迭代器和范围 for 的方式进行遍历了；不过，范围 for 只是一个外壳，它在使用时也是被替换成迭代器，所以其实迭代器遍历才是最通用的遍历方式。

4、容量操作

vector 有如下容量相关的接口：

其中，最重要的两个函数是 reserve 和 resize，reserve 只用于扩容，它不改变 size 的大小；而 resize 是扩容加初始化，既会改变 capacity，也会改变 size；

注意：reserve 和 resize，包括后面的 clear 函数都不会缩容，因为缩容需要开辟新空间、拷贝数据、释放旧空间，而对于自定义类型又有可能存在深拷贝问题，时间开销极大；vector 中唯一可能缩容的函数就只有 shrink_to_fit，对于它来说，如果 capacity 大于 size，它会进行缩容，让二者相等。

5、元素访问

vector 提供了如下接口来进行元素访问：

其中，operator 和 at 都是返回 pos 下标位置元素的引用，且它们内部都会对 pos 的合法性进行检查；不同的是，operator[] 中如果检查到 pos 非法，那么它会直接终止程序，报断言错误，而 at 则是抛异常；

注：release 模式下检查不出断言错误。

6、修改 – 迭代器失效

vector 提供了如下接口来进行修改操作：

assign && push_back && pop_back

assign 函数用来替换 vector 对象中的数据，支持 n 个 val 替换，以及迭代器区间替换，push_back 尾插、pop_back 尾插，这些接口的使用和 string 一模一样，这里就不再过多阐释；

insert && erase

和 string 不同，为了提高规范性，STL 中的容器都统一使用 iterator 作为 pos 的类型，并且插入/删除后会返回 pos：

所以，以后我们如果要在中间插入或删除元素的话，必须配合算法库里面的 find 函数来使用：

同时，在 VS 下，insert 和 erase 之后会导致 pos 迭代器失效，如果需要再次使用，需要更新 pos，如下：

不过，在 Linux 下不会出现这个问题：

造成这个问题的根本原因是 VS 使用的 PJ 版本对 iterator 进行了封装，在每次 inset 和 erase 之后对迭代器进行了特殊处理，而 g++ 使用的 SGI 版本中的 iterator 是原生指针，具体细节在后文 vector 的模拟实现中我们再讨论；

但是为了代码的可移植性，我们 统一认为 insert 和 erase 之后迭代器会失效，所以，如果要再次使用迭代器，我们必须对其进行更新；我们以移除 vector 中的所有偶数为例：

swap

和 vector 一样，由于算法库 swap 函数存在深拷贝的问题，vector 自己提供了一个不需要深拷贝的 swap 函数，用来交换两个 vector 对象：

同时，为了避免我们不使用成员函数的 swap，vector 还将算法库中的 swap 进行了重载，然后该重载函数的内部又去调用成员函数 swap：

---

二、vector 的模拟实现

1、浅析 vector 源码

对于编程来说，学习初期进步最快的方式就是阅读别人优秀的代码，理解其中的逻辑和细节后自己独立的去实现几次，学习 STL 也是如此；我们可以适当的去阅读 STL 的源码，当然我们并不是要逐行的进行阅读，因为这样太耗费时间，况且其中很多 C++ 的语法我们也还没学。

当前阶段，我们阅读 STL 源码是为了学习 STL 库的核心框架，然后根据这个框架自己模拟实现一个简易的 vector (只实现核心接口)；阅读源码与模拟实现能够让我们更好的了解底层，对 STL 做到 能用，并且 明理。

我们在 【STL简介 – string 的使用及其模拟实现】 中对 STL 做了一些基本的介绍，知道了 STL 由原始版本主要发展出了 PJ、RW 和 SGI 版本，其中，微软的 VS 系列使用的就是 PJ 版，但是由于其命名风格的原因，我们阅读源码时一般选择 SGI 版，而且 Linux 下 gcc/g++ 也是使用的 SGI 版本，再加上侯捷老师有一本非常著名的书 《STL源码剖析》也是使用的 SGI 版本，所以以后阅读和模拟实现 STL 时我都使用这个版本。

《STL源码剖析》电子版和 《stl30》源码我都放在下面了，需要的可以自取：

STL源码剖析：https://www.aliyundrive.com/s/Nc4mpLC43kj
stl30：https://www.aliyundrive.com/s/pnwMuB9uwEN
1
2

vector 的部分源码如下：

//vector.h
#ifndef __SGI_STL_VECTOR_H
#define __SGI_STL_VECTOR_H

#include 
#include 
#include 

#ifdef __STL_USE_NAMESPACES
using __STD::vector;
1
2
3
4
5
6
7
8
9
10

//stl_vector.h
template <class T, class Alloc = alloc>
class vector {
public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
    
   //成员函数
    
protected:
  typedef simple_alloc<value_type, Alloc> data_allocator;
  iterator start;
  iterator finish;
  iterator end_of_storage;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

可以看到，vector.h 仅仅是将几个头文件包含在一起，vector 的主要实现都在 stl_vector.h 里面。

2、核心框架

我们可以根据上面的 vector 源码来得出 vector 的核心框架：

namespace thj {
	template<class T>
    class vector {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

    public:
        //成员函数

    private:
        T* _start;
        T* _finish;
        T* _end_of_storage;
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看到，vector 的底层和 string 一样，都是一个指针指向一块动态开辟的数组，但是二者不同的是，string 是用 _size 和 _capacity 两个 size_t 的成员函数来维护这块空间，而 vector 是用 _finish 和 _end_of_storage 两个指针来维护这块空间；虽然 vector 使用指针看起来难了一些，但本质上其实是一样的 – _size = _finish - _start, _capacity = _end_of_storage - _start;

3、构造函数错误调用问题

在我们模拟实现了构造函数中的迭代器区间构造和 n 个 val 构造后，我们会发现一个奇怪的问题，我们使用 n 个 val 来构造其他类型的对象都没问题，唯独构造 int 类型的对象时会编译出错，如下：

//迭代器区间构造
template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }

//n个val构造
vector(size_t n, const T& val = T())
    :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {
        reserve(n);
        for (size_t i = 0; i < n; i++)
            push_back(val);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这是由于编译器在进行模板实例化以及函数参数匹配时会调用最匹配的一个函数，当我们将 T 实例化为 int 之后，由于两个参数都是 int，所以对于迭代器构造函数来说，它会直接将 InputIterator 实例化为 int；

但对于 n 个 val 的构造来说，它不仅需要将 T 实例化为 int，还需要将第一个参数隐式转换为 size_t；所以编译器默认会调用迭代器构造，同时由于迭代器构造内部会对 first 进行解引用，所以这里报错 “非法的间接寻址”；

解决方法有很多种，比如将第一个参数强转为 int，又或者是将 n 个 val 构造的第一个参数定义为 int，我们这里和 STL 源码保持一致 – 提供第一个参数为 int 的 n 个 val 构造的重载函数：

//n个val构造
vector(size_t n, const T& val = T())
    :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {
        reserve(n);
        for (size_t i = 0; i < n; i++)
            push_back(val);
    }

//n个val构造 -- 重载
vector(int n, const T& val = T())
    :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {
        reserve(n);
        for (int i = 0; i < n; i++)
            push_back(val);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、insert 和 erase 迭代器失效问题

我们模拟实现的 insert 和 erase 函数如下：

//任意位置插入
iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    //扩容导致 pos 迭代器失效
    if (size() == capacity())
    {
        size_t oldPos = pos - _start;  //记录pos，避免扩容后pos变为野指针
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
        pos = _start + oldPos;  //扩容之后更新pos
    }

    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }

    *pos = x;
    ++_finish;
    return pos;
}

//任意位置删除 -- erase 之后也认为 pos 迭代器失效
iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator begin = pos;
    while (begin < _finish - 1)
    {
        *begin = *(begin + 1);
        ++begin;
    }
    --_finish;
    return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

我们在 vector 的使用中就提到 VS 下 insert 和 erase 后迭代器会失效，再次访问编译器会直接报错，这是因为 PJ 版本下 iterator 不是原生指针，如下：

可以看到，VS 中的迭代器是一个类，当我们进行 insert 或者 erase 操作之后，iterator 中的某个函数可能会将 pos 置为空或者其他操作，导致再次访问 pos 报错，除非我们每次使用后都更新 pos：

而 Linux 下的 g++ 却不会出现这样的问题，因为 g++ 使用的是 SGI 版本，该版本的源码我们在上面也已经见过了，其迭代器是一个原生指针，同时它内部 insert 和 erase 接口的实现也和我们模拟的类似，可以看到，我们并没有在函数内部改变 pos (改变也没用，因为这是形参)，所以 insert、erase 之后 pos 可以继续使用；

但是这里也存在一个问题，insert 和 erase 之后 pos 的意义变了 – 我们插入元素后 pos 不再指向原来的元素，而是指向我们新插入的元素；同样，erase 之后 pos 也不再指向原来的元素，而是指向该元素的后一个元素；特别是当 erase 尾部的数据后，pos 就等于 _finish 了；

那么对于不了解底层的人就极易写出下面这样的代码 – 删除 vector 中的所有偶数：

可以看到，第一个由于删除元素后 pos 不再指向原位置，而是指向下一个位置，所以 erase 之后会导致一个元素被跳过，导致部分偶数没有被删除，但好在末尾是奇数，所以程序能够正常运行；

但是第二个就没那么好运了，由于最后一个元素是偶数，所以 erase 之后 pos 直接指向了 _finish 的下一个位置，循环终止条件失效，发生越界。

综上，为了保证程序的跨平台性，我们统一认为 insert 和 erase 之后迭代器失效，必须更新后才能再次使用。

5、reserve 函数的浅拷贝问题

除了上面这两个问题之外，我们的 vector 还存在一个问题 – reserve 函数 深层次的浅拷贝问题，模拟实现的 reserve 函数如下：

void reserve(size_t n)
{
    if (n > capacity())  //reserve 函数不缩容
    {
        T* tmp = new T[n];
        memcpy(tmp, _start, sizeof(T) * size());
        size_t oldSize = _finish - _start;  //记录原来的size，避免扩容不能确定_finish
        delete[] _start;

        _start = tmp;
        _finish = _start + oldSize;
        _end_of_storage = _start + n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

很多同学看到这段代码的时候可能会认为它没问题，的确，对于内置类型来说它确实是进行了深拷贝，但是对于需要进行深拷贝的自定义类型来说它就有问题了，如下：

程序报错的原因如图：当 v 中的元素达到4个再进行插入时，push_back 内部就会调用 reserve 函数进行扩容，而扩容时我们虽然对存放 v1 v2 的空间进行了深拷贝，但是空间里面的内容我们是使用 memcpy 按字节拷贝过来的，这就导致原来的 v 里面的 string 元素和现在 v 里面的元素指向的是同一块空间。

当我们拷贝完毕之后使用 delete[] 释放原空间，而 delete[] 释放空间时对于自定义类型会调用其析构函数，而 v 内部的 string 对象又会去调用自己的析构函数，所以 delete[] 完毕后原来的 v 以及 v 中各个元素指向的空间都被释放了，此时现在的 v 里面的每个元素全部指向已经释放的空间。

从第一张图中我们也可以看到，最后一次 push_back 之后 v 里面的元素全部变红了；最终，当程序结束自动调用析构函数时，就会去析构刚才已经被释放掉的 v 中的各个 string 对象指向的空间，导致同一块空间被析构两次，程序出错。

所以，在 reserve 内部，我们不能使用 memcpy 直接按字节拷贝原空间中的各个元素，因为这些元素可能也指向一块动态开辟的空间，而应该调用每个元素的拷贝构造进行拷贝，如图：

具体代码实现如下：

//扩容
void reserve(size_t n)
{
    if (n > capacity())  //reserve 函数不缩容
    {
        T* tmp = new T[n];
        //memcpy(tmp, _start, sizeof(T) * size());  //error

        //memcpy有自定义类型的浅拷贝问题，需要对每个元素使用拷贝构造进行深拷贝
        for (int i = 0; i < size(); i++)
            tmp[i] = _start[i];  //拷贝构造

        size_t oldSize = _finish - _start;  //记录原来的size，避免扩容不能确定_finish
        delete[] _start;

        _start = tmp;
        _finish = _start + oldSize;
        _end_of_storage = _start + n;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意：有的同学看到这里使用的是赋值运算符就认为这里调用的赋值重载，其实不是的，因为这里完成的是初始化工作，编译器会自动转换为调用拷贝构造函数。

6、模拟 vector 整体代码

在了解了 vector 的核心框架以及解决了上面这几个疑难点之后，剩下的东西就变得很简单了，所以我这里直接给出结果，大家可以根据自己实现的对照一下，如有错误，也欢迎大家指正：

//vector.h
#pragma once
#include 
#include 
#include 
#include 

namespace thj {  //防止命名冲突
	template<class T>
	class vector {
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

	public:
		//-------------------------------------constructor---------------------------------------//
		//无参构造
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{}

		//迭代器区间构造
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//n个val构造
		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
				push_back(val);
		}

		//n个val构造 -- 重载
		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; i++)
				push_back(val);
		}

		//拷贝构造 -- 写法1
		//vector(const vector& v)
		//{
		//	T* tmp = new T[v.capacity()];
		//	memcpy(tmp, v._start, sizeof(T) * v.capacity());
		//	_start = tmp;
		//	_finish = _start + v.size();
		//	_end_of_storage = _start + v.capacity();
		//}

		//拷贝构造 -- 写法2
		//vector(const vector& v)
		//	: _start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//{
		//	reserve(v.capacity());
		//	for (size_t i = 0; i < v.size(); i++)
		//		push_back(v[i]);
		//}

		//拷贝构造 -- 现代写法
		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end());  //复用构造函数和swap函数
			swap(tmp);
		}

		//析构函数
		~vector() {
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

		//赋值重载
		vector<T>& operator=(vector<T> v)  //复用拷贝构造，存在自我赋值的问题，但不影响程序正确性
		{
			swap(v);
			return *this;
		}

		//----------------------------------iterator---------------------------------------//
		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

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

		bool empty() const
		{
			return _start == _finish;
		}

		//扩容
		void reserve(size_t n)
		{
			if (n > capacity())  //reserve 函数不缩容
			{
				T* tmp = new T[n];
				//memcpy(tmp, _start, sizeof(T) * size());  //error

				//memcpy有自定义类型的浅拷贝问题，需要对每个元素使用拷贝构造进行深拷贝
				for (int i = 0; i < size(); i++)
					tmp[i] = _start[i];  //拷贝构造

				size_t oldSize = _finish - _start;  //记录原来的size，避免扩容不能确定_finish
				delete[] _start;

				_start = tmp;
				_finish = _start + oldSize;
				_end_of_storage = _start + n;
			}
		}

		//扩容并初始化
		void resize(size_t n, T x = T())
		{
			if (n > capacity())  //resize 不缩容
			{
				reserve(n);
			}
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = x;
					++_finish;
				}
			}
			if (n < size())
			{
				_finish = _start + n;
			}
		}
        
		//----------------------------------------element access---------------------------------//
		T& operator[](size_t pos)
		{
			assert(pos < size());  //检查越界
			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}

		//----------------------------------------modifys-----------------------------------------//
		//尾插
		void push_back(const T& n)
		{
			if (size() == capacity())
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}
			*_finish = n;
			++_finish;
		}

		//尾删
		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

		//任意位置插入 -- 插入后认为迭代器失效
		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

            //扩容会导致迭代器失效
			if (size() == capacity())
			{
				size_t oldPos = pos - _start;  //记录pos，避免扩容后pos变为野指针
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + oldPos;  //扩容之后更新pos
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}

			*pos = x;
			++_finish;
			return pos;
		}

		//任意位置删除 -- erase 之后也认为 pos 迭代器失效
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator begin = pos;
			while (begin < _finish - 1)
			{
				*begin = *(begin + 1);
				++begin;
			}
			--_finish;
			return pos;
		}

		//交换两个对象
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);  //复用算法库的swap函数
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

		void clear()
		{
			_finish = _start;
		}

	private:
		T* _start;
		T* _finish;
		T* _end_of_storage;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277

---