C++中的vector怎么实现

今天小编给大家分享一下C++中的vector怎么实现的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

vector介绍

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();//无参构造
vector(size_t n,const val_type & val=val_type());//利用v个val初始化vector
vector(const val_type&val);//拷贝构造
template <class InputIterator>
vector (InputIterator first, InputIterator last)//可以用其他类的迭代器来初始化vector

当然，vector还可以直接用数组来填充：

迭代器：

begin();

end();非const对象正向迭代器；

begin() const;

end() const ;const对象正向迭代器；

在VS平台下，vector的迭代器并不是用原生指针来实现的，而是用了一种比较复杂的方式；

VS下vector的迭代器类型：

在g++版本下，迭代器主要采用原生指针的方式，我们下面模拟的时候也是借鉴这种方式！

容量空间：

size();//获取vector有效元素个数;
capacity();//获取vector当前容量;
empty();//判断vector是否为空；
resize(size_t n,const val_type &val=val_type());//设置vector的size大小，使用resize可能会引发扩容；
reserve(size_t n);//设置容量，只有当n>大于当前容量是才会增容；

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。

这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

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

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

增删查改：

push_back(const vay_type &val);//插入一个元素;
pop_back();//从尾部删除一个元素;
InputIterator find (InputIterator first, InputIterator last, const T& val)//这不是vector的成员函数，而是函数模板，用于在某段特定区间[first,last)查找val；找到了返回val的迭代器；找不到返回last；
iterator insert (iterator position, const value_type& val);//在pos位置之前插入数据，insert插入有代价尽量少用；
iterator erase (iterator position);//删除指定位置的数据；
swap（）//成员swap比模板swap快；
operator[]( size_type n);//[ ]重在运算符；

vector模拟实现及迭代器失效讲解

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
#include<string.h>
#include<algorithm>
namespace MySpace
{
	template <typename T>
	class vector
	{
	public:
		//迭代器
		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;
		}
	
		//构造函数和析构函数
		explicit vector() {}
		//由于泛型编程的出现，内置类型也必须支持默认构造函数
		//int a=int();//是编译器允许的
		//int*pa=int*();//直接使用编译器是不允许的，但是写出泛型编程时，编译器又允许了:T pa=T();//这是编译器允许的；
		//很奇怪对吧！
		explicit vector(size_t n,const T&val=T()) {
			reserve(n);
			for (size_t i = 0; i < n; i++)
				push_back(val);
			_finish = _start + n;
		}
	 explicit vector(int n, const T& val = T()) {
			reserve(n);
			for (size_t i = 0; i < (size_t)n; i++)
				push_back(val);
			_finish = _start + n;
		}
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			//memcpy(_start,v._start,v.size()*sizeof(T));//memcpy是字节拷贝，也就是浅拷贝！当T的类型是string一类的时候，就会出现！
			//v1、v2虽然_start、_finish、_end_of_storage 实现了深拷贝！但是他们里面的元素string，是用
			//memcpy拷贝过来的，也就是浅拷贝！也就造成了不同的string元素管理着同一块字符串；
			//当vector析构的时候，就会调用string的析构，就会造成对同一块空间释放两次！
			//为此，我们的vector元素之间也应该实现深拷贝！利用赋值运算符！
			for (const auto& x : v)
				push_back(x);
			_finish = _start + v.size();
		}

		//可以将任和迭代区间转换成vector元素！（前提是隐式类型转换支持）
		template<typename InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
				push_back(*(first++));
		}

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

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				iterator tmp = new T[n];
				//memcpy(tmp, _start, (_finish - _start) * sizeof(T));//这里不要用memcpy，memcpy是字节拷贝，也就是浅拷贝
				//对于T=string这样，里利用memcpy就会出现错误！
				for (size_t i = 0; i < size(); i++)
					tmp[i] = _start[i];
				size_t sz = _finish - _start;//提前记录一下元素个数
				delete[] _start;
				_start = tmp;
				//_finish = tmp + (_finish - _start);//注意此时的_start已经不在指向原来的那块快空间，此时_start==tmp
				//因此_finish还是等于原来的_finish没有改变,为了解决这个问题，我们可以提前记录一下sz;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}
		void resize(size_t n, const T& val = T())//const+引用对于匿名对象来说可以延长匿名对象的生命周期
		{
			if (n <= size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())//需要扩容
				{
					reserve(n);
				}
				for (size_t i = 0; i < n - size(); i++)
					_finish[i] = val;
				_finish += n - size();
			}
		}
		//capacity
		size_t size()const
		{
			return _finish - _start;
		}
		size_t capacity()const
		{
			return _end_of_storage - _start;
		}
		bool empty()const
		{
			return size() == 0;
		}
		void clear()
		{
			_finish = _start;
		}
		//访问
		T& operator[](size_t pos)
		{
			assert(pos >= 0 && pos < size());
			return _start[pos];
		}
		const T& operator[](size_t pos)const
		{
			assert(pos >= 0 && pos < size());
			return _start[pos];
		}
		//修改数据
		void push_back(const T& val)
		{
			if (_finish == _end_of_storage)//容量满了
			{
				//扩容
				reserve(_finish==nullptr?4:(_finish-_start)*2);
			}
			*(_finish) = val;
			_finish++;
		}
		void pop_back()
		{
			assert(empty() == false);
			_finish--;
		}
		iterator insert(iterator pos, const T& val)
		{
			if (_finish == _end_of_storage)//发生扩容过后，pos还是指向的原来的空间，pos是个野指针，需要修正pos
			{//在insert里面也就是这里会发生，迭代器失效!
				size_t gap = pos - _start;
				reserve(capacity() ? capacity() * 2 : 4);
				pos = _start + gap;//修正pos，使pos变成合法指针
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				end[1] = end[0];
				end--;
			}
			pos[0] = val;
			_finish++;
			return pos;//指向插入位置
		}

		iterator erase(iterator pos)//删除pos位置，返回删除位置的地址
		{
			assert(empty() == false);
			iterator end = pos + 1;
			while (end != _finish)
			{
				end[-1] = end[0];
				end++;
			}
			_finish--;
			return pos;
		}

		//交换
		void swap(const vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage,v._end_of_storage);
		}
		
		//重载赋值运算符
		vector<T>& operator=(const vector<T>& v)
	 	 {
       if(this!=&v)
       {
          clear();
          reserve(v.capacity());
          for(const auto&x:v)
            push_back(x);
          _finish=_start+v.size();
       }
       return *this;
     }

	private:
		iterator _start = nullptr;//开始位置
		iterator _finish=nullptr;//最后一个元素的下一个位置
		iterator _end_of_storage = nullptr;//表示当前容量的指针

	};
	void test8()
	{
		std::string str = "Hello World";
		vector<int> v(str.begin(), str.end());
		for (const auto& x : v)
			std::cout << x << " ";
			std::cout << std::endl;

	}
	void test7()
	{
		/*vector<int> v(10,6);
		vector<int> v2 = v;*/

		//vector<std::string> v(3, "112222222255522111");
		vector<std::string> v1 = v;//当T类型为自定义类型时会出现程序崩溃！//主要是因为出现了浅拷贝问题！！

		//v.push_back("2111111111111111");//要避免memcpy带来的浅拷贝危害！
		//v.push_back("333332111111111111111");
		vector<int> v1(3,10);
		vector<int> v2(4,19);
		vector<int> v3(5,6);

		vector<vector<int>> vv;
		vv.push_back(v1);//这里会出现报错，因为我们还没有实现vector<T>的赋值运算符
		vv.push_back(v2);
		vv.push_back(v3);
		//vector<vector<int>> vv2=vv;


	}
	void test6()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		for (size_t i = 0; i < v1.size(); i++)
			std::cout << (v1[i]) << " ";
		std::cout << std::endl;
	vector<int>::iterator pos = v1.begin() + 2;
		pos=v1.erase(pos);
		//*pos += 10;//这里也存在着迭代器失效的问题？从语法上我们认为pos指向的是一块有效空间，这没问题！
		//但是从逻辑上来说，pos却不一定是一块“合法”的空间：假如pos刚好是最后一个元素，erase过后pos与_finish相等
		//如果我们后续再访问pos位置的话就有点不合适了，在逻辑上我们认为pos是个不“合法”的位置，pos不应该访问！
		//为此，为了解决这个问题，vs版本下的vector给出了比较严格的限制，当我们使用erase过后的pos时直接报错！
		//g++下的erase过后的pos是允许使用的，但是这是不合理的！
		//因此我们一般认为erase过后的pos也是迭代器失效，解决办法就是接收一下erase的返回值！
		for (size_t i = 0; i < v1.size(); i++)
			std::cout << (v1[i]) << " ";
	}
	void test1()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

	}
	void test2()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		v.resize(3);
	}
	void test3()
	{
		 vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		for (size_t i = 0; i < v.size(); i++)
			std::cout << (v[i] *=10)<< std::endl;
	}
	void test5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		for (size_t i = 0; i < v.size(); i++)
			std::cout << (v[i] ) << " ";
		std::cout << std::endl;
		vector<int>::iterator pos = std::find(v.begin(),v.end(),3);
		if (pos != v.end())
		{
			pos=v.insert(pos,30);
			//(*pos)++;//这里也是个迭代器失效，虽然我们修正了，insert内部pos，
			//但是外部的pos还是指向的原来的空间，外部的pos还是个野指针，我们的pos是值传递，形参的改变不影响实参！
			//那么我们pos参数用引用可不可以?
			//答：语法上可以！但是实际用起来却不行！eg：insert(v.begin(),10);//如果pos是引用的话，程序直接报错
			//因为begin是值返回，insert相当于引用的一个临时对象，临时对象具有常性！（权限放大了）
			//也不要想着给pos加const解决（加了const，pos都修正不了了，迭代器失效的问题无法解决了）
			//因此我们在insert过后，最好不要再用pos值，要用也应该从新接收一下insert返回值！
			
			//为此vs为了我们使用失效的迭代器！当我们使用insert过后的pos时，就会直接报错！
		}
		(*pos) += 10;
		for (size_t i = 0; i < v.size(); i++)
			std::cout << (v[i]) << " ";
		std::cout << std::endl;
	}
	void test4()
	{
	
		std::vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		for (size_t i = 0; i < v.size(); i++)
			std::cout << (v[i]) << " ";
			std::cout << std::endl;
		std::vector<int>::iterator pos = std::find(v.begin(),v.end(),3);
		if (pos != v.end())
		{
			pos=v.insert(pos,30);
		}
		(*pos) += 10;
		for (size_t i = 0; i < v.size(); i++)
			std::cout << (v[i]) << " ";
		std::cout << std::endl;
		std::cout << typeid(std::vector<int>::iterator).name()<<std::endl;//vs版本下的vector迭代器不是使用的原生指针！
	}
}

以上就是“C++中的vector怎么实现”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。