vector 一、前言

《STL源碼剖析》學(xué)習(xí)到了容器，實(shí)現(xiàn)的成員函數(shù)頓時多了起來，生硬的列出來不太適合把握細(xì)節(jié)，也不方便自己以后復(fù)習(xí)，于是決定從測試代碼出發(fā)，自頂向下，從元素的操作一路下探到內(nèi)存分配。

創(chuàng)新互聯(lián)建站一直秉承“誠信做人，踏實(shí)做事”的原則，不欺瞞客戶，是我們最起碼的底線！ 以服務(wù)為基礎(chǔ)，以質(zhì)量求生存，以技術(shù)求發(fā)展，成交一個客戶多一個朋友！為您提供成都網(wǎng)站制作、成都做網(wǎng)站、成都網(wǎng)頁設(shè)計、小程序開發(fā)、成都網(wǎng)站開發(fā)、成都網(wǎng)站制作、成都軟件開發(fā)、APP應(yīng)用開發(fā)是成都本地專業(yè)的網(wǎng)站建設(shè)和網(wǎng)站設(shè)計公司，等你一起來見證！二、測試代碼縱覽 2.1 自定義數(shù)據(jù)結(jié)構(gòu)

using std::string;
using std::cout;
using std::endl;
using tinystl::vector;

class Person{public:
    Person() = default;
    Person(string& name, int age):m_Age(age), m_Name(name) {}
    Person(const char* name, int age):m_Age(age), m_Name(name) {}
    ~Person()= default;
    friend std::ostream& operator<<(std::ostream& os, const Person& p);
    string m_Name;
    int m_Age{};
};

std::ostream& operator<<(std::ostream& os, const Person& p) {os<< p.m_Name<< ' '<< p.m_Age;
    return os;
}

這部分沒什么特別的，只是想確認(rèn)咱這個粗制濫造的vector不只能存內(nèi)置類型的數(shù)據(jù)，整了個Person類，只有m_Name和m_Age兩個成員變量，然后全局重載了流運(yùn)算符方便打印。

2.2 測試內(nèi)容

1、構(gòu)造：constructor

2、插入：push_back、insert

3、讀?。簅perator[]、front、back

4、刪除：erase、clear

5、改變大?。簉esize

下面進(jìn)入正題?。?！

三、故事從5個Person對象開始 3.1 構(gòu)造、內(nèi)存分配

vectorpv(5, Person("yzh", 22));
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;

這段代碼首先創(chuàng)建了一個匿名Person對象，傳入vector的構(gòu)造函數(shù)中，要求它新建一個容器，并且存五個叫yzh的22歲哥們，接下來看構(gòu)造函數(shù)干了啥。

vector(size_type n, const T &value) {fill_initialize(n, value); }

這里的size_type只是一個typedef，實(shí)際上是size_t，后者又是個typedef，不過這就不重要了，總之一般就是個unsigned long類型。在vector中聲明了數(shù)個typedef，后面還能遇到的。

可以看到由于vector有好幾個構(gòu)造函數(shù)，構(gòu)造的方法大差不差，所以給封裝進(jìn)了一個fill_initialize函數(shù)。

//用于構(gòu)造函數(shù)，初始化元素頭尾和空間尾指針
void fill_initialize(size_type n, const T& value) {_start = allocate_and_fill(n, value);
    _finish = _start + n;
    _end_of_storage = _finish;
}

初始化的這三個東西是什么？往前面翻翻，哦原來是唯三的保護(hù)成員變量，類型是iterator迭代器，再往前找，iterator原來就是T*也就是原生指針類型。對于vector來說很合理，因?yàn)樗沁B續(xù)的、可以隨機(jī)訪問的空間，和指針沒有任何區(qū)別，當(dāng)然也支持指針?biāo)鶕碛械乃胁僮鳌?/p>

using iterator = T *;

iterator _start;
iterator _finish;
iterator _end_of_storage;

此時就搞清楚這個fill_initialize在干什么了，通過allocate_and_fill分配5個Person對象的空間并且填入元素，這個函數(shù)指定是返回了分配空間的首地址，正好接過來初始化首指針。尾指針finish不難理解，關(guān)鍵是這個end_of_storage是干啥的？現(xiàn)在我只能根據(jù)變量名猜測它指示了分配的空間的最后位置，具體為什么是這樣還得繼續(xù)往后執(zhí)行看。

知道了vector是如何初始化的，我希望繼續(xù)深入認(rèn)識到底容器中的內(nèi)存分配和對象的構(gòu)造是怎么設(shè)計的，于是興趣轉(zhuǎn)向這個allocate_and_fill函數(shù)。

iterator allocate_and_fill(size_type n, const T& val) {//申請一片內(nèi)存空間，并返回起始地址
    iterator start = data_allocator::allocate(n);
    tinystl::uninitialized_fill_n(start, n, val);
    return start;
}

這里的data_allocator::allocate(n)忠實(shí)的執(zhí)行了一件事：分配內(nèi)存。具體實(shí)現(xiàn)并不復(fù)雜，只是調(diào)用了全局的operator new申請了一片空間并返回首地址。uninitialized_fill_n(start, n, val)則將對象構(gòu)造與內(nèi)存分配區(qū)分開來，在已分配的空間上構(gòu)造了n個元素，具體實(shí)現(xiàn)按下不表，如果有時間的話可以單獨(dú)做一下筆記。

總而言之，經(jīng)過這么一番折騰，一個vector容器終于構(gòu)造完成，三個指針也指向了第一個元素、最后一個元素的后一個（前閉后開）、分配內(nèi)存最后一個位置的后一個（目前和元素末尾指針指向一樣）。下面回到最開始的測試代碼。

vectorpv(5, Person("yzh", 22));
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;

初始化完成，讓我們看看現(xiàn)在容器的大小吧。

pv.size()返回的是已經(jīng)填入元素的個數(shù)，pv.capacity()返回的是總的分配空間的大小，也就是容器的“容量”。不難想象實(shí)現(xiàn)其實(shí)就是首尾指針相減，只是一個是用finish減start，一個是用end_of_storage。

非常好，和預(yù)想的一樣，可以進(jìn)入下一步了，也是重頭戲，揭開了vector動態(tài)增長的奧秘。

3.2 插入、空間再分配

本節(jié)的主角是這樣一行代碼：

pv.push_back(Person("wqy", 100));

我想要將一個百歲老頭的信息插入到元素的最后一個位置。之前說過end_of_storage指示已分配空間的最后一個位置，那如果還有多余的空位那就好辦了，直接在上面構(gòu)造出來這個新來的哥們就行了。

templatevoid vector::push_back(const T &val) {if (_finish != _end_of_storage) {tinystl::construct(_finish, val);
        ++_finish;
    } else {//如果當(dāng)前已經(jīng)申請到的空間不足以放下新的元素了，執(zhí)行這個函數(shù)
        insert_aux(end(), val);
    }
}

空間不夠了怎么辦？不急，執(zhí)行一個輔助函數(shù)實(shí)現(xiàn)傳說中的搬家。

templatevoid vector::insert_aux(vector::iterator position, const T &x) {if(_finish != _end_of_storage) {//這函數(shù)不只給push_back用，這里還得判斷
        //在最后一個元素的后一個位置構(gòu)造一個最后元素
        tinystl::construct(_finish, *(_finish - 1));
        ++_finish;
        //細(xì)節(jié)，必須要確保存儲下來的是元素的一個副本,不然以后修改容器里面的值影響容器外面豈不是亂套
        T x_copy = x;
        //position后面整體右移
        std::copy_backward(position, _finish - 2, _finish - 1);
        *position = x_copy;
    }
    else {const size_type old_size = size();
        //如果原空間為0，新空間為1，否則為兩倍的原空間
        //注意這里的新空間指的是分配的內(nèi)存，跟size()沒關(guān)系
        const size_type len = old_size != 0 ? 2 * old_size : 1;
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {//別忘了uninitialized系列主打的是構(gòu)造與內(nèi)存分配的分離～
            //首先把插入位置之前的對象拷貝到新位置去
            new_finish = tinystl::uninitialized_copy(_start, position, new_start);
            //構(gòu)造插入對象
            tinystl::construct(new_finish, x);
            ++new_finish;
            //繼續(xù)把插入位置后面的拷貝到新位置去，接在插入對象后面
            new_finish = tinystl::uninitialized_copy(position, _finish, new_finish);
        }
        catch (...) {//要么做完，要么一個別做！
            tinystl::destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        //至此，新空間準(zhǔn)備好了，老空間徹底失去了價值
        destroy(begin(), end());
        deallocate();
        //新的頭尾指針干過去
        _start = new_start;
        _finish = new_finish;
        _end_of_storage = new_start + len;
    }
}
}

關(guān)鍵點(diǎn)都寫在了注釋中，總而言之思路就是之前分配的空間用完了，那么我只能去別處在申請一片更大的空間（原來的地方肯定不能直接在屁股后面申請了，誰都沒法保證后面還有沒有空間）。那么申請多少？現(xiàn)在用了多少，以后很有可能也會用多少，所以整個兩倍大的空間（個人理解）。最后舉家搬遷，完成這次增長。不難看出這個操作一套下來需要消耗大量的資源和時間，如果頻繁搬家會導(dǎo)致效率極低。

有三個細(xì)節(jié)我容易忽視：

1、x_copy：容器存的是副本，可別把傳入的引用存進(jìn)去了

2、commit-rollback語義：如果發(fā)生異常，不能直接終止吧，很多時候罪不至死；更不能卡一半直接返回吧，用戶直接摸不清頭腦你到底走到哪一步，所以要么做完，要么回退到執(zhí)行前的狀態(tài)，你好我好大家好～

3、copy_backward：往后拷貝的時候，可能會因?yàn)閺?fù)制位置的起始點(diǎn)處于原來的區(qū)間內(nèi)而導(dǎo)致出現(xiàn)覆蓋的問題導(dǎo)致實(shí)際效果和期待的不一樣，還是看看cppreference的官方解釋吧：

Copies all elements in the range[first, last)starting from first and proceeding to last - 1. The behavior is undefined ifd_firstis within the range[first, last). In this case, std::copy_backward may be used instead.

最后看看size和capacity的變化（上面的是之前的，下面的是這插入結(jié)束后的），和預(yù)想一樣，容量翻倍，size加一。下一位！

3.3 元素訪問

中場休息放松一下。

pv[0].m_Name = "ywt";
cout<< "front = "<< pv.front()<< ' '<< "back = "<< pv.back()<< endl;

元素的訪問可以說毫無技術(shù)含量。尤其是對于隨機(jī)訪問迭代器來說，有了首尾指針和偏移量可以輕松返回我想要的任意位置的元素，不多說直接上代碼吧。

//提取特定位置的元素
reference front() {return *_start; }
reference back() {return *(_finish - 1); }
reference operator[](size_type n) {return *(begin() + n); }

其中需要注意的大概只有前閉后開的問題了，finish那個位置是一片“虛空”，真正的最后一個元素在前一位，別越界哦?。o論是程序或生活中）

3.4 如果我想任意插入呢？

push_back實(shí)現(xiàn)了在末尾插入一個元素，確實(shí)已經(jīng)可以覆蓋實(shí)際使用中大部分插入場景了，但在中間插入任意個元素的操作還是難以避免的，怎么實(shí)現(xiàn)呢？老規(guī)矩先上測試代碼。

auto itr = pv.begin() + 2;
auto itr2 = pv.insert(itr, 1, Person("nxl", 3));
cout<< *itr2<< endl;

首先很重要的一點(diǎn)，STL規(guī)定插入的元素必須插在指定位置的前一個，咱們模仿也得講規(guī)矩是吧～

看傳參，一個迭代器，一個數(shù)，一個臨時對象。得，猜也猜得到是在迭代器指定的位置插入n個對象唄，讓我們來看具體實(shí)現(xiàn)吧。

templatetypename vector::iterator vector::insert(vector::iterator pos, vector::size_type n, const T &val) {if(n == 0) return pos;
    //用來定位插入元素的第一位
    const difference_type offset = pos - begin();
    if(static_cast(_end_of_storage - _finish) >= n) {//情況1：備用的空間大于待插入元素個數(shù)
        T val_copy = val;
        //插入位置后面有多少元素
        const size_type elems_after = _finish - pos;
        iterator old_finish = _finish;
        //如果后面的元素比要插入的多，意味著需要構(gòu)造的只有原來的元素
        if(elems_after >n) {//空出n個位置，那么后n個需要構(gòu)造
            tinystl::uninitialized_copy(_finish - n, _finish, _finish);
            _finish += n;
            //把剩下的后移n位，注意第三個參數(shù)的含義??！
            //first, last  -  the range of the elements to copy from
            //d_last   -  the end of the destination range
            std::copy_backward(pos, old_finish - n, old_finish);
            //空出來的填元素就可以了
            std::fill(pos, pos + n, val_copy);
        }
        //如果插入位置后面的元素比插入的少，意味著后面的元素要全部前往未構(gòu)造區(qū)域，同時會有插入元素需要構(gòu)造
        else {//想象一下后面元素搬遷后的場景，中間會有一些沒構(gòu)造的區(qū)域，先給他干上去一部分插入元素
            tinystl::uninitialized_fill_n(_finish, n - elems_after, val_copy);
            _finish += n - elems_after;
            //隨后開始大遷徙
            tinystl::uninitialized_copy(pos, old_finish, _finish);
            _finish += elems_after;
            //最后鳩占鵲巢
            std::fill(pos, old_finish, val_copy);
        }
    }
    else {//情況2：備用的空間不夠插了
        const size_type old_size = size();
        //如果需要的新空間比老空間還多，那就需要更大的空間正好裝下，否則還是兩倍的原空間
        //注意這里的新空間指的是分配的內(nèi)存，跟size()沒關(guān)系
        const size_type len = old_size + std::max(old_size, n);
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {//別忘了uninitialized系列主打的是構(gòu)造與內(nèi)存分配的分離～
            //首先把插入位置之前的對象拷貝到新位置去
            new_finish = tinystl::uninitialized_copy(_start, pos, new_start);
            //構(gòu)造插入對象
            new_finish = uninitialized_fill_n(new_finish, n, val);
            //繼續(xù)把插入位置后面的拷貝到新位置去，接在插入對象后面
            new_finish = tinystl::uninitialized_copy(pos, _finish, new_finish);
        }
        catch (...) {//要么做完，要么一個別做！
            tinystl::destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        //至此，新空間準(zhǔn)備好了，老空間徹底失去了價值
        destroy(begin(), end());
        deallocate();
        //新的頭尾指針干過去
        _start = new_start;
        _finish = new_finish;
        _end_of_storage = new_start + len;
    }
    return begin() + offset;
}

注：其中，全局函數(shù)destroy實(shí)現(xiàn)了對象的析構(gòu)，deallocate調(diào)用allocator::deallocate()實(shí)現(xiàn)了內(nèi)存空間的回收，繼續(xù)堅持分離構(gòu)造與空間分配，把操作的粒度細(xì)化以滿足各種各樣的需求。

代碼很長，但是空間不足的部分和之前的insert_aux是幾乎重復(fù)的，無非是從插入一個變成插入許多，所以其實(shí)應(yīng)該包裝起來的，偷懶了。

空間足夠的時候需要充分發(fā)揮一波空間想象力（或者直接畫畫圖），到底備用空間和插入元素個數(shù)的大小比較會帶來什么樣的影響，換句話說，什么情況下在插入時待插入的元素有一部分會踏入“虛空（備用的未構(gòu)造空間）”？想通了代碼就很好理解了。

最后打印一下返回的迭代器指向哪，驗(yàn)證一下返回的確實(shí)是插入元素的第一個位置。這又牽扯到一個迭代器失效的問題了，也就是當(dāng)insert發(fā)生后，插入位置后面的所有早先定義的迭代器都不能再用了，強(qiáng)行使用很有可能不是我想要的效果，好在有了這個確定無疑的返回值，又可以愉快的玩耍了哈哈。（后面erase也有同樣的問題，不再贅述）

3.5 刪除

快結(jié)束嘍！有插入就有刪除，上代碼！

pv.pop_back();
cout<< "after pop: back = "<< *(pv.end() - 1)<< endl;

首先是pop_back()彈出末尾元素。其實(shí)就是刪掉最后一個嘛，簡單，尾指針向前一位，析構(gòu)掉這個位置的對象，完事！實(shí)現(xiàn)如下：

void pop_back() {--_finish;
    tinystl::destroy(_finish);
}

erase則略微復(fù)雜一點(diǎn)點(diǎn)，有兩個重載，一個刪除指定位置的一個元素，一個刪除指定區(qū)間內(nèi)的所有元素

pv.erase(pv.end() - 2, pv.end() - 1);
pv.erase(pv.end() - 3);

在刪除前讓我們再見一見所有的元素們，馬上就要分別之時了，別忘了wqy已經(jīng)被彈出去了。

templatetypename vector::iterator vector::erase(vector::iterator first, vector::iterator last) {//把刪除元素區(qū)間后面的所有元素前移一位，覆蓋掉刪除元素（至少覆蓋一部分）
    // 返回復(fù)制元素末尾的后一個位置
    iterator it = std::copy(last, _finish, first);
    //細(xì)節(jié)，雖然不知道it在前還是last在前，但我能確定的是從it開始到finish的一定都不要
    tinystl::destroy(it, _finish);
    //刪掉多少finish前移多少
    _finish = _finish - (last - first);
    //返回刪掉元素的后一個位置
    return first;
}

templatetypename vector::iterator vector::erase(vector::iterator pos) {if (pos + 1 != end()) {//把pos后面的都復(fù)制到pos的位置來
        std::copy(pos + 1, _finish, pos);
    }
    --_finish;
    data_allocator::destroy(_finish);
    //原來的迭代器會失效，不要erase(iter++)，大概率不是咱想要的效果
    return pos;
}

經(jīng)歷了insert的洗禮，理解erase的實(shí)現(xiàn)過程基本不成問題了，還就是那個移動元素+析構(gòu)，似乎沒有特別的坑，注釋應(yīng)該足夠詳細(xì)了，過！

3.6 修改元素個數(shù)

最后一站，學(xué)習(xí)resize()，上代碼

cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;
if(!pv.empty()) cout<< "not empty"<< endl;
else cout<< "empty"<< endl;

經(jīng)過前面一頓折騰，掐指一算容器里面還剩4個元素。

empty函數(shù)不多說，檢查一下首尾指針是否相等即可。

bool empty() {return begin() == end(); }

接下來開始resize，并打印一下信息

pv.resize(20, Person("null", 1000));
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;
for(const auto& n : pv) {cout<< n.m_Name<< ' ';
}
cout<< endl;

resize也有兩個重載，主要應(yīng)對擴(kuò)大的時候我還想給變大的空間初始化的場景，代碼如下：

void resize(size_type new_size, const T& val) {if(new_size< size())
        erase(begin() + new_size, end());
    else
        insert(end(), new_size - size(), val);
}
void resize(size_type new_size){resize(new_size, T());
}

如果新大小更大的話，應(yīng)該發(fā)生的是插入操作，否則是刪除操作。插入的情況下，插入的元素如果沒有指定的話就直接默認(rèn)構(gòu)造。全都是封裝好的函數(shù)了，寫的人舒服看的人也舒服～打印一下信息，再試試縮小

pv.resize(3);
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;

最后試試清空，有了區(qū)間erase，還怕不會清空？

pv.clear();
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;
if(!pv.empty()) cout<< "not empty"<< endl;
else cout<< "empty"<< endl;

void clear() {erase(begin(), end());}//清空容器

上效果！！

四、后記

蕪湖，vector的學(xué)習(xí)筆記終于結(jié)束啦，現(xiàn)如今C++慢慢發(fā)育起來STL也是日新月異了，這個基于GNU2.9的tinystl實(shí)現(xiàn)肯定是顯得久遠(yuǎn)了。不過沒關(guān)系，以后有機(jī)會再拜讀新的源碼，尤其是C++11、17帶來的那些新東西，很多都還用不明白，離吃透還早呢。。。不管怎么說，我已經(jīng)徹底愛上這個語言了，list再見?。?/p>

哦對了，如果小弟有幸能被大佬看到這篇筆記，希望可以指點(diǎn)出我的錯誤，畢竟自學(xué)，有時候感覺挺怕走了彎路還不自知的，，太感謝了??！

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

網(wǎng)頁題目：STL源碼剖析學(xué)習(xí)筆記——vector-創(chuàng)新互聯(lián)
URL地址：http://weahome.cn/article/iceod.html