Vector底層實作

vector的三個私有成員

:_start   記錄初始位置
, _finish 記錄有效字符
, _endofstoage  記錄容量大小

vector會存盤的型別不同，所以要用模版來定型別 

typedef T* iterator;

iterator _start;
iterator _finish;
iterator _endofstoage;

也就是T*

建構式的方法很多 可以用迭代器的范圍來構造

//用迭代器構造的建構式

傳過來的是它的迭代器的型別 我們也用它的型別來接收 不比加* &

 三個屬性先初始化

只要根據傳過來的范圍來push_back（）即可

push_back函式后面會實作

        //用迭代器構造的建構式
        template <class InputIterator>
        vector(InputIterator first, InputIterator last)
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

構造是 也可以根據n分val來構造 所以這個功能也需要提供

傳過來的是n個 用size_t接收 因為n必須是>=0的  而val是根據型別 所以用模版型別接受  

有些情況下 val會不傳參  那么我們就會提供他的默認構造  （注意 在C++中，內置型別也是有默認構造的）

三個屬性初始話

先用reserve函式創建n個空間

在分別push_back（）添加val

        //構造n個val的建構式
        vector(size_t n, const T& val = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

因為某些情況 第一個引數是int  第二個引數也是int 會呼叫到迭代器的函式 因為這兩個型別更加適配，所以會出問題，所以需要再提供一個第一個引數為int的相同函式，來避免這種情況

    //構造n個val的建構式
        //因為用int會呼叫到其他函式 所以為了區分 單獨寫出一個第一個為int
        vector(int n, const T& val = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

swap函式

這個函式是用來給拷貝構造使用

交換類的三個屬性成員

        //交換
        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endofstoage, v._endofstoage);
        }

拷貝構造

拷貝的本質是把一個有資料的拷貝給一個無資料的，只需要用這個無資料的迭代器去呼叫迭代器構造，給一個臨時tmp，最后再用這個無資料的與臨時tmp交換  即可

因為傳過來的是另一個vector 所以必須用vector<T> 接收  C++傳參是特別需要注意的，真的很容易亂

        //拷貝構造
        vector(const vector<T>& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            vector<T> tmp(v.begin(), v.end());//復用用迭代器構造的建構式
            swap(tmp);
        }

賦值多載

v1=v2  是兩個vector的資料賦值 所以它的回傳值必須是vector<t>  而傳引數時 也必須是vector<t> 

函式本質也是交換，所以直接呼叫swap  這里之所以能直接呼叫 而不影響到v2 是因為函式是用傳值傳參，它是不會影響到v2本體的，（現代寫法）

回傳時是回傳本體 （*this）

    vector<T>& operator=(vector<T> v)//賦值多載   不用參考  現代寫法
        {
            swap(v);//現代寫法 
            return *this;
        }

解構式

判斷是否為空 當不為空時才需要析構  如果為空 去析構 會崩潰

把資料釋放，并且它三個屬性置空

    // 資源管理
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _endofstoage = nullptr;
            }
        }

迭代器部分

vector的迭代器本質就是指標  根據傳進來的型別  iterator就是這個型別的指標

并且迭代器分為const版本和非const版本 

所以需要提供兩個版本

        //迭代器
        typedef T* iterator;
        typedef const T* const_iterator;

注意 end回傳的是你的實際有效字符 而不是你的的空間多大

        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

size 

你的有效字符 _finish  而_finish實際上是有效字符的下一個位置

所以需要減去初始的位置 得到它真正的有效字符

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

capacity

計算的是vector的空間大小 也就是你的記錄空間大小減去初始位置

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

【】多載

vector是支持隨意訪問的，所以【】的多載必不可少

回傳的是vector里存盤的型別  實際上就是模版型別  因為傳出去也代表它需要改變 所以需要傳參考

        T& operator[](size_t n)
        {
            assert(n < size());
            //return *(_start + n);
            return _start[n]; //這個也可以
        }

【】多載 有些地方是需要提供const版本 不允許更改的版本

        const T& operator[](size_t n) const
        {
            assert(n < size());
            //return *(_start + n);
            return _start[n]; //這個也可以
        }

reserve

擴容空間  但不初始化

這里需要注意擴容后的三個屬性更新出現的問題  正常運行會崩潰，  問題的關鍵：開辟一個新空間時，他們三個的型別是指標！而不是下標，一個地址更新，去用以前的指標，去更改這個新的地址，是會崩潰的，而下標是固定位置，地址在怎么更新，下標的位置就是固定的，

我們需要記錄原先的有效字符個數

正常比較和擴容，只是這里用memcpy函式時，出現嵌套情況時，會出現淺拷貝情況

需要用賦值 深拷貝

另外兩個要更新時，要用預先存盤好的資料來更新 詳情看注釋！

        void reserve(size_t n)
        {
            size_t sz = size();
            if (n > capacity())
            {
                T* tmp = new T[n];
                if (_start)  //如果_start為空時 就不需要拷貝資料了
                {
                    //memcpy(tmp, _start, size() * sizeof(T));//把_start的資料拷貝到tmp  //這樣做 在嵌套時，會發生淺拷貝
                    for (size_t i = 0; i < size(); i++)//正確做法是直接賦值  在vector<vector> 這種嵌套時 是深拷貝
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;//更新過后 _start就不再是nullptr
            }
            //_finish = _start + size();//×  結果為空 解參考無地址 賦值會崩潰 ==_start+(_finish-_start)  這里的_finsih最后是等于空  
            //而跳出函式后 _finish解參考再賦值會崩潰 因為空地址無法賦值

            _finish = _start + sz;//√ 結果為_start有地址，解參考能賦值   ==_start+0 ==  這里先讓原先的_finish-_start==0  再+上0  因為_start已經更新過了 所以需要在開頭記錄_size的大小 
            //而更新過的_start不是空 這時候在呼叫size _finish-_start就不是0了 而是其他值了
            _endofstoage = _start + n;
        }

resize

擴容，但會初始化資料

要擴容的大小 大于實際 空間大小（不是實際字符大小！） 時，我們先開需要大小空間即可

如果n大于實際字符大小時

我們需要在實際字符的位置后開始不斷添加val（要初始化的值）

如果n小于實際字符大小

那么就把實際字符大小改為  n個  即 初始值+n

        void resize(size_t n, T val = T())
        {
            if (n > capacity())
            {
                reserve(n);
            }

            if (n > size())
            {
                while (_finish < _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }

push_back()

添加字符

只要需要添加字符的函式，基本是需要檢查空間是否足夠的

一種情況為 實際空間為0 還未擴容時 默認給它開4個空間，如果有空間，但滿時，擴二倍即可（為什么擴容二倍？沒什么！因為合適 或者1.5倍，擴容其他倍數要么太小，要么太大，1.5和2的倍數是適應性最好的）

擴容好后，或者空間足夠時

直接在有效字符的位置添加字符 （為什么不先++？因為前面說過，實際字符的指標實際上是指向實際字符的后一位，所以你要添加，直接在實際字符指標添加即可）

最后添加好后，實際字符++ （這也是回傳真實字符時，不直接回傳_finish，而是回傳_finish-_start

因為嵌套的作用，此函式在insert函式實作后，可以直接復用insert就可以了

        void push_back(const T& x)
        {
            /*if (_finish == _endofstoage)
            {
                size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newCapacity);
            }

            *_finish = x;
            ++_finish;*/

            insert(end(), x);
        }

pop_back()

此函式只需要把實際字符--即可

先判斷合法性，實際字符必須大于初始值

因為嵌套的作用，此函式在erase函式實作后，可以直接復用erase就可以了

        void pop_back()
        {
            /*        if (_finish > _start)
                    {
                        --_finish;
                    }*/
            erase(end() - 1);
        }

insert

注意此函式會有迭代器失效問題！

通常此函式是不需要回傳的，但因為迭代器失效問題，所以必須有回傳值，因為回傳的就是此指向此函式的指標 也就是T* 模版型別指標  所以用重命名的iterator即可  

pos是指向要插入的位置，這個函式都是用指標來指標，所以沒辦法使用下標，這也是它的失效的問題之一！

首先判斷是否需要擴容

上面的reserve提到過，擴容后，_start的地址是會變的，而pos也是迭代器，它也是指向這個地址的指標，它不會跟著更新地址而變化，

所以這個pos它指向的位置，是原來_start的位置，而這個位置已經被釋放了，所以再去使用這個pos時，是會崩潰的！ 

所以為了防止這種情況，我們需要先記錄這個pos的位置，等待_start的地址更新好后，我們要根據原先這個存盤好pos的位置，在去用_start的地址，去更新新的pos位置，并且pos的位置不變，

然后開始移動pos后的資料 給pos位置開出空間，能讓val插入

最后在pos的位置插入val

再++實際空間

最后需要放回插入后的位置

那么我們在使用是，需要用迭代器去接收，才能防止迭代器的失效，因為原先的迭代器已經失效，需要根據這個回傳值，來更新迭代器，

    while (it != v1.end())
    {
        if (*it % 2 == 0)
        {
            it = v1.insert(it, 100);//因為迭代器更新資料會失效 所以要用it接收 防止失效
            ++ it;//回傳的是插入的位置 再次++會再次遇到原來的位置 所以插入后 要自增++一次
        }
        ++it;
    }

erase

此函式存在迭代器失效的問題

正常洗掉即可

只是回傳必須回傳洗掉后的下一個值

使用這個函式時，也是需要迭代器用函式回傳值接收，來更新迭代器

    while (it != v.end())
    {
        if ((*it) % 2 == 0)
        {
            it = v.erase(it);
        }
        else
        {
            ++it;
        }

    }

clear

置空功能，只需要把有效字符置為初始值即可，

        //置空
        void clear()
        {
            _finish = _start;//把有效字符改為初始
        }

接下來是原始碼

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

namespace moxuan
{
    template<class T>
    class vector
    {
    public:
        //迭代器
        typedef T* iterator;
        typedef const T* const_iterator;

        //默認無參構造
        vector()
            :_start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {}

        //用迭代器構造的建構式
        template <class InputIterator>
        vector(InputIterator first, InputIterator last)
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        //構造n個val的建構式
        vector(size_t n, const T& val = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

        //構造n個val的建構式
        //因為用int會呼叫到其他函式 所以為了區分 單獨寫出一個第一個為int
        vector(int n, const T& val = T())
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

        //交換
        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endofstoage, v._endofstoage);
        }

        //拷貝構造
        vector(const vector<T>& v)
            : _start(nullptr)
            , _finish(nullptr)
            , _endofstoage(nullptr)
        {
            vector<T> tmp(v.begin(), v.end());//復用用迭代器構造的建構式
            swap(tmp);
        }

        vector<T>& operator=(vector<T> v)//賦值多載   不用參考  現代寫法
        {
            swap(v);//現代寫法 
            return *this;
        }

        // 資源管理
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _endofstoage = nullptr;
            }
        }

        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

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

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

        void reserve(size_t n)
        {
            size_t sz = size();
            if (n > capacity())
            {
                T* tmp = new T[n];
                if (_start)  //如果_start為空時 就不需要拷貝資料了
                {
                    //memcpy(tmp, _start, size() * sizeof(T));//把_start的資料拷貝到tmp  //這樣做 在嵌套時，會發生淺拷貝
                    for (size_t i = 0; i < size(); i++)//正確做法是直接賦值  在vector<vector> 這種嵌套時 是深拷貝
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;//更新過后 _start就不再是nullptr
            }
            //_finish = _start + size();//×  結果為空 解參考無地址 賦值會崩潰 ==_start+(_finish-_start)  這里的_finsih最后是等于空  
            //而跳出函式后 _finish解參考再賦值會崩潰 因為空地址無法賦值

            _finish = _start + sz;//√ 結果為_start有地址，解參考能賦值   ==_start+0 ==  這里先讓原先的_finish-_start==0  再+上0  因為_start已經更新過了 所以需要在開頭記錄_size的大小 
            //而更新過的_start不是空 這時候在呼叫size _finish-_start就不是0了 而是其他值了
            _endofstoage = _start + n;
        }

        void resize(size_t n, T val = T())
        {
            if (n > capacity())
            {
                reserve(n);
            }

            if (n > size())
            {
                while (_finish < _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }

        void push_back(const T& x)
        {
            /*if (_finish == _endofstoage)
            {
                size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newCapacity);
            }

            *_finish = x;
            ++_finish;*/

            insert(end(), x);
        }

        void pop_back()
        {
            /*        if (_finish > _start)
                    {
                        --_finish;
                    }*/
            erase(end() - 1);
        }

        T& operator[](size_t n)
        {
            assert(n < size());
            //return *(_start + n);
            return _start[n]; //這個也可以
        }

        const T& operator[](size_t n) const
        {
            assert(n < size());
            //return *(_start + n);
            return _start[n]; //這個也可以
        }

        //插入 注意會有迭代器失效問題!
        iterator insert(iterator pos, const T& val)
        {
            assert(pos >= _start && pos <= _finish);
            if (_finish == _endofstoage)
            {
                size_t n = pos - _start;//因為更新start后 pos無法跟著更新 所以要記錄pos的位置
                size_t newsize = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newsize);
                pos = _start + n;
            }
            iterator cur = _finish - 1;
            while (cur >= pos)
            {
                *(cur + 1) = *cur;
                --cur;
            }
            *pos = val;
            ++_finish;
            return pos;
        }

        //洗掉
        iterator erase(iterator pos)//回傳洗掉后的下一個位置
        {
            assert(pos >= _start && pos < _finish);
            iterator it = pos+1;
            while (it != _finish)
            {
                *(it-1) = *it;
                ++it;
            }
            --_finish;
            return pos++;//回傳洗掉后的下一個位置
        }

        //置空
        void clear()
        {
            _finish = _start;//把有效字符改為初始
        }

    private:
        iterator _start;
        iterator _finish;
        iterator _endofstoage;
    };

接下來是用來測驗這個vector的可行性  楊輝三角

大家可以原始碼拿去編譯器上，然后呼叫這個test4函式即可

    class Solution {
    public:
        vector<vector<int>> generate(int numRows) {
            vector<vector<int>> vv;
            vv.resize(numRows);
            for (size_t i = 0; i < vv.size(); ++i)
            {
                // 楊輝三角，每行個數依次遞增
                vv[i].resize(i + 1, 0);

                // 第一個和最后一個初始化成1
                vv[i][0] = 1;
                vv[i][vv[i].size() - 1] = 1;
            }

            for (size_t i = 0; i < vv.size(); ++i)
            {
                for (size_t j = 0; j < vv[i].size(); ++j)
                {
                    if (vv[i][j] == 0)
                    {
                        // 中間位置等于上一行j-1 和 j個相加
                        vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
                    }
                }
            }

            for (size_t i = 0; i < vv.size(); ++i)
            {
                for (size_t j = 0; j < vv[i].size(); ++j)
                {
                    cout << vv[i][j] << " ";
                }
                cout << endl;
            }
            cout << endl;

            return vv;
        }
    };

    void test4()
    {
        vector<vector<int>> ret = Solution().generate(5);

        for (size_t i = 0; i < ret.size(); ++i)
        {
            for (size_t j = 0; j < ret[i].size(); ++j)
            {
                cout << ret[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
}

這就是本文章的全部內容，感謝您能觀看到這里，如有問題請評論或私信，感謝觀看！

標籤：其他

上一篇：day30-注解

下一篇：Spring(四）-宣告式事務