C++ vector的底層實現分析

這篇文章主要介紹“C++ vector的底層實現分析”，在日常操作中，相信很多人在C++ vector的底層實現分析問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++ vector的底層實現分析”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

定義初始結構

在標準C++中,vector同樣是一個模板,并且其底層實現用的是三個指針,然后利用這三個指針相互加減,達到存儲效果.

而vector和string類似,本質是都是一個順序表.

template <class T>
class vector
{
public:
    ~vector()
    {
        delete _start;
        _start = _finish = _end_of_storage = nullptr;
    }
private:
    T* _start;         //順序表的頭
    T* _finish;        //順序表有效長度位置
    T* _end_of_storage; //順序表末尾
};

聲明構造函數

上一章節已經講解,構造函數比較多,這里只是為了簡單實現,所以博主就實現一個最簡單的構造函數,即無參構造.

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr) {}

容量有關操作

獲取有效數據大小size()

想要獲取size,該怎么實現呢?我們在定義初始結構的時候,已經知道其底層是利用的三個指針,所以size等于_finish - _start.

size_t size() const    //加const是保證const對象也可以用
{
    return _finish - _start;
}

獲取數據容量capacity()

同樣的道理,capacity就應是_end_of_storage - _start;

size_t capacity() //加const是保證const對象也可以用
{
    return _end_of_storage - _start;
}

增加容量reserve()

我們在后面會實現一個接口,叫做push_back(),它的作用是把數據放進vector,但如果空間不足了呢?這就需要我們的增容函數reserve了.

其參數是無符號整型n,代表要開n個空間

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];               //先開辟一塊空間
        size_t sz = size();              //保留原來的有效數據大小,且一定要先保存
        if (_start)        //一定要判斷這個,因為最開始_start為空,那么就只需要開空間
        {
            memcpy(tmp, _start, sizeof(T) * n);  //把原來的數據拷貝進新空間
            delete _start;  //釋放原來的空間
        }
        _start = tmp;                    //移交空間
        _finish = _start + sz;           //更新_finish
        _end_of_storage = _start + n;    //更新_end_of_storage
    }
}

重置大小resize()

這個想必大家現在已經比較習慣了吧?他有兩個參數,會分情況討論是否大于size()而進行參數賦值.

void resize(size_t n,const T& val = T())
{
    if(n>capacity()) reserve(n);
    for(size_t i = size();i<n;i++)
    {
        _start[i] = val;
    }
    _finish = _start + n;    
}

迭代器

前面講解string的時候說過,現階段我們就把迭代器當做一個指針,**雖然指針一定是迭代器,但是迭代器不一定是指針.**但是目前階段我們用到的迭代器就是一個指針,因此這里便直接定義迭代器了

typedef T* iterator;              //普通迭代器
typedef const T* const_iterator;  //const迭代器
//因此返回首尾迭代器的接口,博主便一并寫下來
iterator begin() {return _start;}
iterator end() {return _finish;}        //普通接口
const_iterator begin() const {return _start;}
const_iterator end() const {return _finish;}  //const接口

數據操作

尾插push_back()

該接口的實現操作一般是先檢查容量是否充足,然后把數據放進去,最后size大小加一.

void push_back(const T& val)
{
    if(size() == capacity())
    {
        size_t newcapacity = size()==0?4:capacity()*2;  //需要考慮到size是否有可能為0的情況
        reserve(newcapacity);
    }
    *_finish = val;
    _finish++;
}

尾刪pop_back()

實現該接口的操作一般是先檢查是否還存在數據,然后size大小減一

void pop_back()
{
    assert(size()>0);
    _finish--;
}

某一位置插入 insert()

同樣的道理,一般先檢查容量是否充足,如果不夠,需要警惕迭代器失效問題,然后移動該位置及以后的所有數據,最后插入數據.

官方文檔定義其返回值為新插入數據的位置

iterator insert(iterator pos,const T& val)
{
    assert(pos>=_start && pos <= _finish);
    if(_finish == _end_of_storage)
    {
        int n = pos - _start;
        size_t newcapacity = 0 ? 4 :capacity()*2;
        pos = _start + n;      //防止pos迭代器失效
    }
    iterator cur = end();
    while(cur > pos)
    {
        *cur = *(cur-1);
        cur--;
    }
    *pos = val;
    _finish++;
    return pos;
}

某一位置刪除 erase()

該接口的操作一般是從pos后位置開始,所有數據前挪一單位.但是在挪之前,需要檢查是否還存在數據

官方文檔定義其返回值為刪除數據的下一位置

iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    iterator it = pos + 1;
    while (it != _finish)
    {
        *(it-1) = *it;
        ++it;
    }
    --_finish;
    return pos;
}

拷貝構造

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
    reserve(v.capacity());
    for (const auto& e : v)
    {
        push_back(e);
    }
}

[]訪問操作

上面我們實現了迭代器,但是vector還支持[]索引取值,博主這里便實現兩個[]重載吧

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

=賦值操作

vector<T>& operator=(vector<T> v)    //注意哦~,我這里故意寫的傳值參數,而不是引用,是為了下面進行交換
{
    swap(*this,v);
    return *this;
}

特別注意!!!

在實現了上面的一系列操作以后,有沒有覺得我們已經大功告成了?其實這里還隱藏著一個小小bug!.為什么呢?看下面'

int main()
{
    //我們假設最開始創建的vector的容量是4
	vector<string> vc;
	vc.push_back("123");    //創建vc,并給其賦值
    vc.push_back("234");
    vc.push_back("345");
    vc.push_back("456");
    vc.push_back("567");
    return 0;
}

初一看,好像并沒有什么錯誤哎?但是一運行就會發現,當插入第5個元素的時候,就報錯了.這是什么原因呢?

調試發現,問題出在了reserve上面,因為push_back之前,會檢查容量,那么我們現在重新瞅瞅 reserve存在什么問題呢?

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];               //先開辟一塊空間
        size_t sz = size();              //保留原來的有效數據大小,且一定要先保存
        if (_start)        //一定要判斷這個,因為最開始_start為空,那么就只需要開空間
        {
            memcpy(tmp, _start, sizeof(T) * n);  //把原來的數據拷貝進新空間
            delete _start; //釋放原來的空間
        }
        _start = tmp;                    //移交空間
        _finish = _start + sz;           //更新_finish
        _end_of_storage = _start + n;    //更新_end_of_storage
    }
}

大家有發現什么問題了嗎?

沒錯,問題出現在memcpy上面,當容量不足,reserve就會增加容量,然后把原來空間的內容值拷貝到新空間.

但是原來空間的內容也就只有三個指針呀,拷貝過去后,新空間和源空間都指向了同一塊空間,而我們又會釋放原空間.

所以,當繼續尾插第5個元素時候,就報錯了,因為空間已經不存在了!!!,被釋放了.

那怎么解決呢?這里便只能用循環,把string值賦給新空間了.

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t sz = size();
        T* tmp = new T[n];
        if (_start)
        {
            for (size_t i = 0; i < sz; ++i)
            {	
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _endofstorage = _start + n;
    }

到此，關于“C++ vector的底層實現分析”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！