阅读 289

C++中vector的模拟实现实例详解

vector是表示可变大小数组的序列容器,它也采用连续存储空间来存储元素,因此可以采用下标对vector的元素进行访问,这篇文章主要给大家介绍了关于C++中vector模拟实现的相关资料,需要的朋友可以参考下

目录

  • vector接口总览

  • 默认成员函数

    • 构造函数

    • 拷贝构造

    • 赋值重载

    • 析构函数

  • 迭代器相关函数

    • begin和end

  • 容量相关函数

    • size和capacity

    • reserve

    • resize

    • empty

  • 修改容器相关函数

    • push_back

    • pop_back

    • insert

    • erase

    • swap

  • 访问容器相关函数

    • operator[ ]

  • 总结

    vector接口总览

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    namespace nzb
    {
        //模拟实现vector
        template<class T>
        class vector
        {
        public:
            typedef T* iterator;
            typedef const T* const_iterator;
     
            //默认成员函数
            vector();                                           //构造函数
            vector(size_t n, const T& val);                     //构造函数
            template<class InputIterator>
            vector(InputIterator first, InputIterator last);    //构造函数
            vector(const vector<T>& v);                         //拷贝构造函数
            vector<T>& operator=(const vector<T>& v);           //赋值重载
            ~vector();                                          //析构函数
     
            //迭代器相关函数
            iterator begin();
            iterator end();
            const_iterator begin()const;
            const_iterator end()const;
     
            //容量相关函数
            size_t size()const;
            size_t capacity()const;
            void reserve(size_t n);
            void resize(size_t n, const T& val = T());
            bool empty()const;
     
            //修改容器相关函数
            void push_back(const T& x);
            void pop_back();
            void insert(iterator pos, const T& x);
            iterator erase(iterator pos);
            void swap(vector<T>& v);
     
            //访问容器相关函数
            T& operator[](size_t i);
            const T& operator[](size_t i)const;
     
        private:
            iterator _start;        //指向容器的头
            iterator _finish;       //指向有效数据的尾
            iterator _endofstorage; //指向容器的尾
        };
    }

    默认成员函数

    构造函数

    1、无参构造，将所有成员变量初始化为空指针即可

    1
    2
    3
    4
    5
    vector()
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {}

    2、构造一个含有n个值为val的vector容器。

    先将容器容量扩大到n，再尾插val

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    vector(size_t n, const T& val)
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        reserve(n); //扩容
        for (size_t i = 0; i < n; i++) //尾插
        {
            push_back(val);
        }
    }

    3、利用迭代器区间进行构造

    因为迭代器区间可以是其他迭代器区间，所以我们要重新定义一块模板，再将迭代器中的数据尾插

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        while (first != last)
        {
                push_back(*first);
                first++;
        }
    }

    拷贝构造

    传统写法

    先将容器容量扩大到n，再尾插原vector类中的数据（这里扩容和尾插调整了容器尾指针和数据尾指针，我们不必再次调整）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    vector(const vector<T>& v)
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        reserve(v.capacity());
        for (const auto& e : v)
        {
            push_back(e);
        }
    }

    现代写法

    利用迭代器构造一份vector类，再交换该类和拷贝构造的类

    1
    2
    3
    4
    5
    6
    7
    8
    vector(const vector<T>& v)
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        vector<T> tmp(v.begin(), v.end());
        swap(tmp);
    }

    赋值重载

    传统写法

    先初始化原来vector类的空间，再将数据拷贝过来

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<T>& operator=(const vector<T>& v)
    {
        if (this != &v)
        {
            delete[] _start;
            _start = _finish = _endofstorage = nullptr;
     
            reserve(v.capacity());
            for (const auto& e : v)
            {
                push_back(e);
            }
        }  
        return *this;
    }

    现代写法

    现代写法极为巧妙，利用传值的特性（出了函数立即销毁）传入vector类，再交换该类和拷贝构造的类达到赋值的效果

    1
    2
    3
    4
    5
    vector<T>& operator=(vector<T> v)
    {
        swap(v);
        return *this;
    }

    析构函数

    释放开辟存储数据的空间，再将容器的各个成员变量置为空

    1
    2
    3
    4
    5
    ~vector()
    {
        delete[] _start;
        _start = _finish = _endofstorage = nullptr;
    }

    迭代器相关函数

    vector当中的迭代器实际上就是容器当中所存储数据类型的指针。

    1
    2
    typedef T* iterator;
    typedef const T* const_iterator;

    begin和end

    vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。

    1
    2
    3
    4
    5
    6
    7
    8
    iterator begin()
    {
        return _start;
    }
    iterator end()
    {
        return _finish;
    }

    我们还需写一份const版本，const版本只能读不能写，防止vector中数据被修改

    1
    2
    3
    4
    5
    6
    7
    8
    const_iterator begin() const
    {
        return _start;
    }
    const_iterator end() const
    {
        return _finish;
    }

    容量相关函数

    size和capacity

    size表示vector容器中已存储有效数据个数而capacity表示vector容器的最大容量，那如何得出该组数据呢？

    我们知道vector成员函数_start,_finish,_endofstorage是指针，而指针减指针得到两个指针间的数据个数，我们可以用_finish-_start得到size,用_endofstorage-_start得到capacity

    1
    2
    3
    4
    5
    6
    7
    8
    size_t size() const
    {
        return _finish - _start;
    }
    size_t capacity() const
    {
        return _endofstorage - _start;
    }

    reserve

    当n大于当前的capacity时，将capacity扩大到n或大于n。

    当n小于当前capacity时什么也不做。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void reserve(size_t n)
    {
        if (n > capacity())
        {
            size_t sz = size(); // 记录原容器中数据个数
            T* tmp = new T[n]; // 开辟一块容量为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;
        }
    }

    注意：这里拷贝数据不能用memcpy。当我们拷贝的是一些简单的常量时是没有问题的，但是当我们拷贝的是另一个类，如string类时，拷贝的string还是指向原来string类指向的空间。当原来string被释放时，原string类指向的空间也被释放，此时拷贝的string类指向的是一块已被释放的空间，程序结束时它将再次被释放，释放一块已被释放的空间程序报错。

    resize

    当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。

    当n小于当前的size时，将size缩小到n。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void resize(size_t n, const T& val = T())
    {
        if (n <= size())// 当n小于当前的size时
        {
            _finish = n + _start;// 将size缩小到n
        }
        else // 当n大于当前的size时
        {
            if (n > capacity())// 当n大于容量时，扩容
            {
                reserve(n);
            }
     
            while (_finish < _start + n)// 给size到容器结尾赋值
            {
                *_finish = val;
                _finish++;
            }
        }
    }

    这里用了匿名对象T（）来作为缺省参数

    empty

    通过比较_start和_finish指针来判断容器是否为空

    1
    2
    3
    4
    bool empty()const
    {
        return _start == _finish;
    }

    修改容器相关函数

    push_back

    先判断容器是否已满，如果满了先扩容再尾插，如果没满，直接尾插

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void push_back(const T& x)
    {
        if (_finish == _endofstorage)// 判断是否需要扩容
        {
            size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
            reserve(newcapacity);
        }
        // 尾插数据
        *_finish = x;
        _finish++;
    }

    pop_back

    先判空处理，再–_finish

    1
    2
    3
    4
    5
    void pop_back()
    {
        assert(!empty());// 判空
        --_finish;
    }

    insert

    功能：利用迭代器再指定位置插入数据。

    实现方式：插入前判断是否需要扩容，再将指定位置后的数据往后挪动一位，把数据插入指定位置。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    iterator insert(iterator pos, const T& x)
    {
        assert(pos >= _start&&pos <= _finish);// 判断传入数据的合法性
        if (_finish == _endofstorage)// 扩容
        {
            size_t len = pos - _start;// 记录pos的位置
            size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
            reserve(newcapacity);
            pos = _start + len;
        }
        iterator end = _finish - 1;
        while (end >= pos)// 挪动数据
        {
            *(end + 1) = *end;
            --end;
        }
        *pos = x;// 插入数据
        _finish++;
        return pos;
    }

    注意:扩容时要记录pos和_start的相对位置，避免扩容后迭代器失效问题

    erase

    功能：删除指定位置数据。

    实现方式：先判断传入数据的合法性，在将pos位置后的数据全部往前挪动一位，覆盖掉原pos位置的数据

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    iterator erase(iterator pos)
    {
        assert(pos >= _start&&pos < _finish);// 判断传入数据的合法性
        iterator it = pos + 1;// 利用迭代器记录pos的后一位
        while (it != _finish)// 将pos后的数据往前挪动一位
        {
            *(it - 1) = *it;
            it++;
        }
        _finish--;
     
        return pos;
    }

    swap

    功能：交换两个vector中的数据

    实现方式：利用库函数中的swap进行交换

    1
    2
    3
    4
    5
    6
    void swap(vector<T>& v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endofstorage, v._endofstorage);
    }

    访问容器相关函数

    operator[ ]

    为了方便访问数据vector中也加入了“下标+[ ]”操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    T& operator[](size_t i)// 可读可写
    {
        assert(i < size());
        return _start[i];
    }
     
    const T& operator[](size_t i) const// 只能读
    {
        assert(i<size());
        return _start[i];
    }

    总结

    到此这篇关于C++中vector的模拟实现的文章就介绍到这了

    原文链接：https://blog.csdn.net/qq_56663697/article/details/121240754


    文章分类
    代码人生
    文章标签
    c++
    vector
    实例
    版权声明：本站是系统测试站点，无实际运营。本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 XXXXXXo@163.com 举报，一经查实，本站将立刻删除。
    相关推荐