【C++】vector

vector的介绍和使用 vector的介绍

vector是C++标准模板库中的部分内容，中文偶尔译作“容器”，但并不准确。它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。 [1]

如何理解这段话呢，可以把它想像成一个数组，这里面可以放任意类型的数据

如果是int，那就是一个整型数组

如果是char，那就有点类似string

它还可以是vecto类似，这就相当于是一个二维数组了...

vector的使用

vector - C++ Reference (cplusplus.com)

虽然是全英文，但有的游览器会自带翻译，这里说个大概用法：跟string差不多，创建类后用.函数名来使用

vector的定义

有以下几种：

vector()	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x);	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

一般常用的是无参和拷贝，因为数据的插入和删除也算比较简单的，所以构造并初始化和使用迭代器进行构造的也算比较少

vector iterator

这个在string里面是迭代器，用来遍历string用的，在vector里面使用的办法也一样，用来遍历vector

这里可以看图：

就是一个正向一个反向，其实这里用法跟string一样，不过还是演示一下：

    vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	vector::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it <<" ";
		++it;
	}
	cout << endl;
	return 0;

如上代码。创建了一个vector并插入了1234，并用迭代器进行打印，这里要记得++it，不然会死循环，打印效果：

这里要提一下，迭代器有两种，第一种是没有const的，这种是可以遍历的时候修改的，另一种带const的就是单纯的遍历

如果对应的vector是带有const修饰的，那编译器会自动调用带const的迭代器

不过这里要注意，如果是带有const的vector，那在迭代前面也要加上const，像这样：

vector::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}

不然会出现这样的错误；

因为普通的it的不带const的，它可以修改对应的值，而const的修饰就是为了不让修改，所以出现了权限放大的问题，这里要注意，带上const就好了，下面是效果的演示

vector的空间

这里大致看一下就好了，跟string其实很像，前面有不了解的可以去看前一篇我的string讲解

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

这里的用法也跟string一样，直接对象名.函数名就可以了

vector的常用操作

push_back	尾插
pop_back	尾删
find	查找
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[]	像数组一样访问

其实用法也很简单，这里大致示范一下：

vector迭代器失效问题

这个理解起来也很简单，这里可以先看图理解：

第一种情况：迭代器指向原本被释放的空间

一开始开创好了一块空间来放数据，假设这个时候我的放的数据又比较多，空间不够了，这里就要reserve调整一块空间，但是在遍历的时候，it还指向的是原空间，导致程序崩溃报错，这里看图

但此时，it还指向的是原空间，这就会导致出错

//开空间并初始化
vector v{1,2,3,4,5,6};

//创建it
auto it = v.begin();

//调整空间
v.assign(100, 8);

//打印
while(it != v.end())
{
cout<< *it << " " ;
++it;
}
cout< 
类似这里就会出现崩溃，因为v的begin和end已经变成了新的空间区域，但it还指向的是原本空间，而原本空间在开辟新空间后已经被释放掉，所以会崩溃报错 
解决办法：更新it的值即可 
第二种情况：迭代器的意义改变 
假设此时有一个vector里面有这样的几个数字： 
 
此时，我要对这个vector进行如下操作： 
在所有偶数前面加上20，其实这样也算简单，因为按照我们以前写的代码逻辑，只需要将偶数的位置由它后一个替换，然后++在判断即可，但是，这样就会出现问题： 
  
 
一开始it指向1，1不是偶数，所以不会动，但当it指向2的时候： 
  
我们知道it现在指向2，2是偶数，所以要在前面加上20： 
  
假设it已经成功在2的前面加上20了，从逻辑上来讲，这里应该是没有问题的，但是这里就会出现这样的情况： 
原本it指向的是2，但此时2的位置已经变成了20，2的位置已经改变，但it却指向原空间 
所以就会出现第二种情况：迭代器所指向的意义变了 
解决办法：重新修改迭代器指向即可 
------------ 
模拟实现 
目标 
namespace knous

{

	template

	class vector

	{

	public:

		// Vector的迭代器是一个原生指针

		typedef T* iterator;

		typedef const T* const_iterator;

		iterator begin();

		iterator end();

		const_iterator cbegin();

		const_iterator cend() const;



		// construct and destroy

		vector();

		vector(int n, const T& value = T());

		template

		vector(InputIterator first, InputIterator last);

		vector& operator= (vector v);

		~vector();

		// capacity

		size_t size() const;

		size_t capacity() const;

		void reserve(size_t n);

		void resize(size_t n, const T& value = T());



		///access///

		T& operator[](size_t pos);

		const T& operator[](size_t pos)const;



		///modify/

		void push_back(const T& x);

		void pop_back();

		void swap(vector& v);

		iterator insert(iterator pos, const T& x);

		iterator erase(iterator pos);

	private:

		iterator _start; // 指向数据块的开始

		iterator _finish; // 指向有效数据的尾

		iterator _endOfStorage; // 指向存储容量的尾

	};

} 
上面是之后会实现的东西，我们一点一点来，先将vector的类参数写出来： 
namespace knous

{

	template
	class vector
	{
	public:




	private:

	};

} 
从上往下看，逐步分析： 
因为vector是一个容器，它可以放任意类型，所以这里我们单纯的用int、char指针来构造显然是错误的，这里就要用到之前学到的模板，T可以是任意类型的数据，在这里接收到类型之后它会自动替换下面所有T的地方 
迭代器 
这里本来想给大家看一下源代码，但是觉得自己水平不够，所以就不献丑了 
我想说的是：vector里面的类型都是迭代器，没有之前在string里面的size、capacity之类的，它会有如下的三种指针： 
        iterator _start; // 指向数据块的开始

		iterator _finish; // 指向有效数据的尾

		iterator _endOfStorage; // 指向存储容量的尾 
既然我们要模拟实现，那这个iterator又是什么呢？ 
其实是由我们typedef定义的类型，这里就简单定义一下： 
namespace knous

{

	template
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;




	private:
		iterator _start; // 指向数据块的开始

		iterator _finish; // 指向有效数据的尾

		iterator _endOfStorage; // 指向存储容量的尾

	};

} 
这就是我们大致的模板，因为T是任意类型，所以T*就是任意类型的指针，让T*重定义为iterator方便我们之后好看，然后写一个const版本来应对其他情况 
一点一点来 
这里先写一个begin和end，因为比较简单： 
        iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			reruen _finish;
		}

		const_iterator cbegin()
		{
			reruen _start;
		}

		const_iterator cend() const
		{
			rerurn _finis;
		} 
构造 
我们知道类里面会自动一个构造函数，这里就浅浅的写一个： 
无参的，直接让对应的迭代器指向空即可 
vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
		} 
 
opeartor= 
vector& operator=(vector v)
		{
			swap(v);
			return *this;
		} 
这算一个现代写法，直接在形参那里构造一个，然后跟这个构造的交换空间，这里再写一个交换函数； 
void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);

		} 
这里因为交换函数标准头文件已经有了，就不用自己写了 
 
给一个长度和一个初始值构造 
vector(int n, const T& value = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				push_back(value);
			}
		} 
先调整空间，然后插入即可 
 
用一个迭代器区间来初始化另一个 
		template < class Iterator >
			vector(Iterator first,Iterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			while (first != end)
			{
				push_back(*first);
				++*first;
			}
		} 
因为无法确定这个迭代器区间类型，所以这里还是要用另一个模板来接收然后初始化尾插 
 
基本的操作函数 
    //重载方括号
     T& operator[](size_t pos)；

    const T& operator[](size_t pos)const； 

   // capacity

    size_t size() const ；

    size_t capacity() const；

    void reserve(size_t n)；

    void resize(size_t n, const T& value = T())；



    void push_back(const T& x);

    void pop_back();

    iterator insert(iterator pos, const T& x);

    iterator erase(Iterator pos); 
顺着来： 
opeartor[] 
两个版本是因为如果只要遍历就可以调用const防止修改，如果要修改就会调用另外一个： 
        T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];
		}

		const T& operator[](size_t pos)const
		{
			assert(pos < size());
			return _start[pos];
		} 
 
size、capacity、resize、reserve 
 
		size_t capacity() const
		{
			_endOfStorage - _start;
		}

		void reserve(size_t n)
		{
			size_t size = size();

			if (n > capacity())
			{
				if (_start)
				{
					T* tmp = new T[n];
					for (size_t i = ; i < size(); i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
			}
			_finish = _start + size;
			_endOfStorage = _start + n;
		}

		void resize(size_t n, const T& value = T())
		{
			if (n>capacity())
			{
				reserve(n);
			}
			else if (n>size())
			{
					while (_finish < _start + n)
					{
						*_finish = value;
						++_finish;
					}
			}
			else
			{
				_finish = _start + n;
			}
		} 
尾插和尾删 
         void push_back(const T& x)
		{
			if (capacity() == 0)
			{
				int new_capacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(new_capacity);
			}
			*_finsh = x;
			_finish++;
		}

		void pop_back()
		{
			if (_finish)
				_finish--;
		} 
先判断容量，然后直接插入或者删除 
随机插入和删除: 
这里算是比较重要的地方，插入我们要先记住pos的位置，防止开新空间后pos指向旧空间出现迭代器失效的问题 
删除就直接替换就可以 
		iterator insert(iterator pos, const T& x)
		{
			assert(pos <= _finish && pos >= _start);

			//看容量
			if (_finish == _endOfStorage)
			{

				//记录pos
				size_t size = pos - _start;
				size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(new_capacity);

				pos = _start + size;
			}


			//挪数据
			iterator it = _finish;
			while (it != pos)
			{
				*(it) = *(it-1);
				it--;
			}

			//填数据
			*pos = x;
			_finish++;
			return pos;
		}

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

			iterator it = pos;
			while (it + 1 != _finish)
			{
				*it = *(it+1);
				it++;
			}

			--_finish;
			return pos;
		} 
------ 
这里放上全部代码： 
namespace knous

{

	template
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator cbegin()
		{
			reruen _start;
		}

		const_iterator cend() const
		{
			rerurn _finis;
		}

		void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);

		}


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

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

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


			~vector()
			{
				delete[] _start;
				_start = _finish = _endOfStorage = nullptr;
			}

		vector& operator=(vector v)
		{
			swap(v);
			return *this;
		}

		// capacity

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

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

		void reserve(size_t n)
		{
			size_t sz = size();

			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < size(); i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
			}
			_finish = _start + sz;
			_endOfStorage = _start + n;
		}

		void resize(size_t n, const T& value = T())
		{
			if (n>capacity())
			{
				reserve(n);
			}
			else if (n>size())
			{
					while (_finish < _start + n)
					{
						*_finish = value;
						++_finish;
					}
			}
			else
			{
				_finish = _start + n;
			}
		}


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

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


		void push_back(const T& x)
		{
			if (_finish == _endOfStorage)
			{
				int new_capacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(new_capacity);
			}
			*_finish = x;
			_finish++;
		}

		void pop_back()
		{
			if (_finish)
				_finish--;
		}

		iterator insert(iterator pos, const T& x)
		{
			assert(pos <= _finish && pos >= _start);

			//看容量
			if (_finish == _endOfStorage)
			{

				//记录pos
				size_t size = pos - _start;
				size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(new_capacity);

				pos = _start + size;
			}


			//挪数据
			iterator it = _finish;
			while (it != pos)
			{
				*(it) = *(it-1);
				it--;
			}

			//填数据
			*pos = x;
			_finish++;
			return pos;
		}

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

			iterator it = pos;
			while (it + 1 != _finish)
			{
				*it = *(it+1);
				it++;
			}

			--_finish;
			return pos;
		}


	private:
		iterator _start; // 指向数据块的开始

		iterator _finish; // 指向有效数据的尾

		iterator _endOfStorage; // 指向存储容量的尾

	};

} 
望这篇文章对您有所帮助

【C++】vector

C/C++/C#相关栏目本月热门文章