【C++干货铺】解密vector底层逻辑

=========================================================================

个人主页点击直达：小白不是程序媛

C++系列专栏：C++干货铺

代码仓库：Gitee

=========================================================================

目录

vector介绍

vector的使用

vector的定义和使用

vector的空间增长问题

vector的增删查改

解密vector及模拟实现

成员变量

成员函数

构造函数

拷贝构造函数

operator = 

析构函数

reserve

push_back

erase

 resize

insert

operator [ ] 

迭代器

size

capacity

vector介绍

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

vector的使用

vector的使用和string差不多，有很多的接口供我们函数调用。这些函数的功能包括增、删、查、改等。

vector的定义和使用

	vector <int> v1;
	vector <int> v2(10, 1);
	for (size_t i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " ";
	}
	cout << endl;
	vector<int>::iterator it = v2.begin();
	while (it != v2.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	string s1("hello world");
	vector<char> v3(s1.begin(), s1.end());
	for (auto ch : v3)
	{
		cout << ch << " ";
	}
	cout << endl;
	vector<char> v4(v3);
	for (auto ch : v4)
	{
		cout << ch << " ";
	}
	cout << endl;

vector的空间增长问题

	vector<int> v1;
	
	size_t sz = v1.capacity();
	cout << "初始容量：" << sz << endl;
	for (size_t i = 0; i < 100; i++)
	{
		v1.push_back(i);
		if (sz != v1.capacity())
		{
			sz = v1.capacity();
			cout << "容量： " << sz << endl;
		}
	}

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
• reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
• resize在开空间的同时还会进行初始化，影响size。

vector的增删查改

	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	v.pop_back();
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	vector<int>::iterator pos = v.begin();
	v.insert(pos, 1);
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	v.erase(v.begin());
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;

解密vector及模拟实现

成员变量

	//指向动态开辟空间的开始
	iterator _start;
	//指向最后一个有效数据的结尾
	iterator _finish;
	//指向动态开辟空间的结尾
	iterator _end;

vector是通过三个指针实现的，并不像我们在数据结构初阶那样使用一个指向动态开辟的指针和两个变量来实现。三个指针都指向的是动态开辟的空间，只不过各司其职；第一个指针直接指向动态开辟空间，第二个指针指向动态开辟空间中有效数据的个数的下一位，第三个指针指向的是动态开辟空间的结尾。

成员函数

构造函数

	//传入数据类型的指针
	typedef T* iterator;
	//静态
	typedef const T* const_iterator;
	//构造函数
	Vector()
		:_start(nullptr)
		, _finish(nullptr)
		, _end(nullptr)
	{}

使用初始化列表对成员变量进行初始化为空指针。

拷贝构造函数

	Vector(const Vector<T>& x)
		:_start(nullptr)
		, _finish(nullptr)
		, _end(nullptr)
	{
		reserve(x.capacity());
		for (auto e : x)
		{
			push_back(e);
		}
	}

operator =

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

析构函数

	~Vector()
	{
		delete[] _start;
		_start = _finish = _end = nullptr;
	}

reserve

	void reserve(size_t n)
	{
		
		if (n > capacity())
		{
			T* tmp = new T[n];
			//记录开始和有效数据结尾中间的有效数据个数防止，迭代器失效
			size_t sz = size();
			//判断原指针是否为空指针，第一次开辟空间是空指针
			if (_start)
			{
				//将有效数据的字节数拷贝到新空间中
                //memcpy函数只会进行的是浅拷贝，对于自定以类型无法完成深拷贝
				//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= _start + n;
		}
	}

这里我们要进行空间的扩容，先将size记录下来；开辟好新的空间后根据size和第一个指针重置第二个指针；根据第一个指针和开辟好空间的容量重置第三个指针。

push_back

	void push_back(const T& x)
	{
		//需不需要扩容
		if (_finish == _end)
		{
			//第一次容量为空
			reserve(capacity() == 0 ? 4 : capacity() * 2);
		}
		//尾插数据，移动指针
		*_finish = x;
		_finish++;
	}

尾插根据第二个和第三个指针判断容量的大小，是否需要扩容；注意：第一次扩容时使用三目操作符进行判断；

erase

	void /*iterator*/ erase(iterator pos)
	{
		assert(pos < _finish);
		iterator begin = pos + 1;
		//移动数据
		while (begin < _finish)
		{
			*(begin - 1) = *(begin);
			begin++;
		}
		//修改指针；
		_finish--;
		//return pos;
	}

resize

	void resize(size_t n , const T& val=T())
	{
		if (n < size())
		{
			//重置的大小小于当前大小
			//修改指针即可
			_finish = _start + n;
		}
		else
		{
			//两种情况
			//重置的大小小于大于当前容量  需要扩容
			//重置的大小小于小于当前容量  不用扩容直 接放数据
			if (n > capacity())
			{
				reserve(n);
			}
			while (_finish < _start + n)
			{
				*_finish = val;
				_finish++;
			}
		}
	}

insert

	void insert(iterator pos, const T& x)
	{
		//判断容量
		if (_finish == _end)
		{
			//记录旧空间的pos位置
			size_t sz = pos - _start;
			reserve(capacity() == 0 ? 4 : capacity() * 2);
			//在新空间中找到pos位置
			pos = _start + sz;
		}
		auto end = _finish - 1;
		while (end >= pos)
		{
			*(end + 1) == *end;
			end--;
		}
		*pos = x;
		_finish++;
	}

这里扩容后改指向旧空间pos是野指针，程序会崩溃；要在扩容前配合第一个指针记录此时的位置，扩容后进行重置。

operator [ ]

	//可读可写
    T& operator[](size_t pos)
	{
		return _start[pos];
	}
    //只读
	const T& operator[](size_t pos) const
	{
		return _start[pos];
	}

迭代器

    //可读可写
    iterator begin()
	{
		return _start;
	}
	iterator end()
	{
		return _finish;
	}
	//只读
    const_iterator begin()const
	{
		return _start;
	}
	const_iterator end()const
	{
		return _finish;
	}

size

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

capacity

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

今天对vector的介绍和底层模拟实现的分享到这就结束了，希望大家读完后有很大的收获，也可以在评论区点评文章中的内容和分享自己的看法。您三连的支持就是我前进的动力，感谢大家的支持！！！