C++模擬實(shí)現(xiàn)vector流程詳解

更新時(shí)間：2022年08月08日 15:46:29 作者：戀戀風(fēng)辰

這篇文章主要介紹了C++容器Vector的模擬實(shí)現(xiàn)，Vector是一個(gè)能夠存放任意類(lèi)型的動(dòng)態(tài)數(shù)組，有點(diǎn)類(lèi)似數(shù)組，是一個(gè)連續(xù)地址空間，下文更多詳細(xì)內(nèi)容的介紹，需要的小伙伴可以參考一下

模擬vector

我們可以通過(guò)模板實(shí)現(xiàn)類(lèi)似vector的類(lèi)。我們實(shí)現(xiàn)一個(gè)StrVecTemp類(lèi)，其內(nèi)部通過(guò)allocator開(kāi)辟空間，存儲(chǔ)的類(lèi)型用T來(lái)表示，T是模板類(lèi)型。

template <typename T>
class StrVecTemp
{
public:
    StrVecTemp() : elements(nullptr), first_free(nullptr),
                   cap(nullptr) {}
    //拷貝構(gòu)造函數(shù)
    StrVecTemp(const StrVecTemp &);
    //拷貝賦值運(yùn)算符
    StrVecTemp &operator=(const StrVecTemp &);
    //移動(dòng)構(gòu)造函數(shù)
    StrVecTemp(StrVecTemp &&src) noexcept : elements(src.elements),
                                            first_free(src.first_free), cap(src.cap)
    {
        //將源數(shù)據(jù)置空
        src.elements = src.first_free = src.cap = nullptr;
    }
    template <class... Args>
    void emplace_back(Args &&...args);
    //析構(gòu)函數(shù)
    ~StrVecTemp();
    //拷貝元素
    void push_back(const T &);
    //拋出元素
    void pop_back(T &s);
    //返回元素個(gè)數(shù)
    size_t size() const { return first_free - elements; }
    //返回capacity返回容量
    size_t capacity() const { return cap - elements; }
    //返回首元素的指針
    T *begin() const
    {
        return elements;
    }
    //返回第一個(gè)空閑元素指針
    T *end() const
    {
        return first_free;
    }
private:
    //判斷容量不足靠皮新空間
    void chk_n_alloc()
    {
        if (size() == capacity())
        {
            reallocate();
        }
    }
    //重新開(kāi)辟空間
    void reallocate();
    // copy指定范圍的元素到新的內(nèi)存中
    std::pair<T *, T *> alloc_n_copy(const T *, const T *);
    //釋放空間
    void free();
    //數(shù)組首元素的指針
    T *elements;
    //指向數(shù)組第一個(gè)空閑元素的指針
    T *first_free;
    //指向數(shù)組尾后位置的指針
    T *cap;
    //初始化alloc用來(lái)分配空間
    static std::allocator<T> alloc;
};
template <typename T>
std::allocator<T> StrVecTemp<T>::alloc;

alloc在使用前要在類(lèi)外初始化，因?yàn)槭悄０孱?lèi)，所以放在.h中初始化即可。

接下來(lái)我們要實(shí)現(xiàn)根據(jù)迭代器開(kāi)始和結(jié)束的區(qū)間copy舊元素到新的空間里

//實(shí)現(xiàn)區(qū)間copy
template <typename T>
std::pair<T *, T *> StrVecTemp<T>::alloc_n_copy(const T *b, const T *e)
{
    auto newdata = alloc.allocate(e - b);
    //用舊的數(shù)據(jù)初始化新的空間
    auto first_free = uninitialized_copy(b, e, newdata);
    return {newdata, first_free};
}

實(shí)現(xiàn)copy構(gòu)造

//實(shí)現(xiàn)拷貝構(gòu)造函數(shù)
template <class T>
StrVecTemp<T>::StrVecTemp(const StrVecTemp &strVec)
{
    auto rsp = alloc_n_copy(strVec.begin(), strVec.end());
    //利用pair類(lèi)型更新elements, cap, first_free
    elements = rsp.first;
    first_free = rsp.second;
    cap = rsp.second;
}

實(shí)現(xiàn)copy賦值

//拷貝賦值運(yùn)算符
template <class T>
StrVecTemp<T> &StrVecTemp<T>::operator=(const StrVecTemp &strVec)
{
    if (this == &strVec)
    {
        return *this;
    }
    //如果不是自賦值，就將形參copy給自己
    auto rsp = alloc_n_copy(strVec.begin(), strVec.end());
    elements = rsp.first;
    first_free = rsp.second;
    cap = rsp.second;
}

析構(gòu)函數(shù)要先銷(xiāo)毀數(shù)據(jù)再回收內(nèi)存

//析構(gòu)函數(shù)
template <class T>
StrVecTemp<T>::~StrVecTemp()
{
    //判斷elements是否為空
    if (elements == nullptr)
    {
        return;
    }
    //緩存第一個(gè)有效元素的地址
    auto dest = elements;
    //循環(huán)析構(gòu)
    for (size_t i = 0; i < size(); i++)
    {
        //析構(gòu)每一個(gè)元素
        alloc.destroy(dest++);
    }
    //再回收內(nèi)存
    alloc.deallocate(elements, cap - elements);
    elements = nullptr;
    cap = nullptr;
    first_free = nullptr;
}

重新開(kāi)辟空間

template <class T>
void StrVecTemp<T>::reallocate()
{
    T *newdata = nullptr;
    //數(shù)組為空的情況
    if (elements == nullptr || cap == nullptr || first_free == nullptr)
    {
        newdata = alloc.allocate(1);
        elements = newdata;
        first_free = newdata;
        // cap指向數(shù)組尾元素的下一個(gè)位置
        cap = newdata + 1;
        return;
    }
    //原數(shù)據(jù)不為空，則擴(kuò)充size兩倍大小
    newdata = alloc.allocate(size() * 2);
    //新內(nèi)存空閑位置
    auto dest = newdata;
    //就內(nèi)存的有效位置
    auto src = elements;
    //通過(guò)移動(dòng)操作將舊數(shù)據(jù)放到新內(nèi)存中
    for (size_t i = 0; i != size(); ++i)
    {
        alloc.construct(dest++, std::move(*src++));
    }
    //移動(dòng)完舊數(shù)據(jù)后一定要?jiǎng)h除
    free();
    //更新數(shù)據(jù)位置
    elements = newdata;
    first_free = dest;
    cap = newdata + size() * 2;
}

上面的函數(shù)用到了free函數(shù)，我們自己實(shí)現(xiàn)一個(gè)free

template <typename T>
void StrVecTemp<T>::free()
{
    //先判斷elements是否為空
    if (elements == nullptr)
    {
        return;
    }
    auto dest = elements;
    //遍歷析構(gòu)每一個(gè)對(duì)象
    for (size_t i = 0; i < size(); i++)
    {
        // destroy 會(huì)析構(gòu)每一個(gè)元素
        alloc.destroy(dest++);
    }
    //再整體回收內(nèi)存
    alloc.deallocate(elements, cap - elements);
    elements = nullptr;
    cap = nullptr;
    first_free = nullptr;
}

壓入元素和彈出元素

//拷貝元素
template <class T>
void StrVecTemp<T>::push_back(const T &t)
{
    chk_n_alloc();
    alloc.construct(first_free++, t);
}
//拋出元素
template <class T>
void StrVecTemp<T>::pop_back(T &s)
{
    //先判斷是否為空
    if (first_free == nullptr)
    {
        return;
    }
    //判斷size為1
    if (size() == 1)
    {
        s = *elements;
        alloc.destroy(elements);
        first_free = nullptr;
        elements = nullptr;
        return;
    }
    s = *(--first_free);
    alloc.destroy(first_free);
}

接下來(lái)要實(shí)現(xiàn)emplace_back，因?yàn)閑mplace_back支持多種構(gòu)造函數(shù)的參數(shù)，所以要用模板參數(shù)列表的方式定義該函數(shù)。

模板參數(shù)列表和形參列表都要用參數(shù)包的方式

template <class T>
template <class... Args>
void StrVecTemp<T>::emplace_back(Args &&...args)
{
    chk_n_alloc();
    alloc.construct(first_free++, forward<Args>(args)...);
}

Args是模板參數(shù)包，args是參數(shù)列表。因?yàn)閏onstruct的參數(shù)可能為右值引用，所以要用forward將原參數(shù)列表類(lèi)型原樣轉(zhuǎn)發(fā)。

// forward既擴(kuò)展了模板參數(shù)包Args，又?jǐn)U展了函數(shù)參數(shù)包args
// std::forward<Args>(args)... 等價(jià)于std::forward<Ti>(ti)
//比如傳遞給emplace_back(10,'c');
//相當(dāng)于調(diào)用 alloc.construct(first_free++, forward<int>(10), forward<char>('c'))
//調(diào)用的就是插入cccccccccc