1.為什么要模擬實(shí)現(xiàn)vector?
模擬實(shí)現(xiàn)vector是為了深入理解和學(xué)習(xí)C++標(biāo)準(zhǔn)庫中vector容器的工作原理和實(shí)現(xiàn)細(xì)節(jié)。
vector是C++標(biāo)準(zhǔn)庫中最常用的容器之一，它提供了動(dòng)態(tài)數(shù)組的功能，并且具有自動(dòng)擴(kuò)容和內(nèi)存管理的特性，使得在使用時(shí)非常方便。
模擬實(shí)現(xiàn)vector有以下幾個(gè)優(yōu)點(diǎn)：
- 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法：實(shí)現(xiàn)vector需要涉及到動(dòng)態(tài)數(shù)組的增刪查改等操作，這可以讓開發(fā)者學(xué)習(xí)到關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的相關(guān)知識(shí)。
- 理解內(nèi)存管理：vector需要管理動(dòng)態(tài)內(nèi)存分配和釋放，了解如何使用指針、動(dòng)態(tài)分配內(nèi)存以及防止內(nèi)存泄漏等問題是很重要的。
- 理解模板編程：vector是一個(gè)通用的容器，可以存儲(chǔ)不同類型的元素。模擬實(shí)現(xiàn)vector需要涉及到模板編程，讓開發(fā)者更好地理解C++中的模板機(jī)制。
- 提高編程技巧：通過實(shí)現(xiàn)vector，開發(fā)者可以鍛煉自己的編程技巧和代碼設(shè)計(jì)能力，同時(shí)也可以發(fā)現(xiàn)一些潛在的問題和改進(jìn)的空間。
雖然C++標(biāo)準(zhǔn)庫中已經(jīng)提供了vector容器，但是模擬實(shí)現(xiàn)vector對(duì)于學(xué)習(xí)和理解C++的底層實(shí)現(xiàn)以及算法和數(shù)據(jù)結(jié)構(gòu)有很大的幫助。實(shí)際開發(fā)中，我們通常使用標(biāo)準(zhǔn)庫中的vector，因?yàn)樗呀?jīng)經(jīng)過了充分的測試和優(yōu)化，具有更好的性能和穩(wěn)定性。然而，通過模擬實(shí)現(xiàn)vector，我們可以更好地理解背后的原理和設(shè)計(jì)思想。
2.模擬實(shí)現(xiàn)vector需要注意哪些問題?
在模擬實(shí)現(xiàn)vector時(shí)，需要注意以下幾個(gè)關(guān)鍵問題：
- 動(dòng)態(tài)內(nèi)存管理：vector是動(dòng)態(tài)數(shù)組，需要在運(yùn)行時(shí)動(dòng)態(tài)分配內(nèi)存。要確保在插入、刪除元素時(shí)正確地分配和釋放內(nèi)存，避免內(nèi)存泄漏和懸掛指針的問題。
- 自動(dòng)擴(kuò)容：vector具有自動(dòng)擴(kuò)容的功能，當(dāng)容器中的元素?cái)?shù)量超過當(dāng)前容量時(shí)，需要重新分配更大的內(nèi)存空間，并將原有的元素拷貝到新的內(nèi)存空間中。
- 模板編程：vector是一個(gè)通用的容器，可以存儲(chǔ)不同類型的元素。因此，在模擬實(shí)現(xiàn)vector時(shí)需要使用模板編程，確保容器可以適用于不同類型的數(shù)據(jù)。
- 迭代器：vector應(yīng)該提供迭代器用于訪問容器中的元素。迭代器應(yīng)該支持指針的各種操作，如指針?biāo)阈g(shù)、解引用等。
- 成員函數(shù)和接口：模擬實(shí)現(xiàn)的vector應(yīng)該提供類似于標(biāo)準(zhǔn)庫中vector的成員函數(shù)和接口，例如push_back、pop_back、size、capacity等等。
- 異常安全性：在模擬實(shí)現(xiàn)vector的過程中，要確保對(duì)異常的處理，避免因?yàn)楫惓６鴮?dǎo)致內(nèi)存泄漏或數(shù)據(jù)結(jié)構(gòu)被破壞。
- 性能優(yōu)化：模擬實(shí)現(xiàn)的vector可能不如標(biāo)準(zhǔn)庫中的vector性能優(yōu)越，但是仍然要考慮一些性能優(yōu)化的方法，例如避免頻繁的內(nèi)存分配和釋放、減少不必要的拷貝等。
- 測試：在實(shí)現(xiàn)過程中，要進(jìn)行充分的測試，確保vector的各種功能和接口都能正確地工作，并且能夠處理各種邊界情況。
總的來說，模擬實(shí)現(xiàn)vector需要考慮到數(shù)據(jù)結(jié)構(gòu)、內(nèi)存管理、模板編程、異常處理以及性能優(yōu)化等方面的問題，確保實(shí)現(xiàn)的容器能夠穩(wěn)定、高效地工作。模擬實(shí)現(xiàn)vector是一個(gè)很好的學(xué)習(xí)和鍛煉編程能力的練習(xí)，同時(shí)也能更深入地理解C++標(biāo)準(zhǔn)庫中容器的原理和設(shè)計(jì)思想。
3.vector模擬實(shí)現(xiàn)
3.1 命名空間vector的成員變量定義
要定義成員變量，首先我們要了解vector的成員變量有哪些，它和我們?cè)跀?shù)據(jù)結(jié)構(gòu)中的順序表雖然很像，但又有很多不同之處，在vector中三個(gè)很重要的成員變量分別是：
iterator _start: 這是指向第一個(gè)元素的迭代器，它表示容器中的有效元素的起始位置。iterator _finish: 這是指向最后一個(gè)元素的下一個(gè)位置的迭代器，也就是超出有效范圍的位置。它用于表示容器中已經(jīng)存儲(chǔ)的元素的末尾位置。iterator _end_of_storage: 這是指向分配的內(nèi)存空間的末尾位置的迭代器，即容器實(shí)際分配的內(nèi)存空間的結(jié)束位置。這個(gè)位置可能會(huì)在容器擴(kuò)容時(shí)變化。
這樣的定義是為了將容器的內(nèi)存管理和元素訪問分離開來，通過這三個(gè)迭代器，vector可以有效地管理容器的內(nèi)存空間和元素的訪問。
當(dāng)vector中的元素?cái)?shù)量超過當(dāng)前內(nèi)存空間的容量時(shí)，會(huì)進(jìn)行擴(kuò)容操作。此時(shí)，會(huì)重新分配更大的內(nèi)存空間，并將已有的元素從舊內(nèi)存復(fù)制到新內(nèi)存，然后更新 _start、_finish 和 _end_of_storage 迭代器的值，使其正確地指向新的內(nèi)存空間。
定義這三個(gè)迭代器的方式，使得vector能夠在不同的操作下保持內(nèi)存管理和元素訪問的一致性。它們將內(nèi)存的分配和元素的訪問解耦，使得vector的實(shí)現(xiàn)更加靈活和高效。
所以第一步我們需要先定義迭代器和對(duì)應(yīng)的迭代器成員
namespace xzq//為了和原vector做區(qū)分，放在不同名的命名空間內(nèi)
{
template<class T>//模板命名
class vector
{
public:
typedef T* iterator; //變量模板迭代器指針
typedef const T* const_iterator; //常量模板迭代器指針
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
3.2 迭代器成員函數(shù)begin()和end()定義
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
iterator begin()：返回一個(gè)指向容器中第一個(gè)元素的迭代器（非 const 版本）。
iterator end()：返回一個(gè)指向容器中最后一個(gè)元素的后一個(gè)位置的迭代器（非 const 版本）。
const_iterator begin() const：返回一個(gè)指向容器中第一個(gè)元素的迭代器（const 版本，用于常量對(duì)象）。
const_iterator end() const：返回一個(gè)指向容器中最后一個(gè)元素的后一個(gè)位置的迭代器（const 版本，用于常量對(duì)象）。
這些函數(shù)允許你通過迭代器遍歷訪問 vector 中的元素。區(qū)別在于，非 const 版本的函數(shù)返回的迭代器可以用于修改元素，而 const 版本的函數(shù)返回的迭代器只能用于訪問元素而不能修改。
3.3 構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)和析構(gòu)函數(shù)
3.3.1 構(gòu)造函數(shù)
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
這是一個(gè)默認(rèn)構(gòu)造函數(shù)的實(shí)現(xiàn)，用于初始化一個(gè)空的 vector 對(duì)象。在這個(gè)構(gòu)造函數(shù)中，通過初始化成員變量 _start、_finish 和 _end_of_storage 為 nullptr，表示該 vector 對(duì)象沒有分配任何內(nèi)存空間，也沒有存儲(chǔ)任何元素。
這個(gè)構(gòu)造函數(shù)在創(chuàng)建一個(gè)空的 vector 對(duì)象時(shí)使用，因?yàn)閯傞_始還沒有元素需要存儲(chǔ)，所以內(nèi)存空間的指針都被設(shè)置為 nullptr。隨后在 vector 的操作中，當(dāng)需要添加元素時(shí)，會(huì)根據(jù)需要進(jìn)行內(nèi)存空間的分配，并逐步調(diào)整這些指針的值。
總之，這個(gè)構(gòu)造函數(shù)的目的是創(chuàng)建一個(gè)空的 vector 對(duì)象，并初始化內(nèi)部的迭代器成員，為后續(xù)的操作做好準(zhǔn)備。
3.3.2 拷貝構(gòu)造函數(shù)
vector(const vector<T>& v)三種寫法
第一種寫法：直接分配內(nèi)存并逐個(gè)賦值
vector(const vector<T>& v)
{
_start = new T[v.size()]; // v.capacity()也可以
//memcpy(_start, v._start, sizeof(T)*v.size());
for (size_t i = 0; i < v.size(); ++i)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_end_of_storage = _start + v.size();
}
這里建議是不要用memcpy函數(shù)，memcpy 不會(huì)調(diào)用元素類型的拷貝構(gòu)造函數(shù)，可能會(huì)導(dǎo)致未初始化或釋放的內(nèi)存問題。它僅適用于 POD（Plain Old Data）類型，對(duì)于非 POD 類型（如含有指針、自定義構(gòu)造函數(shù)等的類型），使用 memcpy 可能會(huì)導(dǎo)致錯(cuò)誤。
優(yōu)點(diǎn)：
直觀：清晰地展示了如何手動(dòng)分配內(nèi)存、逐個(gè)賦值元素。
缺點(diǎn)：
重復(fù)操作：需要逐個(gè)賦值元素，可能會(huì)有一些不必要的重復(fù)操作。
內(nèi)存泄漏：如果在分配內(nèi)存和賦值之間出現(xiàn)異常，可能導(dǎo)致內(nèi)存泄漏。
第二種寫法：利用 push_back 和 reserve 實(shí)現(xiàn)
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.size());
for (const auto& e : v)
{
push_back(e);
}
}
優(yōu)點(diǎn)：
避免重復(fù)操作：利用 push_back 直接將元素插入，避免了逐個(gè)賦值的重復(fù)操作。
缺點(diǎn)：
性能問題：使用 push_back 可能會(huì)多次分配內(nèi)存和釋放內(nèi)存，性能較差。
可能出現(xiàn)異常：如果 push_back 中的內(nèi)存分配失敗，可能會(huì)導(dǎo)致異常。
第三種寫法：利用臨時(shí) vector 進(jìn)行交換
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
這種寫法要建立在另一種迭代器類型的拷貝構(gòu)造。
優(yōu)點(diǎn)：
交換技巧：通過構(gòu)造一個(gè)臨時(shí) vector，然后將當(dāng)前 vector 和臨時(shí) vector 進(jìn)行交換，避免了重復(fù)內(nèi)存操作。
缺點(diǎn)：
需要額外內(nèi)存：需要額外的內(nèi)存來構(gòu)造臨時(shí) vector。
不直觀：可能不太直觀，需要理解 swap 的交換機(jī)制。
綜合考慮，第三種寫法可能是最佳的選擇，因?yàn)樗苊饬酥貜?fù)內(nèi)存操作，同時(shí)通過利用 swap 技巧來保證異常安全性。然而，第二種寫法也是一個(gè)不錯(cuò)的選擇，特別是在不要求高性能的情況下，代碼清晰易懂。至于第一種寫法，由于可能出現(xiàn)內(nèi)存泄漏和異常不安全問題，可能并不推薦使用。
template <class InputIterator>vector(InputIterator first, InputIterator last)
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
這個(gè)構(gòu)造函數(shù)模板實(shí)現(xiàn)了通過迭代器范圍初始化 vector。它遍歷輸入的迭代器范圍，將每個(gè)元素通過 push_back 插入到 vector 中。這種方式非常適合處理容器的初始化，無論容器中元素的數(shù)量和類型如何，都可以通過迭代器范圍方便地初始化一個(gè)新的 vector。這種構(gòu)造函數(shù)利用了迭代器提供的通用性，使得代碼更加靈活，可以適用于各種元素類型，包括內(nèi)置類型和用戶自定義類型。這個(gè)構(gòu)造函數(shù)模板充分展示了 C++ 中的泛型編程思想，使得代碼可以適用于不同的情境和數(shù)據(jù)類型。
上一種拷貝構(gòu)造復(fù)用了此類迭代器拷貝構(gòu)造。
vector(size_t n, const T& val = T())
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
這個(gè)構(gòu)造函數(shù)實(shí)現(xiàn)了通過重復(fù)插入相同值來初始化 vector。它接受兩個(gè)參數(shù)，第一個(gè)參數(shù)是初始化的元素?cái)?shù)量 n，第二個(gè)參數(shù)是元素的初始值 val。這種構(gòu)造函數(shù)的作用是創(chuàng)建一個(gè)包含了 n 個(gè)相同值 val 的 vector。通過循環(huán)將相同值插入容器中，實(shí)現(xiàn)了快速初始化相同值的需求。默認(rèn)情況下，val 的值使用了默認(rèn)構(gòu)造函數(shù)來初始化，因此可以在調(diào)用時(shí)省略。
這個(gè)構(gòu)造函數(shù)在某些場景下可以提高初始化的效率，尤其是當(dāng)需要初始化大量相同值的元素時(shí)，避免了反復(fù)調(diào)用 push_back 的開銷，而直接在內(nèi)存中復(fù)制值。
但最好加上下面這個(gè)版本
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
防止出現(xiàn)下面這種情況
vector<int> v2(3, 10);
這樣調(diào)用拷貝構(gòu)造時(shí)，可能會(huì)優(yōu)先調(diào)用template <class InputIterator> vector(InputIterator first, InputIterator last)，因?yàn)閮蓚€(gè)操作數(shù)為同一類型，編譯器在類中找匹配函數(shù)時(shí)，會(huì)找更相近匹配的，此時(shí)會(huì)發(fā)生錯(cuò)誤，所以最好加上下面這個(gè)int版本，可能你會(huì)疑問，為什么不直接用int版本，這是因?yàn)関ector拷貝函數(shù)的定義就是無符號(hào)整形。
3.3.3 析構(gòu)函數(shù)
~vector()
{
delete[] _start; // 釋放存儲(chǔ)元素的內(nèi)存塊
_start = _finish = _end_of_storage = nullptr; // 將成員指針置為 nullptr
}
在析構(gòu)函數(shù)中，首先使用 delete[] 刪除存儲(chǔ)元素的內(nèi)存塊 _start，這會(huì)釋放所有存儲(chǔ)在 vector 中的元素所占用的內(nèi)存。接著，將 _start、_finish、_end_of_storage 這三個(gè)成員指針全部置為 nullptr，以避免在析構(gòu)函數(shù)執(zhí)行完畢后再次調(diào)用它們引發(fā)問題。
這個(gè)析構(gòu)函數(shù)的作用是確保在 vector 對(duì)象被銷毀時(shí)，所占用的內(nèi)存得到釋放，避免內(nèi)存泄漏。
3.4 容量函數(shù)、元素訪問函數(shù)和增刪查改函數(shù)
3.4.1 容量函數(shù)
capacity()
size_t capacity() const
{
return _end_of_storage - _start;
}
這個(gè) capacity() 成員函數(shù)返回的是 vector 內(nèi)部分配的存儲(chǔ)空間的容量，即當(dāng)前可容納的元素個(gè)數(shù)，而不是當(dāng)前已經(jīng)存儲(chǔ)的元素個(gè)數(shù)（使用 size() 獲取）。這個(gè)函數(shù)的實(shí)現(xiàn)很簡單，它返回 _end_of_storage 指針減去 _start 指針?biāo)玫降牟钪?/mark>，也就是當(dāng)前分配的存儲(chǔ)空間可以容納的元素個(gè)數(shù)。這是因?yàn)樵?vector 的實(shí)現(xiàn)中，連續(xù)的存儲(chǔ)空間被分配在 _start 和 _end_of_storage 之間，所以兩者之間的距離就代表了容量。
size()
size_t size() const
{
return _finish - _start;
}
這個(gè) size() 函數(shù)用于返回 vector 中元素的個(gè)數(shù)，它的實(shí)現(xiàn)通過計(jì)算 _finish 指針和 _start 指針之間的距離（偏移量）來得到。由于 _finish 和 _start 分別指向 vector 內(nèi)存空間中的元素的尾后位置和起始位置，它們之間的距離就是 vector 中元素的個(gè)數(shù)。這個(gè)函數(shù)在 O(1) 的時(shí)間復(fù)雜度下返回 vector 中的元素個(gè)數(shù)。
reserve()
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T)*sz);
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
這個(gè) reserve(size_t n) 函數(shù)用于預(yù)留內(nèi)存空間，確保 vector 至少能容納 n 個(gè)元素，以減少頻繁的內(nèi)存重新分配。如果當(dāng)前的內(nèi)存空間不足以容納 n 個(gè)元素，它會(huì)重新分配一個(gè)新的內(nèi)存空間，并將原有的元素復(fù)制到新的內(nèi)存中。
這個(gè)函數(shù)首先檢查要求預(yù)留的內(nèi)存是否超過當(dāng)前的容量（capacity）。如果超過了，它會(huì)重新分配一個(gè)新的內(nèi)存空間，并將原有的元素復(fù)制到新的內(nèi)存中。然后更新 _start、_finish 和 _end_of_storage 指針，以反映新的內(nèi)存布局。
需要注意的是，這個(gè)函數(shù)不會(huì)改變 vector 中元素的個(gè)數(shù)，只會(huì)改變內(nèi)存的分配情況。
這里使用 for 循環(huán)和 memcpy 進(jìn)行內(nèi)存復(fù)制有一些區(qū)別和注意事項(xiàng)：
數(shù)據(jù)類型限制：memcpy是按字節(jié)復(fù)制的，不會(huì)執(zhí)行元素類型的構(gòu)造函數(shù)。如果存儲(chǔ)的是類對(duì)象，可能會(huì)導(dǎo)致未預(yù)期的行為。使用 for 循環(huán)時(shí)，會(huì)調(diào)用元素的拷貝構(gòu)造函數(shù)，確保正確地復(fù)制每個(gè)元素。
可移植性：memcpy 是一個(gè)底層的內(nèi)存復(fù)制函數(shù)，其使用可能會(huì)受到不同平臺(tái)的影響。而使用 for 循環(huán)是一種更加通用和可移植的方式。
類型安全：使用memcpy 需要確保元素的大小和布局是適合的，否則可能會(huì)導(dǎo)致數(shù)據(jù)損壞。而 for 循環(huán)在拷貝每個(gè)元素時(shí)會(huì)確保類型的正確性。
可讀性：for 循環(huán)更容易理解和維護(hù)，可以清晰地看到每個(gè)元素的操作。
綜上所述，如果是簡單的數(shù)據(jù)類型，使用 memcpy 可能會(huì)更高效，但在涉及類對(duì)象、復(fù)雜數(shù)據(jù)結(jié)構(gòu)或類型安全性的情況下，使用 for 循環(huán)更為安全和推薦。
resize()
void resize(size_t n, const T& val = T())
{
if (n < size()) {
// 縮小容器大小
for (size_t i = n; i < size(); ++i) {
_start[i].~T(); // 銷毀元素
}
_finish = _start + n;
}
else if (n > size()) {
if (n > capacity()) {
// 需要重新分配內(nèi)存
T* new_start = new T[n];
for (size_t i = 0; i < size(); ++i) {
new (&new_start[i]) T(std::move(_start[i])); // 移動(dòng)構(gòu)造元素
_start[i].~T(); // 銷毀原來的元素
}
delete[] _start;
_start = new_start;
_finish = _start + size();
_end_of_storage = _start + n;
}
// 構(gòu)造新添加的元素
for (size_t i = size(); i < n; ++i) {
new (&_start[i]) T(val);
}
_finish = _start + n;
}
// 若 n == size() 則不需要進(jìn)行任何操作
}
首先，函數(shù)檢查是否需要縮小容器大小。如果 n 小于當(dāng)前大?。╯ize()），則會(huì)進(jìn)入縮小容器大小的分支。
在這種情況下，函數(shù)會(huì)逐個(gè)調(diào)用 _start[i].~T()，即對(duì)應(yīng)位置元素的析構(gòu)函數(shù)，以銷毀多余的元素。然后，將 _finish 指針更新為 _start + n，表示容器只包含前 n 個(gè)元素。如果== n 大于當(dāng)前大小==，那么函數(shù)會(huì)檢查是否需要重新分配內(nèi)存。如果 n 大于當(dāng)前容量（capacity()），則會(huì)進(jìn)入重新分配內(nèi)存的分支。
在這種情況下，函數(shù)會(huì)創(chuàng)建一個(gè)新的內(nèi)存塊 new_start，然后將當(dāng)前容器中的元素逐個(gè)移動(dòng)構(gòu)造到新的內(nèi)存塊中，同時(shí)析構(gòu)原來位置的元素。然后，釋放原來的內(nèi)存塊 _start，并更新 _start、_finish 和 _end_of_storage 指針。
無論是縮小容器大小還是重新分配內(nèi)存，函數(shù)都會(huì)在容器尾部構(gòu)造新的元素，以填充到 n 個(gè)元素。使用 new (&_start[i]) T(val) 來在指定位置構(gòu)造元素，其中 val 為傳入的默認(rèn)值。然后，將 _finish 指針更新為 _start + n。
3.4.2 元素訪問函數(shù)
operator[]
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
這兩個(gè)重載的 operator[] 函數(shù)分別用于訪問 vector 中指定位置的元素。一個(gè)是 const 版本，用于在常量對(duì)象上獲取元素值，另一個(gè)是非 const 版本，用于在非常量對(duì)象上獲取或修改元素值。這兩個(gè)函數(shù)通過檢查索引 pos 是否在合法范圍內(nèi)來保證不越界訪問。非 const 版本返回一個(gè)非常量引用，這允許用戶通過該操作符修改 vector 中的元素值。而 const 版本返回一個(gè)常量引用，用于在常量對(duì)象上訪問元素值，但不允許修改。
front()
T& front()
{
assert(size() > 0);
return *_start;
}
首先，函數(shù)使用 assert 宏來檢查容器的大小是否大于 0，確保容器中至少有一個(gè)元素。
然后，函數(shù)返回 _start 指針指向的元素的引用，即容器的第一個(gè)元素。
back()
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
首先，函數(shù)使用 assert 宏來檢查容器的大小是否大于 0，確保容器中至少有一個(gè)元素。
然后，函數(shù)返回 _finish - 1 指針指向的元素的引用，即容器的最后一個(gè)元素。
3.4.3 增刪查改函數(shù)
push_back()
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
//insert(end(), x);
}
首先，函數(shù)檢查 _finish 指針是否等于 _end_of_storage，即是否達(dá)到了當(dāng)前容器的容量上限。如果達(dá)到了容量上限，說明沒有足夠的空間存放新元素，因此需要進(jìn)行內(nèi)存重新分配。
內(nèi)存重新分配時(shí)，使用 reserve 函數(shù)，如果當(dāng)前容量為 0，則分配至少 4 個(gè)元素的空間，否則將容量擴(kuò)展為當(dāng)前容量的兩倍。然后，函數(shù)將新元素 x 賦值給 _finish 指針指向的位置，即當(dāng)前容器的末尾。然后，通過遞增 _finish 指針，將 _finish 指向下一個(gè)可用位置。
pop_back()
void pop_back()
{
assert(_finish > _start);
--_finish;
}
首先，函數(shù)使用 assert 宏來檢查 _finish 指針是否大于 _start 指針。這是一個(gè)斷言，用于確保在 _finish 小于或等于 _start 時(shí)不會(huì)發(fā)生錯(cuò)誤。如果 _finish 不大于 _start，則斷言會(huì)觸發(fā)錯(cuò)誤，幫助在開發(fā)過程中發(fā)現(xiàn)問題。
接著，函數(shù)將 _finish 指針遞減 1，從而使其指向容器中的倒數(shù)第二個(gè)元素，即刪除了最后一個(gè)元素。
iterator insert()
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
// 挪動(dòng)數(shù)據(jù)
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
首先，函數(shù)使用 assert 宏來檢查 pos 是否在 _start 和 _finish 之間，確保插入位置在合法范圍內(nèi)。然后，函數(shù)檢查容器是否已滿，即 _finish 是否等于 _end_of_storage。如果容器已滿，需要擴(kuò)容。首先計(jì)算插入位置相對(duì)于 _start 的偏移量 len，以便在插入后重新定位 pos，以防擴(kuò)容導(dǎo)致迭代器失效。接著根據(jù)擴(kuò)容規(guī)則進(jìn)行擴(kuò)容操作，將 _start 移動(dòng)到新分配的內(nèi)存中。在容器中插入元素之前，需要將插入位置之后的元素往后挪動(dòng)一個(gè)位置。使用一個(gè)循環(huán)從 _finish - 1 開始，逐個(gè)將元素向后移動(dòng)一位，為新元素騰出空間。將新元素 x 插入到指定的位置 pos。最后，遞增 _finish 指針，表示容器中多了一個(gè)元素，然后返回插入位置的迭代器。
iterator erase()
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
首先，函數(shù)使用 assert 宏來檢查 pos 是否在 _start 和 _finish 之間，確保刪除位置在合法范圍內(nèi)。
然后，函數(shù)創(chuàng)建一個(gè)名為 begin 的迭代器，初始值為 pos 的下一個(gè)位置，即要?jiǎng)h除的元素之后的位置。
接著，使用一個(gè)循環(huán)將 begin 位置及其后面的元素逐個(gè)向前移動(dòng)一個(gè)位置，覆蓋掉要?jiǎng)h除的元素。這樣就相當(dāng)于將刪除位置的元素覆蓋掉，從而實(shí)現(xiàn)刪除操作。
最后，遞減 _finish 指針，表示容器中少了一個(gè)元素，然后返回原始的刪除位置的迭代器。
3.4.4 賦值運(yùn)算符重載
operator=
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
這個(gè)賦值運(yùn)算符重載是一個(gè)實(shí)現(xiàn) C++ 中的拷貝交換技術(shù)（Copy-and-Swap Idiom）的常見寫法，用于實(shí)現(xiàn)自定義的賦值操作。該賦值運(yùn)算符接受一個(gè)傳值的參數(shù) v，這里通過傳值來進(jìn)行拷貝構(gòu)造一個(gè)臨時(shí)的 vector 對(duì)象，然后調(diào)用 swap(v) 實(shí)現(xiàn)了將當(dāng)前對(duì)象的數(shù)據(jù)與臨時(shí)對(duì)象進(jìn)行交換。這樣，臨時(shí)對(duì)象的數(shù)據(jù)會(huì)被賦值給當(dāng)前對(duì)象，而臨時(shí)對(duì)象會(huì)在函數(shù)結(jié)束時(shí)被析構(gòu)，從而釋放掉原來當(dāng)前對(duì)象的資源。
這種寫法的好處在于它可以避免拷貝構(gòu)造和析構(gòu)造成的額外開銷，從而提高了效率。同時(shí)，交換操作的實(shí)現(xiàn)通常在類內(nèi)部對(duì)各個(gè)成員進(jìn)行指針交換，因此不會(huì)涉及數(shù)據(jù)的實(shí)際拷貝。
總的來說，這個(gè)賦值運(yùn)算符實(shí)現(xiàn)了一種高效的賦值操作，是 C++ 中常用的實(shí)現(xiàn)方式之一。文章來源：http://www.zghlxwxcb.cn/news/detail-629887.html
vector模擬實(shí)現(xiàn)全部代碼
#pragma once
#include <assert.h>
#include <iostream>
namespace bit
{
template<class T>
class vector
{
public:
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;
}
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
//vector(const vector<T>& v)
//{
// _start = new T[v.size()]; // v.capacity()也可以
// //memcpy(_start, v._start, sizeof(T)*v.size());
// for (size_t i = 0; i < v.size(); ++i)
// {
// _start[i] = v._start[i];
// }
// _finish = _start + v.size();
// _end_of_storage = _start + v.size();
//}
/*vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.size());
for (const auto& e : v)
{
push_back(e);
}
}*/
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
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(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
// v1 = v2
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
size_t size() const
{
return _finish - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T)*sz);
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n < size()) {
// 縮小容器大小
for (size_t i = n; i < size(); ++i) {
_start[i].~T(); // 銷毀元素
}
_finish = _start + n;
}
else if (n > size()) {
if (n > capacity()) {
// 需要重新分配內(nèi)存
T* new_start = new T[n];
for (size_t i = 0; i < size(); ++i) {
new (&new_start[i]) T(std::move(_start[i])); // 移動(dòng)構(gòu)造元素
_start[i].~T(); // 銷毀原來的元素
}
delete[] _start;
_start = new_start;
_finish = _start + size();
_end_of_storage = _start + n;
}
// 構(gòu)造新添加的元素
for (size_t i = size(); i < n; ++i) {
new (&_start[i]) T(val);
}
_finish = _start + n;
}
// 若 n == size() 則不需要進(jìn)行任何操作
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
//insert(end(), x);
}
void pop_back()
{
assert(_finish > _start);
--_finish;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
// 挪動(dòng)數(shù)據(jù)
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
// stl 規(guī)定erase返回刪除位置下一個(gè)位置迭代器
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
T& front()
{
assert(size() > 0);
return *_start;
}
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
結(jié)語
有興趣的小伙伴可以關(guān)注作者，如果覺得內(nèi)容不錯(cuò)，請(qǐng)給個(gè)一鍵三連吧，蟹蟹你喲?。。?br> 制作不易，如有不正之處敬請(qǐng)指出
感謝大家的來訪，UU們的觀看是我堅(jiān)持下去的動(dòng)力
在時(shí)間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧！??！文章來源地址http://www.zghlxwxcb.cn/news/detail-629887.html
到了這里，關(guān)于C++初階之一篇文章讓你掌握vector（模擬實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
