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;
        }

你的有效字符 _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;
    }
}

这就是本文章的全部内容，感谢您能观看到这里，如有问题请评论或私信。感谢观看！

Vector底层实现 - Lonely丶MoXuan

Vector底层实现

Recommend

小蛮腰定律，社交货币的诞生

Purpose Ether ETF在8月减持约7.17万枚ETH，为近一年最大月减持

Sony Xperia 5 IV is finally here, but this camera phone is missing a big feature

资深关卡策划：如何用整体思维做游戏关卡设计？

韩国政府资助开发的“慰安妇题材”抗日游戏，被韩国人自己“喷没了”

Hands-on: Lenovo’s second foldable PC addresses the first’s biggest problems

日本权威动画数据库“动画大全”上线！记录百年发展、收录1.5万部作品

中秋送礼如何选？入手索尼WH-1000XM5头戴式降噪耳机，让TA“静”享浓浓情意-品玩

OptiFi Program Incident Report — 08/29/22

Insurer nib backs Queensland startup Midnight Health in $12 million Series A

About Joyk