【C++修炼秘籍】Vector深度剖析

【C++修炼秘籍】STL-Vector

??心有所向，日复一日，必有精进

??专栏《C++修炼秘籍》

??作者：沂沐沐

??如果有错误，烦请指正，如有疑问可私信联系；

---

目录

---

前言

vector的数据安排以及操作方式，与array非常相似，就像数组一样，vector采用连续的存储空间，可以像数组一样的随机访问，但是又不像数组一样，它的大小是可以随意改变的，而且是自动处理；有了vector后，相比于C语言的数组使用要方便许多，接下来让我们深入了解一下；

---

一、vector介绍

vector动态开辟空间，是可变大变小的数组序列容器；

像数组一样随机访问；

vector的动态分配策略：

分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小
所以vector在对空间进行管理的时候扩容一般是异地扩容，代价比较高，尽量避免扩容减少扩容，缩容是几乎不可能缩容的；但是有缩容函数

shrink_to_fit（）缩容函数（不建议使用、代价很大，异地缩容；）

例如：

reserve不会缩容，缩容是有代价的，以空间换时间；

resize（）不会缩容，只是改size；

vector<char>和string 是有一定区别：没有“\0",接口不一样；

二、vector的使用/接口介绍

vector的构造

(constructor)构造函数声明	接口说明
vector()（重点）	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x); （重点）	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

vector迭代器

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

迭代器我们可以知道他可以遍历STL的容器，vector也可以使用[]像数组那样访问，但是List地址不连续怎么像数组那样访问；

?下面是vector的三种访问方式：

vector<int> vv = {2,3,5,7,1,5,0};
	vector<int>::iterator it = vv.begin();
	cout << "迭代器方式" << endl;
	while (it != vv.end())//迭代器方式
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << "[]访问方式" << endl;

	for (int i = 0; i < vv.size(); i++)//[]访问方式
	{
		cout << vv[i] << " ";
	}
	cout << endl;
	cout << "范围for方式" << endl;
	for (auto e : vv)//范围for方式
	{
		cout << e << " ";
	}

范围for其实底层就是对迭代器的简单替代；?

vector 空间管理

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
reserve （重点）	改变vector的capacity

resize；

void resize (size_type n, value_type val = value_type());

这里使用的是匿名对象，value_type()，如果使用其他初始化，如果是一个自定义类型的，会造成一些问题。

resize要分成三种情况：

需要扩容加填数据；

不需扩容，只需要填数字

不需扩容和填数据

vector的增容机制

大概是1.5倍的增容，这是微软编译器的，gcc大概的扩容是2倍大多数，都是二倍；

?为什么扩容二倍？

每次扩容少了会导致扩容频繁；

每次扩多了就用不完，存在浪费；

vector 增删查改

vector增删查改	接口说明
push_back（重点）	尾插
pop_back （重点）	尾删
find	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[] （重点）	像数组一样访问

at和[]功能上是一样的，真正的区别：[]是直接用断言检查；at是一个成员函数，而at报错是抛出异常；而异常是可以被捕获的；

断言会有一个坑：release下面断言失效；断言时一般是debug就要发现的问题，如果debug没有发现，问题会很大。

?

三、vector深度剖析+模拟实现

vector的元素是指针：

private:?? ??? ?
?? ??? ?iterator _start;
?? ??? ?iterator _finish;
?? ??? ?iterator ?_endofstorage;

?

为什么采用指针的方式，模拟实现后解会体会到，使用指针的好处；

构造函数

vector()（重点）

无参构造

        vector() 
			:_start(nullptr),
			_finish(nullptr),
			_endofstorage(nullptr)
		{}

vector（size_type n, const value_type& val = value_type()）

构造并初始化n个val

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

???这里有些问题为什么这里要实现一个size_t和int两个函数呢？

其实和下面的迭代器构造有一定的关系；假如我们把int类型函数删掉如

这是因为模板匹配会匹配最合适的，size_t,int;和模板来说，模板是最合适的，所以要在实现一个，这样就最匹配了。

vector (InputIterator first, InputIterator last);

使用迭代器进行初始化构造

        template<class InputIterator>
		vector(InputIterator first, InputIterator last) 
			: _start(nullptr),
			_finish(nullptr),
			_endofstorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		
		}

vector (const vector& x);?

拷贝构造

vector(const vector<T>& v)//拷贝构造
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end());
			swap(tmp);
		}
		vector<T>& operator=(vector<T> val){//看清楚再写！！！！
			swap(val);
			return *this;
		}

??代码复用真的好好?

赋值运算符重载?

		vector<T>& operator=(vector<T> val){//看清楚再写！！！！我这里写错了
        //我怎么测都不对，最后烦死了才看到参数写错了想抽自己
			swap(val);
			return *this;
		}

迭代器?

begin + end（重点）

获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator

        typedef T* iterator;
		typedef const T* const_iterator;

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

迭代器这里实现的就是个原生指针；这里其实就体现出来元素设计成指针的好处了；?

空间管理

reserve （重点）

改变vector的capacity

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

				_start = newcapacity;
				_finish = _start + Oldsize;
				_endofstorage = _start + n;
			}
		}

?这里一开始使用的是memcpy是会出现问题，这个问题后面解决；?

?memcpy源内存地址的起始位置开始拷贝若干个字节到目标内存地址中

resize（重点）

改变vector的size

//resize;
		void resize(int n, T val = T()){
			if (n > capacity())//扩容+填充
			{
				reserve(n);

			}
			//size肯定比capacity小
			if (n > size())//填充
			{
				while (_finish < _start + n)
				{
					*_finish = val;//忘记解引用了
					++_finish;
				}
			}
			else//缩小但是不缩容
			{
				_finish = _start + n;
			}
		}

size	获取数据个数
capacity	获取容量大小
empty	判断是否为空

bool empty()const
		{
			return _finish == _start;
		}
		size_t size()const{
			return _finish - _start;
		}
		size_t capacity()const{

			return _endofstorage - _start;
		}

clear

清空

	void clear()
		{
			_finish = _start;
		}

clear也不动空间

clear _finish=_start不清空间，如果直接start=nullptr空间泄露

增删改查

增 push_back不直接头插，数组谁会头插啊？？万一真头插insert；

删 pop_back、erase

查 vector没有find成员 ，算法库里的find；

改 迭代器+[]

push_back（重点）

尾插

        void push_back(const T& val){
			//if (_finish == _endofstorage)reserve(capacity() + 1);
			if (_finish == _endofstorage)//为了防止频繁开辟空间而且一般是开辟二倍的空间
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}
			*_finish = val;
			++_finish;
		}

?这里一开始使用的是memcpy是会出现问题，这个问题后面解决；

push_back是否会开辟空间呢？——开辟滴；直接复用reserve；

memcpy源内存地址的起始位置开始拷贝若干个字节到目标内存地址中

pop_back （重点）

尾删

    void pop_back()
		{
			assert(!empty());
			--_finish;

		}

迭代器失效问题

insert

在position之前插入val

存在迭代器失效的问题?

主要是涉及数据的挪动问题，vector类似数组，像数组一样插入数据要向后挪动数据，迭代器而是一个原生指针，挪动数据必然会导致迭代器失效；

看下库里能空插入吗用insert还是直接断言——能；

//insert;//存在迭代器失效的问题
		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			//涉及到数据挪动的数据
			if (_start == _endofstorage)
			{
				size_t n = pos - _start;
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + n;

			}

erase

删除position位置的数据

?在earse操作后

在V2013下迭代器失效，直接断言错误

g++4.8迭代器不报错误 ，但是在极端场景，譬如删除最后一个数据报错

至于为什么不报错但是因为底层实现不一样，迭代器实现，VS下实现是是函数调用，g++是原生指针

我们统一认为失效，所以使用完erase后就不要用迭代器；

本文模拟实现是用的g++的方式；

最后用一个返回值来更新迭代器来解决问题，但是已经指向删除数据后最后一个；

//erase
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			//数据挪动
			assert(!empty());
			iterator end = pos+1;
			while (end < _finish)
			{
				*(end-1) = *end ;
				++end;
			}
			--_finish;
			return  pos;
		}

C语言使用二维数组

怎么malloc二维数组，要先开一个一维数组

 int **pp=(int **)malloc(sizeof(int*)*N);`
 ? ? ? ?for(int i = 0;i<m;i++){
 ? ? ? ? ? ?pp[i] = malloc//伪代码
 ? ? ?  }

释放的时候还是要一个一个释放；

而C++开辟二维数组来使用：

vector<vector<int>> vv

就是vector里面是vector<int>的对象；

vv.size();
?
for(size_t i = 0;i<vv.size();i++
?
{
?
    vv[i].szie(i+1,0);
    vv[i][0] = vv[i][vv[i].size()-1] = 1;//这里的[]是operator[]是函数调用，
                                //执行一个[]返回的是里面的vector对象，
                                //所以继续调用[]和二维数组的访问不太一样；
}

memcpy浅拷贝问题?

这里有个大问题哦

1、memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2.、如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

vector<vector<int>>去扩容

//浅拷贝memcpy是浅拷贝；

如果是memcpy简答浅拷贝就像下图理解：

?

我们发现也就是vector里面还是一块空间；

所以说不能用memcpy哦！

四、一些注意点?

如果代码有问题，可以使用排除法，缩小范围

1、只读的函数接口：const；

2、只写接口函数：非const；

3、可读可写：const+非const 例如operator[]

assign：将n个value进行赋值，也可以支持区间赋值（迭代区间迭代区间一般左闭右开）。

find使用algorithm库里的；

find在<algorithm>头文件里

---

总结

STL的vector是开篇之作，极大的方便的使用，vector的学习会使得接下来的容器学习变的方便，请接下来，加油一起学习！