【C++】使用vector和模擬其實現-創(chuàng)新互聯(lián)

文章目錄

- 1、vector的使用
- - 1.1 vector的構造、拷貝構造與迭代器
  - 1.2 vector的空間查詢和隨機訪問
  - 1.2 vector的增刪查改
- 2、vector的模擬實現
- - 2.1 vector的迭代器
  - 2.2 vector的結構構建
  - 2.4 vector的構造和拷貝構造
  - 2.4 vector的增刪

你所需要的網站建設服務，我們均能行業(yè)靠前的水平為你提供.標準是產品質量的保證，主要從事成都網站制作、網站建設、外貿網站建設、企業(yè)網站建設、移動網站建設、網頁設計、高端網站設計、網頁制作、做網站、建網站。創(chuàng)新互聯(lián)公司擁有實力堅強的技術研發(fā)團隊及素養(yǎng)的視覺設計專才。1、vector的使用

C++中的vector和C數據結構中的動態(tài)順序表是相似的。

vector屬于C++STL中的容器，STL在主流上有PJ版本（Windows Visual C++采用，可讀性較差）、SGI（被Linux采用，可移植性好，閱讀性也高）等。

這里的使用在VS環(huán)境下進行，后續(xù)模擬實現參考SGI版本。

值得注意的是，因為類模板的出現，容器中如vector，只是一個類模板，而真正的類需要實例化，如vector，所以定義一個vector對象，應該是類似vectorv這樣的。

1.1 vector的構造、拷貝構造與迭代器

先認識一下，包括vector的構造、拷貝構造、賦值。
構造：
(為了更好理解使用，做了一些關于空間配置器的省略)

//第一種無參構造
vector()
//第二種，第一個參數代表初始有效個數，val代表賦的初始值
vector(size_type n, const value_type& val = value_type());
//第三種，迭代器賦值
template(class InputIterator)
vector(InputIterator first, InputIterator last);

拷貝構造:
拷貝構造很簡單

vector (const vector& x);

賦值:
賦值注意的是兩種不同的形式，代表不同含義。

//第一種 直接賦值
vectorv1;
vectorv2(10, 0);
v1 = v2;
//第二種 表面賦值，其實是拷貝構造
vectorv3 = v2;

實例:

#include#includeusing namespace std;

void vector_test1()
{//構造
	vectorv1;
	vectorv2(10, 0);
	vectorv3(v2.begin(), v2.end());
	
	string s = "hello world";
	vectorvs(s.begin(), s.end());
	
	//拷貝構造
	vectorv4(v2);
	vectorv5 = v2;
	
	//賦值
	vectorv6;
	v6 = v2;
}

int main()
{vector_test1();
	return 0;
}

vector中的迭代器使用
迭代器在C++中，封裝了iterator和const_iterator兩個類。在使用層面上與指針的使用一致，但在底層實現上不同STL版本，不一致，不能簡單和指針等同。

首先介紹簡單的begin和end。

//begin 返回指向vector中首元素位置的迭代器
iterator begin();

//end 返回指向vector中末尾元素再下一個位置的迭代器
iterator end();

比如:

void vector_test2()
{//構造
	vectorv1(10, 1);
	vectorv2(v1.begin(), v1.end());
	
	//打印
	vector::iterator it = v2.begin();
	while(it != v2.end())
	{cout<< *it;
		++it;
	}
	cout<< endl;
}

?
const 迭代器的使用
const迭代器保護的是指向的數據不能被修改，而迭代器本身是可以被修改的。

//begin 返回指向vector中首元素位置的迭代器
const iterator begin();

//end 返回指向vector中末尾元素再下一個位置的迭代器
const iterator end() const;

比如：

void vector_test3()
{//構造
	vectorv1(10, 1);
	//權限的縮小
	const vectorv2(v1.begin(), v1.end());
	
	//打印
	//切記不能寫成 因為這樣是使得it不能修改。
	//const vector::iterator it = v2.begin();
	
	//這樣改變的是迭代器類型，得換的是一個類
	vector::const_iterator it = v2.begin();
	while(it != v2.end())
	{cout<< *it;
		++it;
	}
	cout<< endl;
}

在迭代器成員函數中還有rbegin，rend。它們使用和begin、end一樣，只是返回迭代器指向位置反了過來。
在這里插入圖片描述
?

1.2 vector的空間查詢和隨機訪問

vector作為動態(tài)數組，也有著當前有效數據個數（size）和當前總容量(capacity)。

size相關的成員函數:

//返回當前有效數據個數
size_type size() const;
//重新設置當前有效數據個數
void resize(size_type n, value_type val = value_type());

capacity相關的成員函數:

//返回當前總容量大小
size_type capacity() const;
//重新設置總容量大小 不縮容只擴容
void reserve(size_type n);

隨機訪問與其它:

//[]是運算符重載，返回值是單個數據
reference operator[](size_type n);
const_reference operator[](size_type n) const;

//at和[]結果一樣，只不過是函數，不怎么用
reference at (size_type n);
const_reference at (size_type n) const;

//返回首元素
reference front();
const_reference front() const;

//返回末尾元素
reference back();
const_reference back() const;

void vector_test4()
{vectorv1(1, 5);
	cout<< v1.size()<< endl;
	cout<< v1.front()<< endl;

	//擴大size，補4
	v1.resize(11, 4);
	cout<< v1.back()<< endl;
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1[i];
	}
	cout<< endl;

	//縮小size, 截斷
	v1.resize(6);
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1.at(i);
	}
	cout<< endl;

	//不縮容只擴容
	v1.reserve(10);
	cout<< v1.capacity()<< endl;//11

	v1.reserve(12);
	cout<< v1.capacity()<< endl;//12

}

在這里插入圖片描述

1.2 vector的增刪查改

注意:vector的插入和刪除，一定要注意返回的迭代器，在進行插入刪除后，最好對迭代器指向的位置進行更新，不然可能會引起迭代器失效問題。

//尾插
void push_back (const value_type& val);
//尾刪
void pop_back();

//指定位置插入刪除
//指向位置pos插入val, 返回插入新元素的位置
iterator insert (iterator position, const value_type& val);
//指定位置刪除，返回下一個位置
iterator erase (iterator position);

//指定范圍插入刪除
//指定位置，范圍插入。
templatevoid insert (iterator position, InputIterator first, InputIterator last);
//指定范圍刪除，返回刪除范圍后一個位置
iterator erase (iterator first, iterator last);

//交換數據
void swap (vector& x);
//清空數據，容量不變
void clear();

測試:

void vector_test5()
{//測試尾插尾刪
	vectorv1;
	v1.push_back(1);
	v1.push_back(2);
	v1.pop_back();

	//測試指定位置插入刪除
	vector::iterator it = v1.begin();
	it = v1.insert(it, 0);
	it = v1.erase(it);
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1[i];
	}
	cout<< endl;

	//測試指定范圍插入刪除
	vectorv2(10, 1);
	it = v1.begin();
	v1.insert(it, v2.begin(), v2.end());

	it = v1.erase(v1.begin(), v1.begin() + 3);

	//其它
	v1.swap(v2);
	for (int i = 0; i< v1.size(); ++i)
	{cout<< v1[i];
	}
	cout<< endl;

	v2.clear();
	cout<< v2.size()<< endl;
	cout<< v2.capacity()<< endl;
}

使用完~

2、vector的模擬實現

因為SGI版STL可讀性比較好，模擬實現以它為參考。
由于vector的模擬實現簡單易懂，這里只說部分重要的。

2.1 vector的迭代器

由于vector是一個連續(xù)的線性空間，所以原生指針可以作為vector的迭代器且滿足所有必要條件。（但vs中vector的迭代器底層不是這樣的）

templateclass vector
{public:
	typedef T* iterator;
	typedef const T* const_iterator;
	...
}

所以

vector::iterator it;

it就是int*.

2.2 vector的結構構建

vector是一個線性連續(xù)空間。在SGI底層，用三個迭代器start、finish、end_of_storage分別指向空間來標識范圍。

templateclass vector
{public:
	typedef T* iterator;
	typedef const T* const_iterator;
	...
private:
	iterator _start; //表示已使用用空間的頭
	iterator _finish; //表示已使用空間的尾
	iterator _end_of_storage; //表示目前可用空間的尾
}

通過這三個迭代器，可以很輕松的聯(lián)系上以下功能

templateclass vector
{public:
	typedef T* iterator;
	typedef const T* const_iterator;
	
	iterator begin()
	{return _start;
	}

	const_iterator begin() const
	{return _start;
	}

	iterator end()
	{return _finish;
	}
	
	const_iterator end() const
	{return _finish;
	}
	
	size_t size() const
	{return end()-begin();
	}
	
	size_t capacity() const
	{return _end_of_storage - begin();
	}
	
	bool empty() const
	{return end() == begin();
	}

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

	const T& operator[](size_t pos) const
	{assert(pos< size());
		return _start[pos];
	}
private:
	iterator _start; //表示已使用用空間的頭
	iterator _finish; //表示已使用空間的尾
	iterator _end_of_storage; //表示目前可用空間的尾
}

在這里插入圖片描述
?

2.4 vector的構造和拷貝構造

vector構造有三種：

vector();

vector(size_t n, const T& val = T());

templatevector(InputIterator first, InputIterator last);

值得注意的是:第二個構造在調用時可能是vector v(10,1);這樣的，由于10和1的類型一樣，可能會導致調用第三個構造造成尋址錯誤，所以下面通過函數重載避免其出現。

#include#include 
using namespace std;

namespace test
{templateclass vector
	{public:
		...
		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_end_of_storage(nullptr)
		{}

		//構造
		vector(size_t n, const T& val = T()) //默認0
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	size_t i = 0;
			for (i = 0; i< n; ++i)
			{		push_back(val);
			}
		}

		//重載解決類似vectorv(10, 1);這樣引發(fā)的尋址錯誤
		vector(int n, const T& val = T()) //默認0
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	int i = 0;
			for (i = 0; i< n; ++i)
			{		push_back(val);
			}
		}

		templatevector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	while (first != last)
			{		push_back(*first);
				++first;
			}
		}
		...
		...
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

vector的拷貝構造，可以多進行函數復用，來精簡代碼。

//拷貝構造 寫法一
		//vector(const vector& v)
		//	:_start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//{//	reserve(v.capacity());
		//	for (const auto& e : v) //注意要加& 不然T可能是自定義類型
		//	{//		push_back(e);
		//	}
		//}

		//函數復用 寫法二
		vector(const vector& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	vectortmp(v.begin(), v.end());
			swap(tmp);
		}

		//利用v拷貝構造的臨時對象進行交換
		vector& operator=(vectorv)
		{	swap(v);
			return *this;
		}
		
		//調用官方std中的淺拷貝
		void swap(vector& v)
		{	std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

2.4 vector的增刪

插入中的迭代器需要注意，擴容可能會導致原本空間被釋放，需要迭代器重新指向新空間。

reserve實現有兩個注意點：
1. 因為擴容是會開辟新空間，歸還舊空間的，所以指向原來舊空間的指針也需要更新。
2. 在拷貝舊空間數據的時候，需要深拷貝，不然自定義類型數據淺拷貝會出現析構錯誤。

void reserve(size_t n)
	{if (n >capacity())
		{	//使用oldsize 記錄舊空間size大小
			size_t oldSize = size();
			T* tmp = new T[n];
			if (_start)
			{		//memcpy(tmp, _start, sizeof(T) * oldSize); 拷貝的是內置數據 對于自定義類型是淺拷貝
				for (size_t i = 0; i< oldSize; ++i)
				{tmp[i] = _start[i];
				}
				delete[] _start;
			}

			_start = tmp;
			_finish = _start + oldSize;
			_end_of_storage = _start + n;
		}
	}

insert實現要注意迭代器失效問題，迭代器pos在擴容以后與原來start的相對距離是固定的，但是指向的位置是原來舊空間的位置，在擴容后需要更新。

iterator insert(iterator pos, const T& val)
	{assert(pos >= _start);
		assert(pos< _finish);
		if (_finish == _end_of_storage)
		{	// 迭代器失效
			// 擴容導致迭代器失效
			size_t oldPos = pos - _start;
			size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
			reserve(newCapacity);
			pos = _start + oldPos; //但形參不改變實參
		}

		iterator end = _finish - 1;
		while (end >= pos)
		{	*(end + 1) = *end;
			--end;
		}

		*pos = val;
		++_finish;

		return pos;

	}

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

		iterator begin = pos + 1;
		while (begin< _finish)
		{	*(begin - 1) = *(begin);
			++begin;
		}
		--_finish;

		return pos;
	}

最后在vector中，insert或者erase后，一定要注意迭代器的位置，如果在插入或刪除后需要使用迭代器，一定要讓迭代器接收返回值，不然會出現迭代器失效。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

當前名稱：【C++】使用vector和模擬其實現-創(chuàng)新互聯(lián)
標題鏈接：http://muchs.cn/article34/ipdpe.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供建站公司、網站營銷、靜態(tài)網站、軟件開發(fā)、網站策劃、手機網站建設

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內容