【C++心愿便利店】No.13—C++之探索vector底层原理

文章目录

• 前言
• 一、STL简介
• • 1.1 什么是STL
  • 1.2 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 增删查改
• 三、vector模拟实现
• • 3.1 成员变量
  • 3.2 成员函数
  • • 3.2.1 构造函数
    • 3.2.2 拷贝构造函数
    • 3.2.3 operator=
    • 3.2.4 size
    • 3.2.5 capacity
    • 3.2.6 reserve(注意memcpy的拷贝方式)
    • 3.2.7 resize
    • 3.2.8 operator[]
    • 3.2.9 insert（涉及迭代器失效）
    • 3.2.10 erase（涉及迭代器失效）
    • 3.2.11 push_back
    • 3.2.12 pop_back
    • 3.2.13 迭代器

前言

👧个人主页：@小沈YO.
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：C++ 心愿便利店
🔑本章内容：vector
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

提示：以下是本篇文章正文内容，下面案例可供参考

一、STL简介

1.1 什么是STL

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

1.2 STL的六大组件

二、vector的介绍及使用

2.1 vector的介绍

vector的文档介绍

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

2.2 vector的使用

2.2.1 vector的定义

void test_vector1()
{
	//构造函数
	vector<int> v;//无参构造
	vector<int> v1(5, 1);
	vector<int> v2(v1.begin(), v1.end());
	string s1 = "hello world";
	vector<int> v3(s1.begin(), s1.end());//隐式类型转换
	vector<int> v4(v3);//拷贝构造
}

2.2.2 vector iterator 的使用

void test_vector1()
{
	vector<int> v2(v1.begin(), v1.end());
	string s1 = "hello world";
	vector<int> v3(s1.begin(), s1.end());//隐式类型转换
	vector<int> v4(v3);//拷贝构造
	
	//1.iterator
	vector<int>::iterator it = v3.begin();
	while (it != v3.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	
	//2.operator[]
	for (size_t i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " ";
	}
	cout << endl;

	//3.范围for
	for (auto e : v4)
	{
		cout << e << " ";
	}
	cout << endl;
}

2.2.3 vector 空间增长问题

// 测试vector的默认扩容机制
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';
 	 }
  }
}

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

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

// 如果已经确定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';
 	}
  }
}

• resize在开空间的同时还会进行初始化，影响size

void test_vector3()
{
	vector<int> v1;
	cout << v1.max_size() << endl;

	size_t sz;
	vector<int> v;
	//v.reserve(100);   ---> size=0,capacity=100
	v.resize(100);      ---> size=100,capacity=100
	//for (size_t i = 0; i < v.size(); i++)//当写成这种形式用reserve(100)是不会进入循环的因为v.size()返回值是0
	for (size_t i = 0; i < 100; i++)
	{
		v[i] = i;//断言在release下不起作用
		//虽然空间开出来了100但是不能访问，因为operator[]里面加了断言，断言访问的下标必须是小于size的,大于size就越界了,所以只能访问[0，size-1]的数据,但是reverse(100)--->size=0
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

上面的代码用reserve(100)虽然给 v 提前开了 100 个空间，但是 v 中的有效元素个数size还是 0，所以不能直接通过下标去访问 vector 对象中的每一个元素，因为 operator[ ] 实现中的第一步就是检查下标的合理性，防止越界访问，执行 assert(pos < _size)，而此时 _size 是 0，就会越界报错。而把 reserve 改成 resize 就可以正常运行，因为 resize 会改变 _size 的大小。

2.2.4 vector 增删查改

vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	
	v.insert(v.begin(), 0);
	
	auto it=find(v.begin(), v.end(), 3);寻找--->注意这个是算法模块实现，不是vector的成员接口
	if (it != v.end())
	{
		v.insert(it, 30);插入
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	it = find(v.begin(), v.end(), 3);
	if (it != v.end())
	{
		v.erase(it);删除
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	
	cout << endl;
	cout << v.size() << endl;
	cout << v.capacity() << endl;

	v.clear();
	v.shrink_to_fit();//缩容不建议用

	cout << v.size() << endl;
	cout << v.capacity() << endl;
}

三、vector模拟实现

3.1 成员变量

class vector
{
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(int n, const T& val  = T())
{
	reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

vector(size_t n, const T& val = T())
{
	rserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}
//迭代器区间初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

• 无参的构造并不陌生
• 带参的构造并初始化为什么要写两个？

因为如果不单独提供一个 vector(int n, const T& val = T())；代码vector v1(10, 1) 会走最匹配的，即和迭代器区间初始化函数匹配（迭代器区间初始化采用的是函数模板），但是我们希望它走 vector(size_t n, const T& val = T()) 构造函数，可是 10 是 int 型，和 size_t 不匹配上（只会走最匹配的），因此就会去和迭代器区间初始化函数进行匹配，InputIterator 就会被实例化成 int 型，函数中会对 int 型解引用，就会报错

• 迭代器区间初始化采用的是函数模板，因为它可能使用不同类型的迭代器。

3.2.2 拷贝构造函数

vector(const vector<T>& v)//const对象
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(v.capacity());
	for (auto& e : v)//这里加上&防止T是个大对象拷贝代价大
	{
		push_back(e);
	}
}

3.2.3 operator=

vector<T> operator=(vector<T> tmp)
{
	swap(tmp);
	return *this;
}
void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}

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.2.6 reserve(注意memcpy的拷贝方式)

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * sz);
			delete[] _start;
		}
		_start = tmp;

		_finish = _start + size();
		_end_of_storage = _start + cp;
	}
}
_________________________________________________________________________________________
void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * sz);
			delete[] _start;
		}
		_finish = tmp + size();
		_start = tmp;

		_end_of_storage = _start + cp;
	}
}
_________________________________________________________________________________________
void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * sz);
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

注意：第一种代码的写法是不正确的，因为当开辟新空间tmp，将_start中的数据拷贝到tmp中，释放原空间，将_start指针指向新空间，所以运行代码_finish = _start + size();时要先调用size()，而size=_finish – _start，其中_finish是nullptr（构造时初始化），而_start并不是nullptr（此时是tmp），所以我们预期中的size并不是等于0，而是size=0-_start，所以_finish=_start+0-_start=0
解决方式：

• 写成_finish = tmp + size(); _start = tmp;注意先后顺序，如果写成 _start = tmp; _finish = tmp + size(); 先调用size=_finish-_start=0-tmp;最终_finish=tmp+0-tmp还是没有解决问题，同样也不能写成_finish = _start + size(); _start = tmp; 此时的_start=0，所以_finish=0+0=0，也是不对的
• 第一种的解决方式是可以的但是可读性太差，顺序不对就导致错误，所以可以提前用一个变量存储size()的返回值，size_t sz = size();此时就不会因为顺序报错啦

上面这种扩容逻辑，当 T 是内置类或者是不需要进行深拷贝的自定义类型来说，是可以的。但是当 T 是需要进行深拷贝的类型时，上述这种扩容方式就会出现问题。下述代码以 vector 为例：

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * sz);
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}
void test_vector5()
{
	vector<string> s;
	s.push_back("11111111111111111111");
	s.push_back("11111111111111111111");
	s.push_back("11111111111111111111");
	s.push_back("11111111111111111111");
	s.push_back("11111111111111111111");
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

通过上图可以明显地观察到当插入4个字符串时是没有问题的但是当插入第五个字符串时就会出现问题，显然是扩容中出现了问题，上述代码用 memcpy 将旧空间的数据拷贝到新空间，那么新旧空间中存储的 string 对象指向同一个堆区上的字符串空间，接着在执行 delete[] _start; 销毁旧空间的时候，由于该 _start 是一个 string* 的指针，所以会先调用 string 的析构函数，将对象中申请的空间释放，也就是释放 _str 指向的空间，然后再去调用 operator delete 函数释放 string 对象的空间。所以新空间中存储的 string 对象就出现了问题，因为它的成员变量 _str 指向的空间已经被释放了。
显然 memcpy 执行的是浅拷贝，只需要修改成tmp[i] = _start[i]; 这样会调用 string 对象的赋值运算重载，进行深拷贝。

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * sz);
			for (size_t i=0;i<sz;i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

3.2.7 resize

void resize(size_t n, const T& val = T())
{
	if (n <= size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		//填数据
		while (_finish<_start+n)
		{
			*_finish = val;
			++_finish;
		}
	 }
}

3.2.8 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.9 insert（涉及迭代器失效）

void insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);//检查容量
	}
	iterator end = _finish - 1;
	//插入数据
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	*pos = x;
	_finish++;
}
___________________________________________________________________________________________-
void insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	*pos = x;
	_finish++;
}

注意：在进行 insert 的时候，会引发一个问题 —- 迭代器失效：如果失效就不能再使用这个迭代器，如果使用了，结果未定义。
首先pos 是一个迭代器，在 pos 位置插入一个数据时，要在插入数据之前先检查容量，进行扩容，但是执行了扩容逻辑后，_start、_finish、_end_of_storage 都指向了新空间，旧空间被释放了，且 pos 指向的却还是原来空间中的某个位置，此时 pos 就变成了野指针，再去 pos 指向的位置插入数据时，就会造成非法访问就像第一种所写的代码（总而言之就是扩容导致pos失效）
解决方式：为了解决迭代器失效的问题，可以在检查容量扩容之前先保存一下pos的相对位置，在进行扩容释放旧空间指向新空间逻辑后，更新一下pos指针（总而言之就是更新pos）

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	*pos = x;
	_finish++;
	return pos
}
void test_vector3()
{
	vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	vector<int>::iterator it = v.begin()+2;
	v.insert(it, 30);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

对于上述代码调用insert，虽然更新了 pos，但是由于是传值，形参 pos 的更新，并不会改变实参的 it，所以insert后it可能会失效。
解决上述问题很简单直接把形参的 pos 变成引用不就可以吗？这样形参pos的改变也就使得实参it改变。
这样是可以的解决了传值传参的问题，但是也会引发诸多问题，例如：v.insert(v.begin(), 30);当运行这段代码时就会报错，因为实参具有常性（begin()是传值返回，会产生一个临时变量，临时变量具有常性），&必须要传变量不能传带const属性的值。
所以形参 pos 用引用的话，就需要加 const 进行修饰。但是如果用 const 进行修饰，那在函数内部就不能对 pos 进行更新，所以形参 pos 不能用引用，可以采用返回值的方式，将更新后的 pos 返回。

3.2.10 erase（涉及迭代器失效）

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

根据上述insert实现中迭代器失效是因为扩容引起的，但是erase 只是删除 pos 位置元素，pos 位置之后的元素往前覆盖，没有导致空间的改变，理论上迭代器不会失效
但是根据上述代码，如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 _finish 的位置，而 _finish 位置是没有元素的，那么 pos 就失效了。为了迭代器失效问题，还是可以采用返回值的方式，返回 pos 下一个位置元素的迭代器。

3.2.11 push_back

void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		reserve( capacity() == 0 ? 4 : capacity() * 2);
	}
	*_finish = x;            
	_finish++;                
}
__________________________________________________________________________________
//push_back可以直接复用insert
void push_back(const T& x)
{
	insert(end(), x);
}

3.2.12 pop_back

void pop_back()
{
	erase(--end());
}

3.2.13 迭代器

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

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

vector<int>::iterator it = v.begin();
while (it != v.end())
{
	*it *= 10;
	cout << *it << " ";
	it++;
}
cout << endl;
for (auto e : v)
{
	cout << e << " ";
}
	cout << endl;
}