STL容器—vector的使用及模拟實作

一.vector的介紹。

vector是表示可變大小數組的序列容器。
就像數組一樣，vector也采用的連續存儲空間來存儲元素。也就是意味着可以采用下标對vector的元素進行通路，和數組一樣高效。但是又不像數組，它的大小是可以動态改變的，而且它的大小會被容器自動處理。
本質講，vector使用動态配置設定數組來存儲它的元素。當新元素插入時候，這個數組需要被重新配置設定大小為了增加存儲空間。其做法是，配置設定一個新的數組，然後将全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新配置設定大小。
vector配置設定空間政策：vector會配置設定一些額外的空間以适應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的政策權衡空間的使用和重新配置設定。但是無論如何，重新配置設定都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的複雜度完成。
是以，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動态增長。
與其它動态序列容器相比（deques, lists and forward_lists）， vector在通路元素的時候更加高效，在末尾添加和删除元素相對高效。對于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists統一的疊代器和引用更好。

二.vector的使用。

vector的定義：

vector()（重點）：無參構造。
vector（size_type n, const value_type& val = value_type())：構造并初始化n個val。
vector (const vector& x)：重點）拷貝構造。
vector (InputIterator first, InputIterator last)：使用疊代器進行初始化構造。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> vt1;
	vector<int> vt2(10, 2);//10個空間，初始化為2
	vector<int> vt3(vt2.begin(), vt2.end());//區間構造。
	vector<int> vt4(vt2);//拷貝構造。
	for (auto &e : vt2)
		cout << e <<" " ;
	cout << endl;

	for (vector<int>::iterator it = vt3.begin(); it != vt3.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	for (auto it = vt4.begin(); it != vt4.end(); ++it)
		cout << *it << " ";
	cout << endl;

	return 0;
}

vector iterator 的使用：

begin +end（重點）：

擷取第一個資料位置的iterator/const_iterator，擷取最後一個資料的下一個位置的iterator/const_iterator。
rbegin + rend：擷取最後一個資料位置reverse_iterator，擷取第一個資料前一個位置的reverse_iterator。

STL容器—vector的使用及模拟實作

#include<iostream>
#include<vector>
int main()
{
	vector<int> vt{ 1, 2, 3, 4 };//c++11初始化清單


	vector<int>::iterator it = vt.begin();//順序列印
	while (it != vt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	it = vt.begin();//疊加器的修改
	while (it != vt.end())
	{
		*it *= 2;//擴大二倍
		++it;
	}

	vector<int>::reverse_iterator rit = vt.rbegin();//反向列印
	while (rit != vt.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;

	return 0;
}

vector空間增長問題：

size ：擷取資料個數
capacity ：擷取容量大小
empty ：判斷是否為空
resize（重點）：改變vector的size
reserve （重點）：改變vector放入capacity

using namespace std;

int main()
{
	vector<int> vt;
	cout << vt.empty() << endl;//1 - kong 0 - feikong
	cout <<"size= "<< vt.size() << endl;
	vt.resize(5,2);//修改大小
	vt.reserve(10);//修改容量

	cout << "capacity = "<<vt.capacity() << endl;
	cout << "size= " << vt.size() << endl;
	for (int i = 0; i < 20; ++i)
	{
		vt.push_back(i);
		cout << "vt[" << i << "]=" << vt.capacity() << endl;
	}
	cout << "size = " << vt.size() << endl;
	cout << vt.empty() << endl;//1 - kong 0 - feikong
	return 0;
}

vector 增删查改：

push_back:（重點）尾插
pop_back :（重點）尾删
find :查找。（注意這個是算法子產品實作，不是vector的成員接口）
insert: 在position之前插入val
erase 删除position位置的資料
swap 交換兩個vector的資料空間
operator[] : （重點）像數組一樣通路

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	vector<int>::iterator it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	v.push_back(5);//尾插
	v.push_back(6);//尾插

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

	v.pop_back();//尾部删除

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

	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	// 在pos位置之前插入30
	v.insert(pos, 30);

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

	//找3位置的iostream
	pos = find(v.begin(), v.end(), 30);
	// 删除pos位置的資料
	v.erase(pos);

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

	vector<int> vt{ 5, 6, 7, 8 };
	
	v.swap(vt);//交換vt 與 v 兩空間的資料

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

	return 0;
}

vector 疊代器失效問題：

删除：由于删除pos處疊代器，++it會導緻程式崩潰
插入：由于查入可能會導緻擴容，進而釋放原空間，導緻疊加器失效。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int a[] = { 1, 2, 3, 4 };

	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 使用find查找3所在位置的iterator
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);

	// 删除pos位置的資料，導緻pos疊代器失效。
	v.erase(pos);
	//cout << *pos << endl; // 此處會導緻非法通路

	// 在pos位置插入資料，導緻pos疊代器失效。
	// insert會導緻疊代器失效，是因為insert可
	// 能會導緻增容，增容後pos還指向原來的空間，而原來的空間已經釋放了。
	pos = find(v.begin(), v.end(), 3);
	v.insert(pos, 30);
	//cout << *pos << endl; // 此處會導緻非法通路
	return 0;
}

舉例：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	// 實作删除v中的所有偶數
	// 下面的程式會崩潰掉，如果是偶數，erase導緻it失效
	// 對失效的疊代器進行++it，會導緻程式崩潰
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}
	// 以上程式要改成下面這樣，erase會傳回删除位置的下一個位置
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);
		else
			++it;
	}
	return 0;
}

三.vector的模拟實作。

#include<iostream>
#include<assert.h>
#include<vector>
//#include<string>
using namespace std;

namespace ice
{
	template<class T>
	class vector
	{
	public:
		// Vector的疊代器是一個原生指針
		typedef T* iterator;//疊代器
		typedef const T* const_iterator;//常疊代器
		iterator begin() 
		{ 
			return _start; 
		}
		iterator end() 
		{ 
			return _finish;
		}
		const_iterator cbegin()const 
		{ 
			return _start; 
		}
		const_iterator cend() const 
		{ 
			return _finish; 
		}
		// construct and destroy
		vector()//構造空vector
			: _start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{}
		vector(int n, const T& value = T())//構造n個空間
			: _start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			reserve(n);
			while (n--)
			{
				push_back(value);
			}
		}
		// 如果使用iterator做疊代器，會導緻初始化的疊代器區間[first,last)隻能是vector的疊代器
		// 重新聲明疊代器，疊代器區間[first,last]可以是任意容器的疊代器
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)//區間構造
		{
			reserve(last - first);
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		vector(const vector<T>& v)//拷貝構造
			: _start(nullptr)
			  , _finish(nullptr)
			  , _endOfStorage(nullptr)
		{
			reserve(v.capacity());
			iterator it = begin();
			const_iterator vit = v.cbegin();
			while (vit != v.cend())
			{
				*it++ = *vit++;
			}
			_finish = _start + v.size();
			_endOfStorage = _start + v.capacity();
		}

		vector<T>& operator= (vector<T> v)//指派語句
		{
			swap(v);
			return *this;
		}

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

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

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

		void reserve(size_t n)//設定容量
		{
			if (n > capacity())
			{
				size_t oldSize = size();
				T* tmp = new T[n];
				//if (_start)
				// memcpy(tmp, _start, sizeof(T)*size);
				if (_start)
				{
					for (size_t i = 0; i < oldSize; ++i)
						tmp[i] = _start[i];
				}
				_start = tmp;
				_finish = _start + size;
				_endOfStorage = _start + n;
			}
		}

		void resize(size_t n, const T& value = T())//設定大小
		{
			// 1.如果n小于目前的size，則資料個數縮小到n
			if (n <= size())
			{
				_finish = _start + n;
				return;
			}
			// 2.空間不夠則增容
			if (n > capacity())
				reserve(n);
			// 3.将size擴大到n
			iterator it = _finish;
			iterator _finish = _start + n;
			while (it != _finish)
			{
				*it = value;
				++it;
			}
		}

		T& operator[](size_t pos)//重載[]
		{ 
			return _start[pos];
		}

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

		void push_back(const T& x)
		{ 
			insert(end(), x); 
		}
		void pop_back()
		{ 
			erase(--end()); 
		}

		void swap(vector<T>& v)
		{
			swap(_start, v._start);
			swap(_finish, v._finish);
			swap(_endOfStorage, v._endOfStorage);
		}
		iterator insert(iterator pos, const T& x)//在pos處插入x值
		{
			assert(pos <= _finish);
			// 空間不夠先進行增容
			if (_finish == _endOfStorage)
			{
				size_t size = size();
				size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
				reserve(newCapacity);
				// 如果發生了增容，需要重置pos
				pos = _start + size;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
			return pos;
		}

		iterator erase(Iterator pos)//删除pos處的值
		{
			// 挪動資料進行删除
			iterator begin = pos + 1;
			while (begin != _finish) {
				*(begin - 1) = *begin;
				++begin;
			}
			--_finish;
			return pos;
		}
	private:
		iterator _start; // 指向資料塊的開始
		iterator _finish; // 指向有效資料的尾
		iterator _endOfStorage; // 指向存儲容量的尾
	};
}

測試代碼大家可以進行自我嘗試。。。

STL容器—vector的使用及模拟實作

一.vector的介紹。

二.vector的使用。

三.vector的模拟實作。

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述