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

朱雀 2023-10-15 09:47 151阅读 0赞

![在这里插入图片描述][695afd4d2aeb43d29b3d3eeb540f2dc3.gif_pic_center]

#### **文章目录** ####

*  一、STL
 *   *  1.1 什么是STL?
     *  1.2 STL的版本
     *  1.3 STL的六大组件
 *  二、vector的介绍及使用
 *   *  2.1 vector的介绍
     *  2.2 vector的使用
     *   *  2.2.1 vector的定义
         *  2.2.2 vector iterator
         *  2.2.3 vector空间增长问题
         *  2.2.4 vector增删查改
     *  2.3 vector\\

## 一、STL ##

### 1.1 什么是STL? ###

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

![在这里插入图片描述][3ab3466ce77b43608f933f198c67c904.png_pic_center]

### 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的六大组件 ###

![在这里插入图片描述][3e5d857a2e4a4647ba2e248e5841652d.png_pic_center]

## 二、vector的介绍及使用 ##

### 2.1 vector的介绍 ###

*  vector 是表示可变大小数组序列容器。
 *  就像数组一样，vector 也采用连续的存储空间来存储元素。也就意味着可以采用小标对 vector 的元素进行访问，和数组处理一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
 *  本质讲，vector 使用动态分配数组来存储它的元素。当新元素插入时，为了增加存储空间，这个数组需要被重新分配大小。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价较高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
 *  vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因此存储空间（容量）比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候实在常数时间复杂度完成的。
 *  因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
 *  与其它的动态序列容器相比（如：deque、list、forward\_list），vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率会比较低。

### 2.2 vector的使用 ###

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

#### 2.2.1 vector的定义 ####

<table> 
 <thead> 
  <tr> 
   <th align="center"><b>构造函数声明</b></th> 
   <th align="center"><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">vector()</td> 
   <td align="center">无参构造</td> 
  </tr> 
  <tr> 
   <td align="center">vector(size_type n, const value_type&amp; val = value_type())</td> 
   <td align="center">构造并初始化 n 个 val</td> 
  </tr> 
  <tr> 
   <td align="center">vector(const vector&amp; x)</td> 
   <td align="center">拷贝构造</td> 
  </tr> 
  <tr> 
   <td align="center">vector(Inputlterator first, Inputiterator last)</td> 
   <td align="center">使用迭代器区间进行初始化构造</td> 
  </tr> 
 </tbody> 
</table>

**小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 ####

<table> 
 <thead> 
  <tr> 
   <th><b>iterator的使用</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>begin + end</td> 
   <td>获取第一个数据位置的 iterator / const_iterator，获取最后一个数据下一个位置的iterator / const_iterator</td> 
  </tr> 
  <tr> 
   <td>rbegin + rend</td> 
   <td>获取最后一个数据位置的 reverse_iterator，获取第一个数据前一个位置的 reverse_iterator</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][e4be3147dfc242dda2f494b9e8533fa2.png_pic_center]

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空间增长问题 ####

<table> 
 <thead> 
  <tr> 
   <th><b>容量空间</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size()</td> 
   <td>获取数据个数</td> 
  </tr> 
  <tr> 
   <td>capacity()</td> 
   <td>获取容量大小</td> 
  </tr> 
  <tr> 
   <td>empty()</td> 
   <td>判断是否为空</td> 
  </tr> 
  <tr> 
   <td>resize(size_type n); resize (size_type n, const value_type&amp; val)</td> 
   <td>改变 vector 的 size</td> 
  </tr> 
  <tr> 
   <td>reserve(size_type n)</td> 
   <td>改变 vector 的 capacity</td> 
  </tr> 
 </tbody> 
</table>

*  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 下的结果：  
![在这里插入图片描述][81a52117aba54300b28699a6135a6f74.png_pic_center]  
Linux 下的结果：  
![在这里插入图片描述][52852a87772d4df68f89dd44c25ac90c.png_pic_center]  
**小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增删查改 ####

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

//经典的错误
    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模拟实现 ##

![在这里插入图片描述][260246be920243eca697c3c2ebc5af07.png_pic_center]

### 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 的时候。

![在这里插入图片描述][ef541bace195469da18cc62f2d20342f.png_pic_center]  
如上图所示，如果简单的用 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。

![在这里插入图片描述][2b651418bdae4d39ba4051c51fd1ce90.png_pic_center]  
**小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());
    }

## 四、结语 ##

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

![在这里插入图片描述][edc78985d03043828f98dcd5a8d2983e.gif_pic_center]

[695afd4d2aeb43d29b3d3eeb540f2dc3.gif_pic_center]: https://img-blog.csdnimg.cn/695afd4d2aeb43d29b3d3eeb540f2dc3.gif#pic_center
[3ab3466ce77b43608f933f198c67c904.png_pic_center]: https://img-blog.csdnimg.cn/3ab3466ce77b43608f933f198c67c904.png#pic_center
[3e5d857a2e4a4647ba2e248e5841652d.png_pic_center]: https://img-blog.csdnimg.cn/3e5d857a2e4a4647ba2e248e5841652d.png#pic_center
[vector]: https://legacy.cplusplus.com/reference/vector/vector/
[e4be3147dfc242dda2f494b9e8533fa2.png_pic_center]: https://img-blog.csdnimg.cn/e4be3147dfc242dda2f494b9e8533fa2.png#pic_center
[81a52117aba54300b28699a6135a6f74.png_pic_center]: https://img-blog.csdnimg.cn/81a52117aba54300b28699a6135a6f74.png#pic_center
[52852a87772d4df68f89dd44c25ac90c.png_pic_center]: https://img-blog.csdnimg.cn/52852a87772d4df68f89dd44c25ac90c.png#pic_center
[260246be920243eca697c3c2ebc5af07.png_pic_center]: https://img-blog.csdnimg.cn/260246be920243eca697c3c2ebc5af07.png#pic_center
[ef541bace195469da18cc62f2d20342f.png_pic_center]: https://img-blog.csdnimg.cn/ef541bace195469da18cc62f2d20342f.png#pic_center
[2b651418bdae4d39ba4051c51fd1ce90.png_pic_center]: https://img-blog.csdnimg.cn/2b651418bdae4d39ba4051c51fd1ce90.png#pic_center
[Link 1]: https://blog.csdn.net/weixin_63115236?spm=1000.2115.3001.5343
[edc78985d03043828f98dcd5a8d2983e.gif_pic_center]: https://img-blog.csdnimg.cn/edc78985d03043828f98dcd5a8d2983e.gif#pic_center