嘿，各位技術潮人！好久不見甚是想念。生活就像一場奇妙冒險，而編程就是那把超酷的萬能鑰匙。此刻，陽光灑在鍵盤上，靈感在指尖跳躍，讓我們拋開一切束縛，給平淡日子加點料，注入滿滿的passion。準備好和我一起沖進代碼的奇幻宇宙了嗎？Let's go！
我的博客：yuanManGan
我的專欄：C++入門小館?C言雅韻集?數據結構漫游記? 閑言碎語小記坊?題山采玉?領略算法真諦
目錄
vector的使用:
模擬實現vector:
先來了解一下vector的使用
vector的使用:
初始化方式:
?
這一坨實現的是內存池，如果你對STL里面的內存池不滿意可以自己傳入內存池，自己寫一個。
第一個是無參構造
第二個是構造n個一樣的類型一樣的值
第三個是利用迭代器區間構造。
第四個是拷貝構造。
也可以使用initializer_list類型來構造。
由于vector沒有重載>>和<<運算符，但也沒有必要重載,我們打印也可以用范圍for來遍歷。
for(auto& x : v1){cout << x << " ";}結果:?
?
?
?這些迭代器也很眼熟了，沒有什么好講的，用法也差不多。
shrink_to_fit是用來縮容的，一般不咋用。
front和back是返回第一個和最后一個元素，可以使用下標加方括號就可以訪問到所有元素了。這兩個也不咋常用。
這些也是看的很眼熟了，這里在C++11有一個emplace這個和插入的功能所實現的效果是一樣的，但這個使用起來更高效。
外部有一個swap和內部也有一個swap，還是類似于string類，外部的swap實現起來，造成了很多浪費。
注意這里的insert和erase要傳入迭代器了，不像string能傳入位置，要傳入迭代器。
模擬實現vector:
我們先來看看STL源碼里面的vector怎么實現的
vector要使用模版，另一個是內存池。
這是成員變量：
從下面可以看到vector的迭代器在這個版本的STL中是用原生指針來實現的，但不能說只能用原生指針來實現，其他版本可能使用其他方式實現。
_start 來指向第一個元素，_finish指向的是最后一個元素后面一個位置，_end_of_storage指向內存最大值的下一個位置。
c
?從這些就可以看出來。
好了看了基本的內容，我們就來自己實現一下吧！因為內存池這里，我還沒有學習過，就先不實現了。
寫個成員變量：
namespace refrain
{template <class T>class vector{public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;};
}
默認構造
無參構造
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}容量，數量:
size_t capacity()
{return _end_of_storage - _start;
}
size_t size(size_t i)
{return _end_of_storage - _start;
}我們先來實現插入，方便我們好檢查我們是否寫錯了
但我們實現push_back()之前要先實現一下擴容邏輯，因為push_back可以復用reserve函數。
reserve:
void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){for (int i = 0; i <= size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}
}注意這里這里要先用oldsize存一下原來的size不然，后面_start+size()會調用size函數
這個時候_start已經改變了，得到的finish就不是我們期望的值。
然后push_back的邏輯就簡單了：
void push_back(const T& x){//檢查是否需要擴容if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*(_finish) = x;_finish++;}?pop_back就更簡單了：
void pop_back()
{assert(_finish > _start);_finish--;
}我們再重載一下方括號和迭代器相關的接口，來實現打印一下。
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;
}T& operator[](size_t i)
{return *(_start + i);
}
?接下來的實現insert和erase操作的邏輯就和string差不多了
void insert(iterator pos, T x)
{assert(pos >= _start);assert(pos < _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;it--;}*(pos) = x;_finish++;}
void erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos;while (it < _finish){*(it) = *(it + 1);it++;}_finish--;}?寫下面這個方便打印
void print(const vector<int>& v)
{for (auto& k : v){cout << k << " ";}cout << endl;
}
我們看看下面這個程序：
我們再來寫一個程序，用來刪去v里面的偶數。
我們不能使用已經失效的迭代器，我們咋解決這個問題呢我們看看庫里面的insert和erase
?
?它們都是有返回值的，返回指向下一個位置的迭代器。
所以我們的insert和erase就成了:
iterator insert(iterator pos, T x)
{assert(pos >= _start);assert(pos < _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;it--;}*(pos) = x;_finish++;return pos;}
iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos;while (it < _finish){*(it) = *(it + 1);it++;}_finish--;return pos;
}
就歐克了。這里就出現了迭代器失效的問題。
最后來實現一下賦值運算符和拷貝構造吧！
vector(const vector<T>& v)
{reserve(v.capacity());for (auto& x : v){push_back(x);}
}
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);
}
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}
不多說了和string差不多。
)
