C++中的vector怎么實(shí)現(xiàn)

今天小編給大家分享一下C++中的vector怎么實(shí)現(xiàn)的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

vector介紹

vector文檔

1.vector是表示可變大小數(shù)組的序列容器。

2.就像數(shù)組一樣，vector也采用的連續(xù)存儲(chǔ)空間來存儲(chǔ)元素。也就是意味著可以采用下標(biāo)對(duì)vector的元素進(jìn)行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動(dòng)態(tài)改變的，而且它的大小會(huì)被容器自動(dòng)處理。

3.本質(zhì)講，vector使用動(dòng)態(tài)分配數(shù)組來存儲(chǔ)它的元素。當(dāng)新元素插入時(shí)候，這個(gè)數(shù)組需要被重新分配大小為了增加存儲(chǔ)空間。其做法是，分配一個(gè)新的數(shù)組，然后將全部元素移到這個(gè)數(shù)組。就時(shí)間而言，這是一個(gè)相對(duì)代價(jià)高的任務(wù)，因?yàn)槊慨?dāng)一個(gè)新的元素加入到容器的時(shí)候，vector并不會(huì)每次都重新分配大小。

4.vector分配空間策略：vector會(huì)分配一些額外的空間以適應(yīng)可能的增長，因?yàn)榇鎯?chǔ)空間比實(shí)際需要的存儲(chǔ)空間更大。不同的庫采用不同的策略權(quán)衡空間的使用和重新分配。但是無論如何，重新分配都應(yīng)該是對(duì)數(shù)增長的間隔大小，以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的。

5.因此，vector占用了更多的存儲(chǔ)空間，為了獲得管理存儲(chǔ)空間的能力，并且以一種有效的方式動(dòng)態(tài)增長。

6.與其它動(dòng)態(tài)序列容器相比（deque, list and forward_list）， vector在訪問元素的時(shí)候更加高效，在末尾添加和刪除元素相對(duì)高效。對(duì)于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統(tǒng)一的迭代器和引用更好

vector常見函數(shù)介紹

構(gòu)造函數(shù)：

vector();//無參構(gòu)造
vector(size_t n,const val_type & val=val_type());//利用v個(gè)val初始化vector
vector(const val_type&val);//拷貝構(gòu)造
template <class InputIterator>
vector (InputIterator first, InputIterator last)//可以用其他類的迭代器來初始化vector

當(dāng)然，vector還可以直接用數(shù)組來填充：

迭代器：

begin();

end();非const對(duì)象正向迭代器；

begin() const;

end() const ;const對(duì)象正向迭代器；

在VS平臺(tái)下，vector的迭代器并不是用原生指針來實(shí)現(xiàn)的，而是用了一種比較復(fù)雜的方式；

VS下vector的迭代器類型：

在g++版本下，迭代器主要采用原生指針的方式，我們下面模擬的時(shí)候也是借鑒這種方式！

容量空間：

size();//獲取vector有效元素個(gè)數(shù);
capacity();//獲取vector當(dāng)前容量;
empty();//判斷vector是否為空；
resize(size_t n,const val_type &val=val_type());//設(shè)置vector的size大小，使用resize可能會(huì)引發(fā)擴(kuò)容；
reserve(size_t n);//設(shè)置容量，只有當(dāng)n>大于當(dāng)前容量是才會(huì)增容；

capacity的代碼在vs和g++下分別運(yùn)行會(huì)發(fā)現(xiàn)，vs下capacity是按1.5倍增長的，g++是按2倍增長的。

這個(gè)問題經(jīng)常會(huì)考察，不要固化的認(rèn)為，vector增容都是2倍，具體增長多少是根據(jù)具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL。

reserve只負(fù)責(zé)開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價(jià)缺陷問題。

resize在開空間的同時(shí)還會(huì)進(jìn)行初始化，影響size。

增刪查改：

push_back(const vay_type &val);//插入一個(gè)元素;
pop_back();//從尾部刪除一個(gè)元素;
InputIterator find (InputIterator first, InputIterator last, const T& val)//這不是vector的成員函數(shù)，而是函數(shù)模板，用于在某段特定區(qū)間[first,last)查找val；找到了返回val的迭代器；找不到返回last；
iterator insert (iterator position, const value_type& val);//在pos位置之前插入數(shù)據(jù)，insert插入有代價(jià)盡量少用；
iterator erase (iterator position);//刪除指定位置的數(shù)據(jù)；
swap（）//成員swap比模板swap快；
operator[]( size_type n);//[ ]重在運(yùn)算符；

vector模擬實(shí)現(xiàn)及迭代器失效講解

#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;
		}
	
		//構(gòu)造函數(shù)和析構(gòu)函數(shù)
		explicit vector() {}
		//由于泛型編程的出現(xiàn)，內(nèi)置類型也必須支持默認(rèn)構(gòu)造函數(shù)
		//int a=int();//是編譯器允許的
		//int*pa=int*();//直接使用編譯器是不允許的，但是寫出泛型編程時(shí)，編譯器又允許了:T pa=T();//這是編譯器允許的；
		//很奇怪對(duì)吧！
		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是字節(jié)拷貝，也就是淺拷貝！當(dāng)T的類型是string一類的時(shí)候，就會(huì)出現(xiàn)！
			//v1、v2雖然_start、_finish、_end_of_storage 實(shí)現(xiàn)了深拷貝！但是他們里面的元素string，是用
			//memcpy拷貝過來的，也就是淺拷貝！也就造成了不同的string元素管理著同一塊字符串；
			//當(dāng)vector析構(gòu)的時(shí)候，就會(huì)調(diào)用string的析構(gòu)，就會(huì)造成對(duì)同一塊空間釋放兩次！
			//為此，我們的vector元素之間也應(yīng)該實(shí)現(xiàn)深拷貝！利用賦值運(yùn)算符！
			for (const auto& x : v)
				push_back(x);
			_finish = _start + v.size();
		}

		//可以將任和迭代區(qū)間轉(zhuǎn)換成vector元素?。ㄇ疤崾请[式類型轉(zhuǎn)換支持）
		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是字節(jié)拷貝，也就是淺拷貝
				//對(duì)于T=string這樣，里利用memcpy就會(huì)出現(xiàn)錯(cuò)誤！
				for (size_t i = 0; i < size(); i++)
					tmp[i] = _start[i];
				size_t sz = _finish - _start;//提前記錄一下元素個(gè)數(shù)
				delete[] _start;
				_start = tmp;
				//_finish = tmp + (_finish - _start);//注意此時(shí)的_start已經(jīng)不在指向原來的那塊快空間，此時(shí)_start==tmp
				//因此_finish還是等于原來的_finish沒有改變,為了解決這個(gè)問題，我們可以提前記錄一下sz;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}
		void resize(size_t n, const T& val = T())//const+引用對(duì)于匿名對(duì)象來說可以延長匿名對(duì)象的生命周期
		{
			if (n <= size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())//需要擴(kuò)容
				{
					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];
		}
		//修改數(shù)據(jù)
		void push_back(const T& val)
		{
			if (_finish == _end_of_storage)//容量滿了
			{
				//擴(kuò)容
				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)//發(fā)生擴(kuò)容過后，pos還是指向的原來的空間，pos是個(gè)野指針，需要修正pos
			{//在insert里面也就是這里會(huì)發(fā)生，迭代器失效!
				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);
		}
		
		//重載賦值運(yùn)算符
		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;//最后一個(gè)元素的下一個(gè)位置
		iterator _end_of_storage = nullptr;//表示當(dāng)前容量的指針

	};
	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;//當(dāng)T類型為自定義類型時(shí)會(huì)出現(xiàn)程序崩潰！//主要是因?yàn)槌霈F(xiàn)了淺拷貝問題?。?

		//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);//這里會(huì)出現(xiàn)報(bào)錯(cuò)，因?yàn)槲覀冞€沒有實(shí)現(xiàn)vector<T>的賦值運(yùn)算符
		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;//這里也存在著迭代器失效的問題？從語法上我們認(rèn)為pos指向的是一塊有效空間，這沒問題！
		//但是從邏輯上來說，pos卻不一定是一塊“合法”的空間：假如pos剛好是最后一個(gè)元素，erase過后pos與_finish相等
		//如果我們后續(xù)再訪問pos位置的話就有點(diǎn)不合適了，在邏輯上我們認(rèn)為pos是個(gè)不“合法”的位置，pos不應(yīng)該訪問！
		//為此，為了解決這個(gè)問題，vs版本下的vector給出了比較嚴(yán)格的限制，當(dāng)我們使用erase過后的pos時(shí)直接報(bào)錯(cuò)！
		//g++下的erase過后的pos是允許使用的，但是這是不合理的！
		//因此我們一般認(rèn)為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)++;//這里也是個(gè)迭代器失效，雖然我們修正了，insert內(nèi)部pos，
			//但是外部的pos還是指向的原來的空間，外部的pos還是個(gè)野指針，我們的pos是值傳遞，形參的改變不影響實(shí)參！
			//那么我們pos參數(shù)用引用可不可以?
			//答：語法上可以！但是實(shí)際用起來卻不行！eg：insert(v.begin(),10);//如果pos是引用的話，程序直接報(bào)錯(cuò)
			//因?yàn)閎egin是值返回，insert相當(dāng)于引用的一個(gè)臨時(shí)對(duì)象，臨時(shí)對(duì)象具有常性?。?quán)限放大了）
			//也不要想著給pos加const解決（加了const，pos都修正不了了，迭代器失效的問題無法解決了）
			//因此我們在insert過后，最好不要再用pos值，要用也應(yīng)該從新接收一下insert返回值！
			
			//為此vs為了我們使用失效的迭代器！當(dāng)我們使用insert過后的pos時(shí)，就會(huì)直接報(bào)錯(cuò)！
		}
		(*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怎么實(shí)現(xiàn)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請關(guān)注億速云行業(yè)資訊頻道。