目錄

引言?

一、vector的基本框架

二、尾插push_back、reserve擴容、任意位置插入insert（增）

1.reserve擴容

2.push_back尾插

3.深層次的淺拷貝問題

4.?任意位置插入數據insert(會使迭代器失效)

三、構造、析構、拷貝構造函數

1.構造函數

1.1無參構造

1.2initializer_list?類作為參數來構造。

1.3用任意類型的迭代器來構造

2.拷貝構造

3.析構函數

四、判空函數(empty)、尾刪(pop_back)、刪除任意位置元素(erase)

1.判空

2.尾刪

3.刪除任意位置元素（會使迭代器失效）

五、[]運算符重載、=賦值運算符重載、交換vector函數

1.swap函數

2.=賦值運算符重載

3.[]運算符重載

六、vector.h代碼

---

引言?

手把手帶你實現vector

實現vector的意義：對底層有個更深的理解。鍛煉代碼能力。

_涂色_-博客主頁

C++基礎專欄

為了與STL中的vector區分開，這里都寫在命名空間stl中，并且實現類函數的聲明和定義分離。?

分3個文件來寫：

• string.h：string類的聲明。
• text.c?：測試string的接口是否正確。

因為：模板聲明和定義不能分離定義到兩個文件。所以都在h .cpp文件中。

一、vector的基本框架

這里是為了保持和STL源碼的私有成員一樣所以這樣設計。

這里的迭代器只是以簡單的形式來實現的，真實的迭代器不是這樣的。

namespace stl
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;const_iterator begin() const //vector開始位置{return _start;}const_iterator end() const  //vector結束位置{return _finish;}iterator begin(){return _start;}iterator end(){return _finish;}int capacity() const  //vector里面的個數{return _endofstorage - _start;}int size() const  //計算出vector數組中元素個數{return _finish - _start;}private:iterator _start = nullptr;  // 存儲數據的數組iterator _finish = nullptr;  //數組結尾的寫一個位置iterator _endofstorage = nullptr;  //數組的空間的最后一個位置};
}

二、尾插push_back、reserve擴容、任意位置插入insert（增）

1.reserve擴容

先實現reserve擴容

注意：必須先計算出原來的元素個數，若在下面計算元素個數的時候，由于_start已經發生了改變，會使得計算元素個數錯誤。

? ? ? ? 關于深層次的淺拷貝問題，寫出push_back來給出說明。

void reserve(const size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//拷貝舊空間數據到新空間數據if (_start){//memcpy(tmp, _start, sizeof(T*) * old_size); 會存在深層次的淺拷貝問題。for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + old_size;_endofstorage = _start + n;}
}

2.push_back尾插

先看空間夠不夠，不夠就先擴容，然后尾插即可。

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

3.深層次的淺拷貝問題

運行下面代碼，當尾插5個string類型的數據時，由于需要擴容，就需要拷貝原理的數據。

namespace stl
{	template<class container>void Print(const container& con){for (auto e : con){cout << e << " ";}cout << endl;}void test_vector1(){vector<string> v1;v1.push_back("11111111111111111111111");v1.push_back("11111111111111111111111");v1.push_back("11111111111111111111111");v1.push_back("11111111111111111111111");v1.push_back("11111111111111111111111");Print(v1);}
}int main()
{stl::test_vector1();return 0;
}

但是，如果使用memcpy拷貝數據的話，就會形成生層次的淺拷貝問題。

當使用memcpy拷貝時：

?所以這里不能使用memcpy來進行拷貝，要通過賦值操作符，調用函數的拷貝構造，來進行拷貝。

4.?任意位置插入數據insert(會使迭代器失效)

在 C++ 里，迭代器失效是一個重要概念，它指的是由于容器結構發生改變，導致原本指向容器中某個元素的迭代器不再有效。此時若繼續使用這個迭代器，可能會引發程序崩潰、得到錯誤結果等嚴重問題。

1. 先看空間夠不夠，不夠的話就先擴容，擴容的時候，需要更新pos指針，否則pos位置就被釋放了（pos就是野指針了）。
2. 將pos位置和后面的元素向后移動一位
3. 最后在pos位置插入元素x

iterator insert(iterator pos, const T& x) //給返回值是解決迭代器失效
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 擴容后這里需要更新pos，否則pos就是野指針了pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

三、構造、析構、拷貝構造函數

1.構造函數

1.1無參構造

可以手動寫，但是沒有必要，因為成員給了缺省值，所以，不帶慘的構造使用編譯器生成的即可。

	vector():_start = nullptr,_finish = nullptr, _endofstorage = nullptr{}

但是下面會寫拷貝構造，所以編譯器不會自己生成構造函數了，所以：

		// 強制編譯器生成默認構造vector() = default;

1.2initializer_list<T>?類作為參數來構造。

使用?initializer_list<T>?類作為參數來構造。

vector(initializer_list<T> il)
{reserve(il.size());for (auto& e : il){push_back(e);}
}

通過這種構造，可以這樣初始化vector：

vector<int> v1 = { 1,2,3,4,5,5 };
vector<int> v2 = { 1,2,3,4,5,51,1,1,1,1,1,1,1 };

原因就是通過?initializer_list<T>類來進行初始化。

1.3用任意類型的迭代器來構造

當我們想用string的一段，來初始化vector時：

		// 函數模板// 任意類型容器迭代器初始化template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

運行下面這段代碼?

string s1("hello world");
vector<int> v6(s1.begin(), s1.end());
Print(v6);

?

2.拷貝構造

直接開一樣的空間，進行尾插來拷貝構造

		//v2(v)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

3.析構函數

?釋放數組，然后都置為空。

		~vector<T>(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}

四、判空函數(empty)、尾刪(pop_back)、刪除任意位置元素(erase)

1.判空

• 是空，就返回真，
• 不是空，就返回假

bool empty() const
{return _start == _finish;
}

2.尾刪

有了判空函數，就不需要使用assert來斷言了。

void pop_back()
{//assert(_finish > _start);assert(!empty());--_finish;}

3.刪除任意位置元素（會使迭代器失效）

iterator erase(const iterator pos)  //給返回值是解決迭代器失效
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}return pos;
}

五、[]運算符重載、=賦值運算符重載、交換vector函數

1.swap函數

交換兩個vector

void swap(vector<T> v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}

2.=賦值運算符重載

tmp是v2的拷貝，然后和v1直接交換，就使得v1 等于 v2了。

// V1 = V2
vector<int>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}

3.[]運算符重載

可以通過下標來訪問vector了

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

六、vector.h代碼

#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
// 模板 聲明和定義不能分離定義到兩個文件.h .cppnamespace stl
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}iterator begin(){return _start;}iterator end(){return _finish;}// 強制編譯器生成默認構造vector() = default;vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}//v2(v)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}~vector<T>(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}// V1 = V2vector<int>& operator=(vector<T> tmp){swap(tmp);return *this;}// 函數模板// 任意類型容器迭代器初始化template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}/*vector(iterator first, iterator last){while (first != last){push_back(*first);++first;}}*/vector(int n, int val = T()){resize(n, val);}vector(size_t n, T val = T()){resize(n, val);}void swap(vector<T> v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}void reserve(const size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//拷貝舊空間數據到新空間數據if (_start){//memcpy(tmp, _start, sizeof(T*) * old_size); 會存在深層次的淺拷貝問題。for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + old_size;_endofstorage = _start + n;}}int capacity() const{return _endofstorage - _start;}int size() const{return _finish - _start;}void push_back(const T& x){if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back(){//assert(_finish > _start);assert(!empty());--_finish;}iterator insert(iterator pos, const T& x) //給返回值是解決迭代器失效{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 擴容后這里需要更新pos，否則pos就是野指針了pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}iterator erase(const iterator pos)  //給返回值是解決迭代器失效{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}return pos;}bool empty() const{return _start == _finish;}void resize(size_t n, T val = T()){if (n > size()){reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}

完。