前言：
在上一篇文章中我們詳細的向大家介紹了vector的一些核心接口的使用，那麼本篇文章就來深度的剖析一下vector的底層實現。
文章目錄
- 一、vector的基本成員變量
- 二、vector核心接口的實現
- 2.1構造相關接口的實現
- 2.2迭代器相關的接口實現
- 2.3空間相關的接口的實現
- 2.3.1memcpy深層次的淺拷貝問題
- 2.4元素訪問相關的接口實現
- 2.5vector修改相關的接口實現
- 三，插入刪除引起的迭代器失效問題
- 四、總結
一、vector的基本成員變量
在模擬實現vector之前我們首先要了解vector的基本成員變量，然後在逐步進入到vector的一些核心接口的實現。如何知道這些成員變量呢？下面通過源碼一探究竟：
有了上面的認識，那麼我們模擬實現的vector的成員變量就仿照源碼來實現：
#include<iostream>
using namespace std;
namespace my_vector
{
template<class T>
class vector
{
public:
//vector的迭代器使用的是一個原生指針，因為原生指針本身就能完成迭代器相關的++ * --等這些操作
typedef T* iterator;
typedef const T* const_iterator
private:
iterator _start;//指向空間頭部的指針
iterator _finish;//指向最後一個有效數據的下一個位置
iterator _endofstorage;//指向空間的末尾
};以上就是模擬實現的vector的基本框架，成員變量就是_start、_finish、_endofstorage這三個指針。下面就正式的進入vector的模擬實現，模擬vector的五大步驟：
1、構造相關接口
2、迭代器相關接口
3、空間相關
4、元素訪問
5、vector的修改操作
二、vector核心接口的實現
2.1構造相關接口的實現
構造相關的接口主要有以下幾種：
- 默認構造
- 使用n個元素構造
- 拷貝構造
- 初始化列表構造
- 迭代器區間構造
- operator= 運算符重載
注意：以下實現的接口均是在vector類的內部實現，不像string那樣聲明和定義可以分離到兩個文件。因為我們要自己實現一個vector的模板，而模板的聲明和定義是不能分離到兩個不同的文件的，同一個文件下可以。
//vector的默認構造
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
//使用n個val初始化
//這裏的T()是調用T對應的構造 是為了能夠讓任意類型都能夠調用 如果T是內置類型 就會調用內置類型的構造 如果T是自定義類型就調用自定義類型自己的默認構造
vector(size_t n, T val = T())
{
resize(n, val);//resize接口後面會講
}
//拷貝構造
```cpp
//拷貝構造 v2(v1)
vector(const vector<T>& v)
{
//開與v1一樣大的空間
reserve(v.size());//reserve接口後面會介紹
//底層也是調用push_back
for (auto e : v)
{
push_back(e);//尾插，後面會介紹
}
}
//使用初始化列表構造 示例:vector<int> v1={1,2,3,4,5}; 花括號的內容其實是轉化成了initializer_list對象 這裏不理解的可以看上一篇文章！
vector(initializer_list<T> il)
{
//根據所給的對象il開空間然後調用push_back
reserve(il.size());
for (auto e : il)
{
//底層是this指針調用的pus_back this指針存的是要構造的vector對象的地址
push_back(e);
}
}
//迭代器區間構造 搞成函數模板支持泛型 形參可以是任意容器的迭代器
template<class Inputiterator>
vector(Inputiterator first, Inputiterator last)
{
//底層調的還是push_back
while (first != last)
{
push_back(*(first));
first++;
}
}
//賦值重載 底層使用交換函數交換底層的成員變量
vector operator=(const vector<T>& v)
{
swap(v);
return *this;
}
void swap(const vector<T>& v)
{
std::swap(_start,v._start);
std::swap(_finish,v._finish);
std::swap(_endofstorage,v._endofstorage);
}
//析構
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}2.2迭代器相關的接口實現
vector的迭代器主要實現的是普通迭代器和const迭代器：
//普通迭代器
iterator begin()
{
return _start;
}
iterator end()
{
//返回的是finish不是endofstorage
return _finish;
}
//const迭代器
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
//返回的是finish不是endofstorage
return _finish;
}反向迭代器就是與正向迭代器相反，
rbegin()返回end()-1，rend()返回begin()-1。
2.3空間相關的接口的實現
與空間相關的接口有：
1、size() ——> 記錄有效數據個數
2、capccity() ——> 記錄總的空間大小
3、empty() ——> 判空
4、resize() ——> 擴容 影響size
5、eserve() ——> 擴容 不影響size注意：vector中空間相關的接口就屬reserve接口最為重要，它主要負責vector的擴容邏輯，而resize接口也可以擴容但是兩者有本質的區別，通過下面的底層實現你就能一探究竟：
//size和capacity通過兩個指針相減可以計算它們之間的數據個數
size_t size() const
{
return _finish - _start;
}
size_t capacity()
{
return _endofstorage - _start;
}
bool empty() const
{
return _start == _finish;
}
void resize(size_t n, T val = T())
{
if (n > size())
{
reserve(n);
//n>size後面的n-size個空間使用val來填充
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
else//n<size 縮容影響size 有效數據直接縮到n處
{
_finish = _start + n;
}
}
void reserve(size_t n)
{
//在start更新前要保存一下size
auto oldsize = size();
if (n > size())
{
//開闢新空間 拷貝舊數據
iterator tmp = new T[n];
//拷貝舊數據
if (_start)
{
//memcpy深層次的拷貝問題 原因對於自定義類型是淺拷貝 delete的時候析構兩次
//memcpy(tmp, _start, size()*sizeof(T));
//使用賦值重載來避免這種問題！！！
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
//更新有效數據個數
_finish = _start + oldsize;
_endofstorage = _start + n;
}
}2.3.1memcpy深層次的淺拷貝問題
注意這裏有一個很容易留坑的點：就是memcpy生層次的淺拷貝問題：
怎麼才能解決呢？調用賦值重載完成深拷貝就可以。
2.4元素訪問相關的接口實現
元素訪問相關的接口最常使用的就是operator[]，而vector的迭代器使用的是原生指針，那麼operator[]無非就是訪問某個下標的元素，下面看代碼：
//支持讀和寫操作
const T& operator[](size_t i)
{
//判斷下標是否合法
assert(i < size());
return _start[i];//實際上轉化為指針的解引用: *(_start+i)
}
//加上const後只讀
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}2.5vector修改相關的接口實現
vector修改相關的接口無非就是插入刪除，插入有尾插，任意位置插入，刪除有尾刪，以及任意位置的刪除，實現這些插入，刪除函數時有較多的細節需要注意。下面給出代碼再一點點的剖析。
//尾插
void push_back(const T& x)
{
//插入要考慮空間是否足夠
if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
++_finish;
}
//尾刪
void pop_back()
{
assert(!empty());
--_finish;
}
iterator insert(iterator pos, const T& x)
{
assert(pos <= _finish);
assert(pos >= _start);
//插入首先判斷空間是否足夠
if (_finish == _endofstorage)
{
//法一 計算相對位置
size_t n = pos - _start;
//擴容 異地擴容會導致迭代器失效 在這裏就是野指針
reserve(capacity() == 0 ? 4 : 2 * capacity());
//擴容後更新pos
pos = _start + n;
}
//挪動數據
iterator end = _finish;
while (end >= pos)
{
*(end + 1) = *(end);
end--;
}
*(pos) = x;
_finish++;
return pos;
}
//版本二 返回迭代器
iterator erase(iterator pos)
{
//檢查pos的合法性
assert(pos <= _finish);
assert(pos >= _start);
//刪除要判斷容器是否為空
if (!empty())
{
//刪除也會引發迭代器失效
iterator it = pos;
while (it < _finish)
{
//
*(it) = *(it + 1);
++it;
}
--_finish;
}
return pos;
}三，插入刪除引起的迭代器失效問題
void test_vector9()
{
my_vector::vector<int> v{ 1,2,3,4};
auto it = v.begin();
v.push_back(5); //這裏會擴容
while (it != v.end())
{
cout << *it << " ";
*it = 100;
++it;
}
cout << endl;
}
注意：上面的插入元素的過程中會引發迭代器失效導致打印的全是隨機值(有時候會奔潰)，至於為什麼會失效我們畫圖來分析：
1、插入引起的迭代器失效
void test_vector10()
{
//刪除v中所有的偶數
my_vector::vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;//erase刪除的迭代器如果是最後一個元素++it導致程序崩潰
}
for (auto e : v)
cout << e << " ";
cout << endl;
return 0;
}
2、刪除引起的迭代器失效
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。