【C++】vector的使用及其模擬實(shí)現(xiàn)-創(chuàng)新互聯(lián)

一、vector 的使用

vector 是我們學(xué)習(xí)的第一個(gè)真正的 STL 容器，它接口的使用方式和 string 有一點(diǎn)點(diǎn)的不同，但大部分都是一樣的，所以這里我們就只演示其中一些接口的使用，大家如果有疑惑的地方直接在 cplusplus 是上面查看對(duì)應(yīng)的文檔即可。

成都創(chuàng)新互聯(lián)專(zhuān)業(yè)為企業(yè)提供巴馬網(wǎng)站建設(shè)、巴馬做網(wǎng)站、巴馬網(wǎng)站設(shè)計(jì)、巴馬網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、巴馬企業(yè)網(wǎng)站模板建站服務(wù)，10年巴馬做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。1、構(gòu)造函數(shù)

vector 提供了四種構(gòu)造方式 – 無(wú)參構(gòu)造、n 個(gè) val 構(gòu)造、迭代器區(qū)間構(gòu)造以及拷貝構(gòu)造：

其中構(gòu)造函數(shù)的最后一個(gè)參數(shù) alloc 是空間配置器，它和內(nèi)存池有關(guān)，作用是提高空間分配的效率；我們?nèi)粘Ｊ褂脮r(shí)不用管這個(gè)參數(shù)，使用它的缺省值即可，但是可能有極少數(shù)的人想要用自己實(shí)現(xiàn)的空間配置器來(lái)代替 STL 庫(kù)提供的，所以留出了這一個(gè)參數(shù)的位置。

需要注意的是，迭代器區(qū)間構(gòu)造是一個(gè)函數(shù)模板，即我們可以用其他類(lèi)來(lái)構(gòu)造 vector 對(duì)象：

同時(shí)，上面還有一個(gè)非常重要的細(xì)節(jié)：

在 n 個(gè) val 的構(gòu)造中，val 的缺省值是 T 的匿名對(duì)象，該對(duì)象使用 T 的默認(rèn)構(gòu)造來(lái)初始化，而不是以 0 作為缺省值，這是因?yàn)?T 不僅僅可能是內(nèi)置類(lèi)型，也可能是自定義類(lèi)型，比如 string、list、vector；

當(dāng) T 為自定義類(lèi)型時(shí)，0 就不一定能夠?qū)?val 進(jìn)行初始化，所以我們需要使用 T 的匿名對(duì)象來(lái)調(diào)用默認(rèn)構(gòu)造完成初始化工作；當(dāng) T 為內(nèi)置類(lèi)型時(shí)，我們?nèi)匀豢梢砸赃@種方式進(jìn)行初始化，因?yàn)?內(nèi)置類(lèi)型也具有構(gòu)造函數(shù)，你沒(méi)聽(tīng)錯(cuò)，內(nèi)置類(lèi)型也是有構(gòu)造函數(shù)的，大家可以理解為，為了解決上面這種情況，編譯器對(duì)內(nèi)置類(lèi)型進(jìn)行了特殊處理；

利用匿名對(duì)象調(diào)用默然構(gòu)造函數(shù)來(lái)作為缺省值的方法在下面 resize、insert 等接口中也有體現(xiàn)。

2、擴(kuò)容機(jī)制

vector 的擴(kuò)容機(jī)制和 string 的擴(kuò)容機(jī)制是一樣的，因?yàn)樗鼈兌际莿?dòng)態(tài)增長(zhǎng)的數(shù)組：VS 下大概是 1.5 被擴(kuò)容，Linux g++ 下是標(biāo)準(zhǔn)的二倍擴(kuò)容，測(cè)試用例如下：

void TestVectorExpand() {size_t sz;
	vectorv;
	sz = v.capacity();
	cout<< "making v grow:\n";
	for (int i = 0; i< 100; ++i) {v.push_back(i);
		if (sz != v.capacity()) {	sz = v.capacity();
			cout<< "capacity changed: "<< sz<< '\n';
		}
	}
}

3、三種遍歷方式

和 string 一樣，vector 也支持三種遍歷方式 – 下標(biāo)加[]遍歷、迭代器遍歷、范圍for遍歷：

需要注意的是，vector 和 string 之所以支持 下標(biāo) + [] 的方式遍歷，是因?yàn)樗鼈兊讓佣际菙?shù)組，而數(shù)組支持隨機(jī)訪(fǎng)問(wèn)，但是像我們后面要學(xué)習(xí)的 list set map 等容器，它們的底層不是數(shù)組，不支持隨機(jī)訪(fǎng)問(wèn)，就只能通過(guò)迭代器和范圍 for 的方式進(jìn)行遍歷了；不過(guò)，范圍 for 只是一個(gè)外殼，它在使用時(shí)也是被替換成迭代器，所以其實(shí)迭代器遍歷才是最通用的遍歷方式。

4、容量操作

vector 有如下容量相關(guān)的接口：

其中，最重要的兩個(gè)函數(shù)是 reserve 和 resize，reserve 只用于擴(kuò)容，它不改變 size 的大??；而 resize 是擴(kuò)容加初始化，既會(huì)改變 capacity，也會(huì)改變 size；

注意：reserve 和 resize，包括后面的 clear 函數(shù)都不會(huì)縮容，因?yàn)榭s容需要開(kāi)辟新空間、拷貝數(shù)據(jù)、釋放舊空間，而對(duì)于自定義類(lèi)型又有可能存在深拷貝問(wèn)題，時(shí)間開(kāi)銷(xiāo)極大；vector 中唯一可能縮容的函數(shù)就只有 shrink_to_fit，對(duì)于它來(lái)說(shuō)，如果 capacity 大于 size，它會(huì)進(jìn)行縮容，讓二者相等。

5、元素訪(fǎng)問(wèn)

vector 提供了如下接口來(lái)進(jìn)行元素訪(fǎng)問(wèn)：

其中，operator 和 at 都是返回 pos 下標(biāo)位置元素的引用，且它們內(nèi)部都會(huì)對(duì) pos 的合法性進(jìn)行檢查；不同的是，operator[] 中如果檢查到 pos 非法，那么它會(huì)直接終止程序，報(bào)斷言錯(cuò)誤，而 at 則是拋異常；

注：release 模式下檢查不出斷言錯(cuò)誤。

6、修改 – 迭代器失效

vector 提供了如下接口來(lái)進(jìn)行修改操作：

assign && push_back && pop_back

assign 函數(shù)用來(lái)替換 vector 對(duì)象中的數(shù)據(jù)，支持 n 個(gè) val 替換，以及迭代器區(qū)間替換，push_back 尾插、pop_back 尾插，這些接口的使用和 string 一模一樣，這里就不再過(guò)多闡釋?zhuān)?img src="/upload/otherpic40/4087d5744e19081e0bbf43a2d621bab5.jpg" alt="image-20221130195759960" />

insert && erase

和 string 不同，為了提高規(guī)范性，STL 中的容器都統(tǒng)一使用 iterator 作為 pos 的類(lèi)型，并且插入/刪除后會(huì)返回 pos：

所以，以后我們?nèi)绻谥虚g插入或刪除元素的話(huà)，必須配合算法庫(kù)里面的 find 函數(shù)來(lái)使用：

同時(shí)，在 VS 下，insert 和 erase 之后會(huì)導(dǎo)致 pos 迭代器失效，如果需要再次使用，需要更新 pos，如下：

不過(guò)，在 Linux 下不會(huì)出現(xiàn)這個(gè)問(wèn)題：

造成這個(gè)問(wèn)題的根本原因是 VS 使用的 PJ 版本對(duì) iterator 進(jìn)行了封裝，在每次 inset 和 erase 之后對(duì)迭代器進(jìn)行了特殊處理，而 g++ 使用的 SGI 版本中的 iterator 是原生指針，具體細(xì)節(jié)在后文 vector 的模擬實(shí)現(xiàn)中我們?cè)儆懻摚?/p>

但是為了代碼的可移植性，我們 統(tǒng)一認(rèn)為 insert 和 erase 之后迭代器會(huì)失效，所以，如果要再次使用迭代器，我們必須對(duì)其進(jìn)行更新；我們以移除 vector 中的所有偶數(shù)為例：

swap

和 vector 一樣，由于算法庫(kù) swap 函數(shù)存在深拷貝的問(wèn)題，vector 自己提供了一個(gè)不需要深拷貝的 swap 函數(shù)，用來(lái)交換兩個(gè) vector 對(duì)象：

同時(shí)，為了避免我們不使用成員函數(shù)的 swap，vector 還將算法庫(kù)中的 swap 進(jìn)行了重載，然后該重載函數(shù)的內(nèi)部又去調(diào)用成員函數(shù) swap：

---

二、vector 的模擬實(shí)現(xiàn) 1、淺析 vector 源碼

對(duì)于編程來(lái)說(shuō)，學(xué)習(xí)初期進(jìn)步最快的方式就是閱讀別人優(yōu)秀的代碼，理解其中的邏輯和細(xì)節(jié)后自己獨(dú)立的去實(shí)現(xiàn)幾次，學(xué)習(xí) STL 也是如此；我們可以適當(dāng)?shù)娜ラ喿x STL 的源碼，當(dāng)然我們并不是要逐行的進(jìn)行閱讀，因?yàn)檫@樣太耗費(fèi)時(shí)間，況且其中很多 C++ 的語(yǔ)法我們也還沒(méi)學(xué)。

當(dāng)前階段，我們閱讀 STL 源碼是為了學(xué)習(xí) STL 庫(kù)的核心框架，然后根據(jù)這個(gè)框架自己模擬實(shí)現(xiàn)一個(gè)簡(jiǎn)易的 vector (只實(shí)現(xiàn)核心接口)；閱讀源碼與模擬實(shí)現(xiàn)能夠讓我們更好的了解底層，對(duì) STL 做到 能用，并且 明理。

我們?cè)?【STL簡(jiǎn)介 – string 的使用及其模擬實(shí)現(xiàn)】 中對(duì) STL 做了一些基本的介紹，知道了 STL 由原始版本主要發(fā)展出了 PJ、RW 和 SGI 版本，其中，微軟的 VS 系列使用的就是 PJ 版，但是由于其命名風(fēng)格的原因，我們閱讀源碼時(shí)一般選擇 SGI 版，而且 Linux 下 gcc/g++ 也是使用的 SGI 版本，再加上侯捷老師有一本非常著名的書(shū) 《STL源碼剖析》也是使用的 SGI 版本，所以以后閱讀和模擬實(shí)現(xiàn) STL 時(shí)我都使用這個(gè)版本。

《STL源碼剖析》電子版和 《stl30》源碼我都放在下面了，需要的可以自?。?/p>

STL源碼剖析：https://www.aliyundrive.com/s/Nc4mpLC43kj
stl30：https://www.aliyundrive.com/s/pnwMuB9uwEN

vector 的部分源碼如下：

//vector.h
#ifndef __SGI_STL_VECTOR_H
#define __SGI_STL_VECTOR_H

#include 
#include 
#include#ifdef __STL_USE_NAMESPACES
using __STD::vector;

//stl_vector.h
templateclass vector {public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
    
   //成員函數(shù)
    
protected:
  typedef simple_allocdata_allocator;
  iterator start;
  iterator finish;
  iterator end_of_storage;
}

可以看到，vector.h 僅僅是將幾個(gè)頭文件包含在一起，vector 的主要實(shí)現(xiàn)都在 stl_vector.h 里面。

2、核心框架

我們可以根據(jù)上面的 vector 源碼來(lái)得出 vector 的核心框架：

namespace thj {templateclass vector {public:
        typedef T* iterator;
        typedef const T* const_iterator;

    public:
        //成員函數(shù)

    private:
        T* _start;
        T* _finish;
        T* _end_of_storage;
    };
}

可以看到，vector 的底層和 string 一樣，都是一個(gè)指針指向一塊動(dòng)態(tài)開(kāi)辟的數(shù)組，但是二者不同的是，string 是用 _size 和 _capacity 兩個(gè) size_t 的成員函數(shù)來(lái)維護(hù)這塊空間，而 vector 是用 _finish 和 _end_of_storage 兩個(gè)指針來(lái)維護(hù)這塊空間；雖然 vector 使用指針看起來(lái)難了一些，但本質(zhì)上其實(shí)是一樣的 – _size = _finish - _start, _capacity = _end_of_storage - _start;

3、構(gòu)造函數(shù)錯(cuò)誤調(diào)用問(wèn)題

在我們模擬實(shí)現(xiàn)了構(gòu)造函數(shù)中的迭代器區(qū)間構(gòu)造和 n 個(gè) val 構(gòu)造后，我們會(huì)發(fā)現(xiàn)一個(gè)奇怪的問(wèn)題，我們使用 n 個(gè) val 來(lái)構(gòu)造其他類(lèi)型的對(duì)象都沒(méi)問(wèn)題，唯獨(dú)構(gòu)造 int 類(lèi)型的對(duì)象時(shí)會(huì)編譯出錯(cuò)，如下：

//迭代器區(qū)間構(gòu)造
templatevector(InputIterator first, InputIterator last)
    :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {while (first != last)
        {push_back(*first);
            ++first;
        }
    }

//n個(gè)val構(gòu)造
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);
    }

這是由于編譯器在進(jìn)行模板實(shí)例化以及函數(shù)參數(shù)匹配時(shí)會(huì)調(diào)用最匹配的一個(gè)函數(shù)，當(dāng)我們將 T 實(shí)例化為 int 之后，由于兩個(gè)參數(shù)都是 int，所以對(duì)于迭代器構(gòu)造函數(shù)來(lái)說(shuō)，它會(huì)直接將 InputIterator 實(shí)例化為 int；

但對(duì)于 n 個(gè) val 的構(gòu)造來(lái)說(shuō)，它不僅需要將 T 實(shí)例化為 int，還需要將第一個(gè)參數(shù)隱式轉(zhuǎn)換為 size_t；所以編譯器默認(rèn)會(huì)調(diào)用迭代器構(gòu)造，同時(shí)由于迭代器構(gòu)造內(nèi)部會(huì)對(duì) first 進(jìn)行解引用，所以這里報(bào)錯(cuò) “非法的間接尋址”；

解決方法有很多種，比如將第一個(gè)參數(shù)強(qiáng)轉(zhuǎn)為 int，又或者是將 n 個(gè) val 構(gòu)造的第一個(gè)參數(shù)定義為 int，我們這里和 STL 源碼保持一致 – 提供第一個(gè)參數(shù)為 int 的 n 個(gè) val 構(gòu)造的重載函數(shù)：

//n個(gè)val構(gòu)造
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);
    }

//n個(gè)val構(gòu)造 -- 重載
vector(int 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);
    }

4、insert 和 erase 迭代器失效問(wèn)題

我們模擬實(shí)現(xiàn)的 insert 和 erase 函數(shù)如下：

//任意位置插入
iterator insert(iterator pos, const T& x)
{assert(pos >= _start);
    assert(pos<= _finish);

    //擴(kuò)容導(dǎo)致 pos 迭代器失效
    if (size() == capacity())
    {size_t oldPos = pos - _start;  //記錄pos，避免擴(kuò)容后pos變?yōu)橐爸羔?        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
        pos = _start + oldPos;  //擴(kuò)容之后更新pos
    }

    iterator end = _finish - 1;
    while (end >= pos)
    {*(end + 1) = *end;
        --end;
    }

    *pos = x;
    ++_finish;
    return pos;
}

//任意位置刪除 -- erase 之后也認(rèn)為 pos 迭代器失效
iterator erase(iterator pos)
{assert(pos >= _start);
    assert(pos< _finish);

    iterator begin = pos;
    while (begin< _finish - 1)
    {*begin = *(begin + 1);
        ++begin;
    }
    --_finish;
    return pos;
}

我們?cè)?vector 的使用中就提到 VS 下 insert 和 erase 后迭代器會(huì)失效，再次訪(fǎng)問(wèn)編譯器會(huì)直接報(bào)錯(cuò)，這是因?yàn)?PJ 版本下 iterator 不是原生指針，如下：

可以看到，VS 中的迭代器是一個(gè)類(lèi)，當(dāng)我們進(jìn)行 insert 或者 erase 操作之后，iterator 中的某個(gè)函數(shù)可能會(huì)將 pos 置為空或者其他操作，導(dǎo)致再次訪(fǎng)問(wèn) pos 報(bào)錯(cuò)，除非我們每次使用后都更新 pos：

而 Linux 下的 g++ 卻不會(huì)出現(xiàn)這樣的問(wèn)題，因?yàn)?g++ 使用的是 SGI 版本，該版本的源碼我們?cè)谏厦嬉惨呀?jīng)見(jiàn)過(guò)了，其迭代器是一個(gè)原生指針，同時(shí)它內(nèi)部 insert 和 erase 接口的實(shí)現(xiàn)也和我們模擬的類(lèi)似，可以看到，我們并沒(méi)有在函數(shù)內(nèi)部改變 pos (改變也沒(méi)用，因?yàn)檫@是形參)，所以 insert、erase 之后 pos 可以繼續(xù)使用；

但是這里也存在一個(gè)問(wèn)題，insert 和 erase 之后 pos 的意義變了 – 我們插入元素后 pos 不再指向原來(lái)的元素，而是指向我們新插入的元素；同樣，erase 之后 pos 也不再指向原來(lái)的元素，而是指向該元素的后一個(gè)元素；特別是當(dāng) erase 尾部的數(shù)據(jù)后，pos 就等于 _finish 了；

那么對(duì)于不了解底層的人就極易寫(xiě)出下面這樣的代碼 – 刪除 vector 中的所有偶數(shù)：

可以看到，第一個(gè)由于刪除元素后 pos 不再指向原位置，而是指向下一個(gè)位置，所以 erase 之后會(huì)導(dǎo)致一個(gè)元素被跳過(guò)，導(dǎo)致部分偶數(shù)沒(méi)有被刪除，但好在末尾是奇數(shù)，所以程序能夠正常運(yùn)行；

但是第二個(gè)就沒(méi)那么好運(yùn)了，由于最后一個(gè)元素是偶數(shù)，所以 erase 之后 pos 直接指向了 _finish 的下一個(gè)位置，循環(huán)終止條件失效，發(fā)生越界。

綜上，為了保證程序的跨平臺(tái)性，我們統(tǒng)一認(rèn)為 insert 和 erase 之后迭代器失效，必須更新后才能再次使用。

5、reserve 函數(shù)的淺拷貝問(wèn)題

除了上面這兩個(gè)問(wèn)題之外，我們的 vector 還存在一個(gè)問(wèn)題 – reserve 函數(shù) 深層次的淺拷貝問(wèn)題，模擬實(shí)現(xiàn)的 reserve 函數(shù)如下：

void reserve(size_t n)
{if (n >capacity())  //reserve 函數(shù)不縮容
    {T* tmp = new T[n];
        memcpy(tmp, _start, sizeof(T) * size());
        size_t oldSize = _finish - _start;  //記錄原來(lái)的size，避免擴(kuò)容不能確定_finish
        delete[] _start;

        _start = tmp;
        _finish = _start + oldSize;
        _end_of_storage = _start + n;
    }
}

很多同學(xué)看到這段代碼的時(shí)候可能會(huì)認(rèn)為它沒(méi)問(wèn)題，的確，對(duì)于內(nèi)置類(lèi)型來(lái)說(shuō)它確實(shí)是進(jìn)行了深拷貝，但是對(duì)于需要進(jìn)行深拷貝的自定義類(lèi)型來(lái)說(shuō)它就有問(wèn)題了，如下：

程序報(bào)錯(cuò)的原因如圖：當(dāng) v 中的元素達(dá)到4個(gè)再進(jìn)行插入時(shí)，push_back 內(nèi)部就會(huì)調(diào)用 reserve 函數(shù)進(jìn)行擴(kuò)容，而擴(kuò)容時(shí)我們雖然對(duì)存放 v1 v2 的空間進(jìn)行了深拷貝，但是空間里面的內(nèi)容我們是使用 memcpy 按字節(jié)拷貝過(guò)來(lái)的，這就導(dǎo)致原來(lái)的 v 里面的 string 元素和現(xiàn)在 v 里面的元素指向的是同一塊空間。

當(dāng)我們拷貝完畢之后使用 delete[] 釋放原空間，而 delete[] 釋放空間時(shí)對(duì)于自定義類(lèi)型會(huì)調(diào)用其析構(gòu)函數(shù)，而 v 內(nèi)部的 string 對(duì)象又會(huì)去調(diào)用自己的析構(gòu)函數(shù)，所以 delete[] 完畢后原來(lái)的 v 以及 v 中各個(gè)元素指向的空間都被釋放了，此時(shí)現(xiàn)在的 v 里面的每個(gè)元素全部指向已經(jīng)釋放的空間。

從第一張圖中我們也可以看到，最后一次 push_back 之后 v 里面的元素全部變紅了；最終，當(dāng)程序結(jié)束自動(dòng)調(diào)用析構(gòu)函數(shù)時(shí)，就會(huì)去析構(gòu)剛才已經(jīng)被釋放掉的 v 中的各個(gè) string 對(duì)象指向的空間，導(dǎo)致同一塊空間被析構(gòu)兩次，程序出錯(cuò)。

所以，在 reserve 內(nèi)部，我們不能使用 memcpy 直接按字節(jié)拷貝原空間中的各個(gè)元素，因?yàn)檫@些元素可能也指向一塊動(dòng)態(tài)開(kāi)辟的空間，而應(yīng)該調(diào)用每個(gè)元素的拷貝構(gòu)造進(jìn)行拷貝，如圖：

具體代碼實(shí)現(xiàn)如下：

//擴(kuò)容
void reserve(size_t n)
{if (n >capacity())  //reserve 函數(shù)不縮容
    {T* tmp = new T[n];
        //memcpy(tmp, _start, sizeof(T) * size());  //error

        //memcpy有自定義類(lèi)型的淺拷貝問(wèn)題，需要對(duì)每個(gè)元素使用拷貝構(gòu)造進(jìn)行深拷貝
        for (int i = 0; i< size(); i++)
            tmp[i] = _start[i];  //拷貝構(gòu)造

        size_t oldSize = _finish - _start;  //記錄原來(lái)的size，避免擴(kuò)容不能確定_finish
        delete[] _start;

        _start = tmp;
        _finish = _start + oldSize;
        _end_of_storage = _start + n;
    }

注意：有的同學(xué)看到這里使用的是賦值運(yùn)算符就認(rèn)為這里調(diào)用的賦值重載，其實(shí)不是的，因?yàn)檫@里完成的是初始化工作，編譯器會(huì)自動(dòng)轉(zhuǎn)換為調(diào)用拷貝構(gòu)造函數(shù)。

6、模擬 vector 整體代碼

在了解了 vector 的核心框架以及解決了上面這幾個(gè)疑難點(diǎn)之后，剩下的東西就變得很簡(jiǎn)單了，所以我這里直接給出結(jié)果，大家可以根據(jù)自己實(shí)現(xiàn)的對(duì)照一下，如有錯(cuò)誤，也歡迎大家指正：

//vector.h
#pragma once
#include#include 
#include#include 

namespace thj {//防止命名沖突
	templateclass vector {public:
		typedef T* iterator;
		typedef const T* const_iterator;

	public:
		//-------------------------------------constructor---------------------------------------//
		//無(wú)參構(gòu)造
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{}

		//迭代器區(qū)間構(gòu)造
		templatevector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	while (first != last)
			{		push_back(*first);
				++first;
			}
		}

		//n個(gè)val構(gòu)造
		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);
		}

		//n個(gè)val構(gòu)造 -- 重載
		vector(int 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);
		}

		//拷貝構(gòu)造 -- 寫(xiě)法1
		//vector(const vector& v)
		//{//	T* tmp = new T[v.capacity()];
		//	memcpy(tmp, v._start, sizeof(T) * v.capacity());
		//	_start = tmp;
		//	_finish = _start + v.size();
		//	_end_of_storage = _start + v.capacity();
		//}

		//拷貝構(gòu)造 -- 寫(xiě)法2
		//vector(const vector& v)
		//	: _start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//{//	reserve(v.capacity());
		//	for (size_t i = 0; i< v.size(); i++)
		//		push_back(v[i]);
		//}

		//拷貝構(gòu)造 -- 現(xiàn)代寫(xiě)法
		vector(const vector& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{	vectortmp(v.begin(), v.end());  //復(fù)用構(gòu)造函數(shù)和swap函數(shù)
			swap(tmp);
		}

		//析構(gòu)函數(shù)
		~vector() {	delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

		//賦值重載
		vector& operator=(vectorv)  //復(fù)用拷貝構(gòu)造，存在自我賦值的問(wèn)題，但不影響程序正確性
		{	swap(v);
			return *this;
		}

		//----------------------------------iterator---------------------------------------//
		iterator begin()
		{	return _start;
		}

		iterator end()
		{	return _finish;
		}

		const_iterator begin() const
		{	return _start;
		}

		const_iterator end() const
		{	return _finish;
		}

		//-------------------------------------capacity----------------------------------------//
		size_t size() const
		{	return _finish - _start;
		}

		size_t capacity() const
		{	return _end_of_storage - _start;
		}

		bool empty() const
		{	return _start == _finish;
		}

		//擴(kuò)容
		void reserve(size_t n)
		{	if (n >capacity())  //reserve 函數(shù)不縮容
			{		T* tmp = new T[n];
				//memcpy(tmp, _start, sizeof(T) * size());  //error

				//memcpy有自定義類(lèi)型的淺拷貝問(wèn)題，需要對(duì)每個(gè)元素使用拷貝構(gòu)造進(jìn)行深拷貝
				for (int i = 0; i< size(); i++)
					tmp[i] = _start[i];  //拷貝構(gòu)造

				size_t oldSize = _finish - _start;  //記錄原來(lái)的size，避免擴(kuò)容不能確定_finish
				delete[] _start;

				_start = tmp;
				_finish = _start + oldSize;
				_end_of_storage = _start + n;
			}
		}

		//擴(kuò)容并初始化
		void resize(size_t n, T x = T())
		{	if (n >capacity())  //resize 不縮容
			{		reserve(n);
			}
			if (n >size())
			{		while (_finish< _start + n)
				{*_finish = x;
					++_finish;
				}
			}
			if (n< size())
			{		_finish = _start + n;
			}
		}
        
		//----------------------------------------element access---------------------------------//
		T& operator[](size_t pos)
		{	assert(pos< size());  //檢查越界
			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{	assert(pos< size());
			return _start[pos];
		}

		//----------------------------------------modifys-----------------------------------------//
		//尾插
		void push_back(const T& n)
		{	if (size() == capacity())
			{		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}
			*_finish = n;
			++_finish;
		}

		//尾刪
		void pop_back()
		{	assert(!empty());
			--_finish;
		}

		//任意位置插入 -- 插入后認(rèn)為迭代器失效
		iterator insert(iterator pos, const T& x)
		{	assert(pos >= _start);
			assert(pos<= _finish);

            //擴(kuò)容會(huì)導(dǎo)致迭代器失效
			if (size() == capacity())
			{		size_t oldPos = pos - _start;  //記錄pos，避免擴(kuò)容后pos變?yōu)橐爸羔?				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + oldPos;  //擴(kuò)容之后更新pos
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{		*(end + 1) = *end;
				--end;
			}

			*pos = x;
			++_finish;
			return pos;
		}

		//任意位置刪除 -- erase 之后也認(rèn)為 pos 迭代器失效
		iterator erase(iterator pos)
		{	assert(pos >= _start);
			assert(pos< _finish);

			iterator begin = pos;
			while (begin< _finish - 1)
			{		*begin = *(begin + 1);
				++begin;
			}
			--_finish;
			return pos;
		}

		//交換兩個(gè)對(duì)象
		void swap(vector& v)
		{	std::swap(_start, v._start);  //復(fù)用算法庫(kù)的swap函數(shù)
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

		void clear()
		{	_finish = _start;
		}

	private:
		T* _start;
		T* _finish;
		T* _end_of_storage;
	};
}

---

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：【C++】vector的使用及其模擬實(shí)現(xiàn)-創(chuàng)新互聯(lián)
URL地址：http://muchs.cn/article6/dshiog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機(jī)、網(wǎng)站排名、靜態(tài)網(wǎng)站、品牌網(wǎng)站制作、自適應(yīng)網(wǎng)站、網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)