手撕STL——vector

引言

1，了解 STL 中的 vector?

2，先來一個簡易版跑起來

2_1，構造函數

2_2，擴容reserve（）

2_3，push_back（）

2_4，pop_back（）

2_5，測試一下

3，迭代器

3_1，如何設計iterator

3_2，begin（），end（）一鍋端

4，功能完善

4_1，operator[ ]（）

4_2，size（）和 capacity（）

4_3，resize（size_t n， T? x = T()）

4_4，insert（）

4_5，erase（）

4_6，構造函數重載——迭代器

4_7，拷貝構造函數

4_8，賦值運算符重載

4_9，析構函數

5，總結

革命尚未成功，同志仍須努力

引言

上一期我們手撕了list，這一期我們就來手撕一個vector（代碼在最后），vector手撕起來就比list簡單很多啦。

1，了解 STL 中的 vector?

在學習初階數據結構的時候，順序表咱們也撕過好多次了，有靜態的，也有動態的，在STL中，vector是一個動態開辟的順序表，但是它與咱們在數據結構階段實現的順序表是有差異的，在數據結構階段實現的順序表中，我們是通過 typename* a, int size, int capacity，作為成員變量

#define typename intstruct node
{typename* a;int size;int capacity;
}

但是哈，在vector中，就變得不一樣啦。

template <typename T>
class vector
{private:T* _start;T* _finish;T* _end_of_storage;
}

STL 中的 vector，用了三個指針當成員變量，為什么要這樣設計呢？

在C中，咱們用的是，struct,struct的成員變量咱們是可以直接訪問的，但是在C++的class中，為了保護成員變量，咱們將其設置成private成員，咱們在外面是不能直接訪問的，vector中有size（）和capacity（）函數，來獲取size和capacity。但是其他的思路大致是不變的，那咱們就開始手撕吧。

2，先來一個簡易版跑起來

2_1，構造函數

2_2，擴容reserve（）

vector中數據是存在一段連續的空間，不能像list那樣插入前new一個空間出來，我們必須提前開好空間，保證插入數據的時候空間一個是足夠的。

reserve的實現過程很簡單，在數據結構初階階段我們用realloc進行擴容，其大致原理就是，如果這段連續的空間后面的空間夠就直接原地擴容，如果不夠就找一個空間夠的地方，重新開辟空間，并將原有的數據拷貝過去，最后將原有的空間釋放。

我們直接用new和delete進行異地擴容，開辟好空間后再進行數據拷貝，拷貝完數據記得釋放原來的空間，避免內存泄漏。

2_3，push_back（）

因為順序表頭插需要挪動數據，代價是比較大的，STL中的vector也沒有提供頭插接口，所以這里只來一個頭插

尾插分3步

1，檢查需不需要擴容

2，將 _finish 位置賦值

3，++finish

2_4，pop_back（）

尾刪就比較簡單啦，直接 --_finish，就可以了

2_5，測試一下

咱們目前還沒有完成其他的函數，為了測試，咱們寫一個打印函數print（）

ok，沒有問題，是可以跑起來了的。

3，迭代器

3_1，如何設計iterator

迭代器在STL中是一個非常重要的設計，它觀察STL，當然在vector中的迭代器是比較簡單的。

因為vector中的數據是存儲在一段連續的空間中，咱們的iterator就可以直接由指針typedef得來。

typedef T* iterator;
typedef const T* const_iterator;

3_2，begin（），end（）一鍋端

4，功能完善

4_1，operator[ ]（）

中括號重載是一個比較重要的函數，有他的存在我們就能很方便的插入修改數據。

4_2，size（）和 capacity（）

直接用指針相減的中間元素個數的知識實現

4_3，resize（size_t n， T? x = T()）

resize（）的功能大家一定要清楚，他的注意功能是改變size。

如果 n? <?size（）?就直接刪除數據，通過改變 _finish? 實現

如果 size（）?<? n < capacity （），改變size，并進行初始化

如果? capacity （） <? n，先開空間，在改變size，并進行初始化

4_4，insert（）

insert 大致分三步

1，檢查是否需要擴容

2，挪動數據

3，插入

這里要注意一個問題，當我們進行擴容后，原來的迭代器所指向的位置已經被delete清理了，這時候的iterator實際上是一個野指針。

為了防止出錯，我們要在最開始通過指針的減法記錄迭代器的位置，后面通過加法還原迭代器。

4_5，erase（）

這里也用注意迭代器失效的問題

雖然我們這里沒有擴容，進行刪除后，迭代器仍然指向原來的位置

但是還是會有一點點風險，為了確保萬無一失，咱們這里還是進行了存儲迭代器位置，還原迭代器的操作。

4_6，構造函數重載——迭代器

在STL中，我們常可以看見用迭代器去構造一個容器，vector當然也可以，咱們就來實現一下

其實也是比較簡單啊，通過迭代器，我們可以變量它，得到它的數據，再通過push_back（）插入，遍歷完了之后，vector也構造完了。為了可以使所有的迭代器都可以對其進行傳參構造，這里還需要用到模板。

4_7，拷貝構造函數

根據參數直接構造。

先根據被拷貝的對象的 capacity 對要拷貝的對象進行擴容，再進行遍歷和賦值。

4_8，賦值運算符重載

還是有傳統寫法與現代寫法。

傳統寫法是遍歷參數的數據?給需要被賦值的對象進行數據的賦值

咱們這里寫現代寫法。

傳參的時候不傳引用，編譯器根據咱們的拷貝構造函數進行拷貝，使用swap函數進行交換，對于參數 x 而言，它的數據存儲的空間再堆上，但是x的三個成員變量會在賦值運算符重載這個函數結束的時候進行空間的回收，但是在堆的那一部分數據還是存在的。

使用 swap 函數進行交互只是交換了參數 x 和待賦值的對象的三個指針，讓待賦值的對象的三個成員遍歷指向堆存儲的數據的位置。

傳統寫法和現代寫法原理大差不差的，只不過現代寫法把拷貝數據的工作交給了編譯器，實現起來更為簡潔

4_9，析構函數

因為vector的數據存儲在一段連續的區域，直接delete就可以了

5，總結

雖然咱們手撕了一個 vector 但是咱們撕的只能說是一個簡易版，我只是把 vector 里面常用，經典的函數帶著大家手撕了一下，庫里面的 vector的功能是非常強大的，而且大多函數都有多種重載。

大家可以通過這篇博客感受一下vector 的創建，也可以繼續完善咱們自己的vector

革命尚未成功，同志仍須努力

#pragma once
#include <assert.h>
#include <iostream>
namespace ssy
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}vector(size_t n, T data = T()): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){resize(n, data);}template<class InputIterator>vector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}vector(const vector<int>& v): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){_start = new T[v.capacity()];size_t sz = v.size();for (int i = 0; i < sz; i++){_start[i] = v._start[i];}_finish = _start + sz;_end_of_storage = _start + v.capacity();}void swap(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> x){swap(x);return *this;}~vector(){if (_start){delete _start;_start = _finish = _end_of_storage = nullptr;}}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}void resize(size_t n, T data = T()){size_t sz = size();if (n < capacity()){_finish = _start + n;for (int i = sz; i < n; i++){_start[i] = data;}}else{reserve(n);for (int i = sz; i < n; i++){_start[i] = data;}_finish = _start + n;}}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];int size = _finish - _start;if (_start){for (int i = 0; i < size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + size;_end_of_storage = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;++_finish;}void pop_back(){--_finish;}T& operator[](size_t pos){assert(pos < capacity());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < capacity());return _start[pos];}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}iterator insert(iterator pos, const T& data){size_t ppos = pos - _start;assert(ppos <= size());if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}size_t end = size();while (end > ppos){_start[end] = _start[end - 1];--end;}_start[end] = data;++_finish;return _start + ppos;}iterator erase(iterator pos){size_t ppos = pos - _start;assert(ppos < size());size_t len = ppos;size_t  end = size();while (ppos < end){_start[ppos] = _start[ppos + 1];ppos++;}--_finish;return _start + len;}void print(){int n = _finish - _start;for (int i = 0; i < n; i++){cout << _start[i] << " ";}cout << endl;}private:T* _start;T* _finish;T* _end_of_storage;};
}