詳解C++?STL模擬實現(xiàn)vector
vector 概述
vector 的數(shù)據(jù)結(jié)構(gòu)安排及操作方式，與原生數(shù)組十分相似，兩者唯一的差別在于空間運用的靈活性。原生數(shù)組是靜態(tài)空間，一旦配置了就不能改變大?。籿ector 是動態(tài)空間，可以在插入過程中動態(tài)調(diào)整空間大小。vector 的實現(xiàn)技術(shù)，關(guān)鍵在于它對大小的控制及重新配置時的數(shù)據(jù)移動效率。
在文中，將會挑選 vector 的一些常用接口來模擬實現(xiàn)，但并不和標準庫中實現(xiàn)方式相同。標準庫中使用了大量內(nèi)存操作函數(shù)來提高效率，代碼晦澀難懂，不利用初學者學習。本文實現(xiàn)方式相對簡單，但也需要讀者有一定的 STL 使用經(jīng)驗。下面就讓我們開始吧。
接口總覽
namespace qgw {
template <class T>
class vector {
typedef T* iterator;
typedef const T* const_iterator;
typedef T& reference;
public:
// 默認成員函數(shù)
vector(); // 默認構(gòu)造函數(shù)
vector(size_t n, const T& val = T()); // 構(gòu)造 n 個 T 類型對象
vector(InputIterator first, InputIterator last);// 用一段區(qū)間構(gòu)造
vector(const vector<T>& v); // 拷貝構(gòu)造函數(shù)
vector<T>& operator=(const vector<T>& v); // 復(fù)制賦值函數(shù)
~vector();
// 迭代器函數(shù)
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
// 元素訪問
reference operator[](size_t pos);
const reference operator[](size_t pos) const;
reference back();
const reference back() const;
// 容量
bool empty() const;
size_t size() const;
size_t capacity() const;
void resize(size_t cnt, T val = T());
void reserve(size_t cap);
// 修改
iterator insert(iterator pos, const T& val);
void push_back(const T& val);
iterator erase(iterator pos);
iterator erase(iterator first, iterator last);
void pop_back();
void swap(vector<T>& v);
private:
iterator _start; // 表示目前使用空間的頭
iterator _finish; // 表示目前使用空間的尾
iterator _end_of_storage; // 表示已分配空間的尾
};
}
成員變量介紹
vector 中有三個成員變量，_start 指向使用空間的頭，_finish 指向使用空間的尾，_end_of_storage 指向已分配空間的尾。
由上圖也可以清晰的看出，_finish - _start 就是 size 的大小，_end_of_storage - _start 就是 capacity 的大小。
默認成員函數(shù)
構(gòu)造函數(shù)
默認構(gòu)造函數(shù)
vector 支持一個無參的構(gòu)造函數(shù)，在這個構(gòu)造函數(shù)中我們直接將上文中三個成員變量初始化為空即可。
/// @brief 默認構(gòu)造函數(shù)，將指針初始化為空
vector() {
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
構(gòu)造 n 個 T 類型對象
vector 支持構(gòu)造 n 個 值為 val 的對象?？梢韵扔?reserve開辟容量，在調(diào)用 push_back 插入即可。
注意：reserve 改變的是 capacity 的大小，不改變 size 的大小，先開辟容量為防止需多次擴容降低效率。
/// @brief 構(gòu)造 n 個值為 val 的對象
/// @param n 容器的大小
/// @param val 用來初始化容器元素的值
vector(size_t n, const T& val = T()) {
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
reserve(n);
for (int i = 0; i < n; ++i) {
push_back(val);
}
}
一段區(qū)間構(gòu)造
vector 支持使用一段迭代器區(qū)間構(gòu)造，區(qū)間范圍是 [first, last)，這里的迭代器不一定要是 vector 的迭代器，只有是具有輸入功能的迭代器都可以。
/// @brief 用給定的迭代器區(qū)間初始化，STL 中的區(qū)間均為左閉右開形式，即 [first, last)
/// @tparam InputIterator 所需最低階的迭代器類型，具有輸入功能的迭代器都可以
/// @param first 迭代器起始位置
/// @param last 迭代器終止位置
template< class InputIterator>
vector(InputIterator first, InputIterator last) {
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
// 和上一個類似，先開辟空間，尾減頭即為要開辟的個數(shù)
reserve(last - first);
while (first != last) {
push_back(*first);
++first;
}
}
析構(gòu)函數(shù)
析構(gòu)函數(shù)的實現(xiàn)很簡單，首先檢查容器是否為空，不為空就釋放空間，再把指針置空即可。
注意：因為我們開辟了連續(xù)的空間，要使用 delete[] 來釋放空間，對應(yīng)的也要使用 new[] 來開辟空間。即使我們只開辟一個空間也不能使用 new，否則對自定義類型在釋放時程序會崩潰。
具體原因請看：new 和 delete 為什么要匹配使用
/// @brief 釋放開辟的空間
~vector() {
if (_start != nullptr) {
// 釋放開辟的空間，從此處可以看出，開辟空間一定要用 new[]
// 否則對于自定義類型程序?qū)罎?
delete[] _start;
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
}
拷貝構(gòu)造函數(shù)
下面給出的實現(xiàn)方法比較簡單，直接用容器 v 初始化創(chuàng)建一個臨時容器 tmp，再交換 tmp 和 this 指針指向就好了。
此時 this 指向的容器是由 v 初始化出來的，tmp 指向了一個全空的容器，tmp 出了作用域就銷毀了。
需要注意的是此處一定要先將指針初始化為空，否則交換給 tmp 的指針要是不為空而是隨機值的話，tmp 銷毀時調(diào)用析構(gòu)函數(shù)就會導致程序崩潰。有些 ide（vs 2022） 可能會自動賦空，dev 下就不會，對指針類型編譯器本來就不會處理。
/// @brief 用給定容器初始化
/// @param v 用來初始化的容器
vector(const vector<T>& v) {
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
復(fù)制賦值函數(shù)
該函數(shù)與拷貝構(gòu)造函數(shù)類似，不同的是這里指針不應(yīng)賦空，否則指針原本指針指向的東西就無法正確釋放了。
/// @brief 替換容器內(nèi)容
/// @param v 用作數(shù)據(jù)源的另一容器
/// @return *this
vector<T>& operator=(const vector<T>& v) {
vector<T> tmp(v);
swap(tmp);
// 返回值為對象的引用，為的是可以連續(xù)賦值
return *this;
}
vector 的迭代器
vector 維護的是一個連續(xù)線性空間，不論元素是什么類型，普通指針都可以作為 vector 的迭代器滿足所有的條件，因此元素類型的指針就是 vector 的迭代器。
typedef T* iterator; typedef const T* const_iterator;
begin 和 end
begin 和 end 獲取的是正向迭代器，begin 指向第一個元素，end 指向最后一個元素的下一個位置，begin++ 是向后即 end 方向移動。
對應(yīng)的還有反向迭代器 rbegin 和 rend，rbegin 指向最后一個元素，rend 指向第一個元素的前一個位置，rbegin++ 是向前即 rend 方向移動。兩者對應(yīng)如下圖，因為反向迭代器復(fù)雜的多，這里就不實現(xiàn)了。
/// @brief 返回指向 vector 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
return _start;
}
// const 版本供 const 容器使用
const_iterator begin() const {
return _start;
}
/// @brief 返回指向 vector 最后元素后一元素的迭代器
/// @return 指向最后元素下一個位置的迭代器
iterator end() {
return _finish;
}
const_iterator end() const {
return _finish;
}
元素訪問
operator[]
vector 也支持向數(shù)組一樣的 [] 訪問方式，可以隨機讀取每個位置，返回該位置元素的引用。
需要注意的是，該函數(shù)并不做邊界檢查，需程序員自行檢查。
/// @brief 返回位于指定位置 pos 的元素的引用，不進行邊界檢查
/// @param pos 要返回的元素的位置
/// @return 到所需元素的引用
reference operator[](size_t pos) {
return _start[pos];
}
// 與上面的唯一不同就是用于 const 容器
const reference operator[](size_t pos) const {
return _start[pos];
}
back
back 可以獲取最后一個元素的引用。
/// @brief 返回到容器中最后一個元素的引用
/// @return 最后元素的引用
reference back() {
return *(end() - 1);
}
const reference back() const {
return *(end() - 1);
}
容量相關(guān)函數(shù)
size
根據(jù)圖可知 _finish - _start 即為 size。
/// @brief 返回容器中的元素數(shù)
/// @return 容器中的元素數(shù)量
size_t size() const {
return _finish - _start;
}
capacity
由圖可知 _end_of_storage - _start 即為 capacity。
/// @brief 返回容器當前已為之分配空間的元素數(shù)
/// @return 當前分配存儲的容量
size_t capacity() const {
return _end_of_storage - _start;
}
empty
檢查是否為空的方法很簡單，直接比較 _start 是否 _finish 相等即可，相等就為空，返回 true。
/// @brief 檢查容器是否無元素
/// @return 若容器為空則為 true，否則為 false
bool empty() const {
return _start == _finish;
}
resize
重設(shè)容器大小以容納 cnt 個元素。
如果當前大小大于 cnt，那么減小容器到它的開頭 cnt 個元素。
如果當前大小小于 cnt，那么就調(diào)用 insert 在最后插入 cnt - size() 個 val。
一定要注意，不能只改變 _finish，呢樣會因沒調(diào)用析構(gòu)函數(shù)從而引發(fā)內(nèi)存泄漏。你可能會想，我們會在最后容器銷毀的時候調(diào)用它的析構(gòu)函數(shù)，它的析構(gòu)函數(shù)中有 delete[]，這個語句會調(diào)用數(shù)據(jù)的析構(gòu)函數(shù)不會引起內(nèi)存泄漏。這樣想有一定的道理，但有沒有可能我們 vector 中一開始有 10 個元素，我們用 resize 將其大小改變?yōu)?5，再調(diào)用 5 次 insert 將其大小變?yōu)?10，最后對象銷毀調(diào)用析構(gòu)。
如上圖，我們一開始有 10 個 int* 類型的元素，分別指向一塊空間，后面 resize 為 5 后又添加了 5 個新的數(shù)據(jù)（用藍色標識）。當我們析構(gòu)的時候我們會析構(gòu)下圖中的元素，釋放它們指向的空間，那上圖中的 6、7、8、9、10 呢，沒辦法，因為我們已經(jīng)找不到它們的指針了，也就沒辦法釋放它們的空間了。
/// @brief 重設(shè)容器大小以容納 cot 個元素
/// @param cnt 容器的大小
/// @param val 用以初始化新元素的值
void resize(size_t cnt, T val = T()) {
if (cnt < size()) {
// 新大小小于原來的，需要將多余的部分刪除掉
// 不能只改變 _finish 指向，要使用 erase 來刪除，以便調(diào)用析構(gòu)函數(shù)
erase(begin() + cnt, end());
} else {
// 新空間更大，直接調(diào)用 insert 插入即可
for (int i = 0; i < cnt - size(); ++i) {
insert(end(), val);
}
}
}
reserve
reserve 用來預(yù)留存儲空間，如果要 push_back 大量的數(shù)據(jù)，可能會引起多次空間分配，從而多次轉(zhuǎn)移元素浪費大量時間?？梢灶A(yù)先開辟足夠的空間，減少空間分配的次數(shù)，來提高效率。
注意：
1.若 cap 的值大于當前的 capacity，則分配新存儲，否則不做任何事，也就是說 reserve 不會縮小容量
為什么一定要分配新存儲，而不是在原空間之后接一部分新空間（因為無法保證原空間之后還有足夠的可用空間）
2.同時，capacity 的改變也不會影響 size 的大小
reserve 擴容的思路也比較簡單，開辟一段新空間，將原數(shù)據(jù)拷貝到新空間，釋放舊空間即可。
需要注意的是，一定要在開始記錄之前元素的個數(shù)，因為 _finish 還指向原空間最后一個有效數(shù)據(jù)的下一個位置，需要將其更新指向新空間。
/// @brief 增加 vector 的容量到大于或等于 cap 的值
/// @param cap vector 的新容量
void reserve(size_t cap) {
size_t len = size();
if (cap > capacity()) {
T* tmp = new T[cap];
if (_start != nullptr) {
// 如果容器內(nèi)之前有數(shù)據(jù)，將數(shù)據(jù)拷貝到新位置
for (int i = 0; i < size(); ++i) {
tmp[i] = _start[i];
}
delete[] _start; // 釋放掉舊的空間
}
_start = tmp;
}
// 指向新的地址空間
_finish = _start + len;
_end_of_storage = _start + cap;
}修改函數(shù)
insert
insert 函數(shù)的功能很多，可以在指定位置插入一個或多個值，也可以插入一段區(qū)間。這里我們只實現(xiàn)插入一個值的函數(shù)，在 pos 前面插入 val。
插入之前首先要檢查容量，不夠就進行擴容。然后將插入位置之后的數(shù)據(jù)向后挪動一個位置，插入 val 即可。
需要注意的是，擴容的話需要提前記錄 pos 之前的元素個數(shù)。因為 pos 指向的是之前空間的某個位置，要將其更新為新空間的地址。
/// @brief 將 val 插入到 pos 迭代器之前
/// @param pos 將內(nèi)容插入到它前面的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入 val 的迭代器
iterator insert(iterator pos, const T& val) {
// 檢查參數(shù)是否在合法返回，assert 只在 degug 版本下有效
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage) {
// 首先檢查容量，空間不夠要進行擴容
// 先記錄插入位置之前元素個數(shù)
size_t len = pos - _start;
// 第一次開辟空間給 10 個，后續(xù)擴容為 2 倍
size_t newCap = capacity() == 0 ? 10 : capacity() * 2;
reserve(newCap);
// 更新 pos 在新空間中的位置
pos = _start + len;
}
// 將插入位置之后的所有數(shù)據(jù)向后挪動一個位置
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
push_back
push_back 是向容器的最后添加一個元素，直接調(diào)用 insert 即可。
/// @brief 添加給定元素 val 到容器尾
/// @param val 要添加的元素值
void push_back(const T& val) {
// 直接調(diào)用 insert 即可
insert(end(), val);
}
erase
erase 從容器中刪除指定的元素：
1.移除位于 pos 的元素
2.移除范圍 [first, last) 中的元素
移除 pos 位置的元素方法很簡單，首先調(diào)用該位置的析構(gòu)函數(shù)，然后將后面的數(shù)據(jù)向前移動一個位置，最后的 --_finish 就可以了。
/// @brief 從容器擦除指定位置的元素
/// @param pos 指向要移除的元素的迭代器
/// @return 移除元素之后的迭代器
iterator erase(iterator pos) {
assert(pos >= _start && pos < _finish);
// 在 pos 位置調(diào)用析構(gòu)函數(shù)，釋放資源
pos->~T();
// 將 pos 位置之后的的元素都向前移動一個位置
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
// 此時的 pos 指向沒刪除前 pos 位置下一個元素
return pos;
}范圍刪除同樣也很簡單，首先要計算出要刪除的個數(shù)，循環(huán)調(diào)用 erase 刪除就可以了。
注：下面這種循環(huán)調(diào)用的方式效率十分低，庫函數(shù)并沒有使用這種方法，庫函數(shù)首先對要刪除的范圍調(diào)用析構(gòu)函數(shù)，然后將區(qū)間后面的數(shù)據(jù)移到前面。這樣就只會移動一次數(shù)據(jù)，不向下面需要移動 cnt 次。
/// @brief 移除一段范圍的元素
/// @param first 要移除的起始范圍
/// @param last 要移除的結(jié)束返回
/// @return 移除的最后一個元素之后的迭代器
iterator erase(iterator first, iterator last) {
int cnt = last - first;
while (cnt--) {
first = erase(first);
}
return first;
}
pop_back
pop_back 用來刪除容器的最后一個元素，直接調(diào)用 erase 刪除就行。
/// @brief 移除容器最后一個元素
void pop_back() {
erase(_finish - 1);
}
swap
swap 函數(shù)可以用來交換兩個容器的內(nèi)容，不過不用實際交換數(shù)據(jù)，只需要改變兩個容器指針的指向即可。
/// @brief 交換 this 指向的容器和 v 的內(nèi)容
/// @param v 要交換內(nèi)容的容器
void swap(vector<T>& v) {
// 直接交換所有指針即可
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}到此這篇關(guān)于詳解C++ STL模擬實現(xiàn)vector的文章就介紹到這了,更多相關(guān)C++ STL vector內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了C++實現(xiàn)圖形界面雙人五子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
C++中fstream,ifstream及ofstream用法淺析
這篇文章主要介紹了C++中fstream,ifstream及ofstream用法,適合C++初學者學習文件流的操作,需要的朋友可以參考下2014-08-08
通過先序遍歷和中序遍歷后的序列還原二叉樹(實現(xiàn)方法)
下面小編就為大家?guī)硪黄ㄟ^先序遍歷和中序遍歷后的序列還原二叉樹(實現(xiàn)方法)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要為大家詳細介紹了C語言實現(xiàn)歸并排序，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-08-08
這篇文章主要為大家詳細介紹了C語言面向?qū)ο缶幊讨械姆庋b，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了c語言設(shè)計模式之單例模式中的餓漢與懶漢詳解,單例模式是指一個類只能創(chuàng)建一個對象，保證系統(tǒng)中該類只有一個實例，并提供一個可供訪問的全局訪問點，該實例被所有程序模塊共享，需要的朋友可以參考下2023-08-08
這篇文章主要為大家詳細介紹了C++實現(xiàn)猜數(shù)字游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要介紹了C語言多種獲取字符串長度的方法,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
c/c++?Error:?redefinition?of?'xxx'的問題及解決方法
兩個類/文件同時引用定義ReplyInfo的頭文件,會造成頭文件中定義重復(fù)定義,本文給大家分享c/c++?Error:?redefinition?of?‘xxx’?的問題及解決方法,感興趣的朋友一起看看吧2023-08-08
這篇文章主要為大家詳細介紹了C++提取文件中信息的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-07-07