• (C++ STL) 详解vector模拟实现

    目录

    一.vector的介绍

    1.vector的介绍

    二.vector的定义模拟实现

    三.vector各接口的模拟实现

    1.vector迭代器的模拟实现

    2.构造函数

       2.1无参构造

    2.2 n个val构造

    2.3迭代器区间构造

    2.4通过对象初始化（拷贝构造）

    3.析构函数

    4.size

    5.operator=

    6.capacity

    7.reserve

    8.resize

    9.operator[ ]

    10.insert

    11.push_back

    12.erase

    13.pop_back

    14.empty

    一.vector的介绍

    1.vector的介绍

    这是官方的文档介绍
    cplusplus.com/reference/vector/vector/

    1. vector是表示可变大小数组的序列容器。


    2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。


    3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。


    4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。


    5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。


    6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好

    二.vector的定义模拟实现

    首先我们先 定义一个命名空间 来模拟实现咱们的vector类

    类里面有三个私有 指针变量 分别指向数据块的开始，尾和存储容量的尾

    1. namespace zyl
    2. {
    3.   
    4.  
    5.     template<class T>
    6.     class vector
    7.     {
    8.      public:
    9.       // Vector的迭代器是一个原生指针
    10.       typedef T* iterator;
    11.       typedef const T* const_iterator;
    12.  
    13.      private:
    14.      iterator _start; // 指向数据块的开始
    15.      iterator _finish; // 指向有效数据的尾
    16.      iterator _endOfStorage; // 指向存储容量的尾
    17.     };
    18. }

    三.vector各接口的模拟实现

    1.vector迭代器的模拟实现

    vector的迭代器分为俩种

    一种是普通迭代器 指向的内容可以被修改

    一种是const迭代器 不可以修改只可读

    1.         iterator begin()
    2.         {
    3.             return _start;
    4.         }
    5.         iterator end()
    6.         {
    7.             return _finish;
    8.         }
    9.  
    10.         const_iterator cbegin() const
    11.         {
    12.             return _start;
    13.         }
    14.         const_iterator cend() const
    15.         {
    16.             return _finish;
    17.         }

    2.构造函数

    vector 的四种构造函数

       2.1无参构造

    主要是对各个指针初始化 赋值为空

    1.  vector()
    2.             :_endOfStorage(nullptr)
    3.             ,_start(nullptr)
    4.             ,_finish(nullptr)
    5.         {
    6.  
    7.         }

    2.2 n个val构造

    直接向数组中尾插数据，用reserve提前扩容, 提高效率

    然后需要注意的是  这里传参的第二个参数使用匿名对象，const T& val = T() 这种写法会调用默认构造(可以是任意类型)，我们前面讲内置类型是没有默认构造函数的, 理论而言是没有的, 但是调用模板之后必须要支持默认构造

    1.  vector(int n, const T& value = T())
    2.             :_endOfStorage(nullptr)
    3.             , _start(nullptr)
    4.             , _finish(nullptr)
    5.         {
    6.             reserve(n);//提前开n个空间
    7.             for (int i = 0;i < n;i++)
    8.             {
    9.                 push_back(value);//缺省值默认为val；
    10.             }
    11.         }

    2.3迭代器区间构造

    这里又要使用模板实现， 要实现一个任意类型的迭代器允许任意类型的数据使用，直接用迭代器遍历数组, 尾插数据即可

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

    2.4通过对象初始化（拷贝构造）

         通过传一个vector对象  然后进行交换 

    1.         vector(const vector& v)
    2.         {
    3.             vector tmp(v.cbegin(), v.cend());
    4.             swap(tmp);
    5.         }

    3.析构函数

      析构函数的主要功能 释放掉所有数据 然后三个指针指向空

    1.  
    2.         ~vector()
    3.         {
    4.             delete[]_start;
    5.             _start = nullptr;
    6.             _finish = nullptr;
    7.             _endOfStorage = nullptr;
    8.         }

    4.size

    返回当前vector长度

    1.  size_t size() const
    2.         {
    3.             return _finish - _start;
    4.         }

    5.operator=

    运算符重载=     实现深拷贝 把v对象赋给this

    1.        vector<T>& operator= (vector<T> v)
    2.         {
    3.             if (this != &v)
    4.             {
    5.                 delete[] _start;
    6.                 _start = new T[v.capacity()];
    7.                 for (size_t i = 0;i < v.size();i++)
    8.                 {
    9.                     _start[i] = v[i];
    10.                 }
    11.                 _finish = _start + v.size();
    12.                 _endOfStorage = _start + v.capacity();
    13.             }
    14.             return *this;
    15.         }

    6.capacity

    返回当前vector对象的容量是多少

    1. size_t capacity() const
    2.         {
    3.             return  _endOfStorage - _start;
    4.         }

    7.reserve

    在n>capacity时去进行扩容 是为了防止程序缩容

    判段当前数据是为为空，需不需要旧数据的拷贝转移

    遍历的时候，一定要使用深拷贝，不要使用memcpy去进行拷贝

    1.  void reserve(size_t n)
    2.         {
    3.             if (n >capacity())
    4.             {
    5.                 size_t sz = size();
    6.                 T* tmp = new T[n];
    7.  
    8.                 if (_start)//如果为空  则不用将旧数据转移
    9.                 {
    10.                     for (size_t i = 0;i <size();i++)
    11.                     {
    12.                         tmp[i] = _start[i];
    13.                     }
    14.                     delete[] _start;
    15.                 }
    16.                 _start = tmp;
    17.                 _finish = _start + sz;
    18.                 _endOfStorage = _start + n;
    19.             }
    20.         }

    8.resize

    n < size() 就是删除数据，直接改变 _finish的指向即可

    n > capacity()调用reserve函数扩容， 后遍历给数组赋值

    1.  void resize(size_t n, const T& value = T())
    2.         {
    3.             //查看是否需要扩容
    4.             if (n > capacity())
    5.             {
    6.                 reserve(n);
    7.             }
    8.  
    9.             if (n > size())
    10.             {
    11.                 while (_finish > _start + n)
    12.                 {
    13.                     *_finish = value;
    14.                     ++_finish;
    15.                 }
    16.             }
    17.             else
    18.             {
    19.                 _finish = _start + n;
    20.             }
    21.         }

    9.operator[ ]

    vector也支持下标访问

    重载 [ ] 可以快速的对数据进行访问

    1.  T& operator[](size_t pos)
    2.         {
    3.             assert(pos < size());
    4.             return _start[pos];
    5.         }

    10.insert

    检查容量，观察是否需要扩容, 扩容前计算出pos与start之间，pos与start之间相对距离不变，扩容后更新pos位置(这里存在迭代器失效的问题)

    遍历挪动数据

    将val插入pos位置

    注意: 检查pos位置的合法性

    1. iterator insert(iterator pos, const T& x)
    2.         {
    3.             //pos范围必须在_start和_finish之间
    4.             assert(pos>=_start);
    5.             assert(pos <= _finish);
    6.             //内存满了 进行扩容
    7.             if (_finish == _endOfStorage)
    8.             {
    9.                 size_t len = pos - _start;
    10.                 reseve(capacity() > 0 ? 4 : capacity * 2);
    11.                 pos = _start + len;
    12.             }
    13.             iterator end = _finish;
    14.             //移动数据 进行插入
    15.             while (end >= pos)
    16.             {
    17.                 *end = *(end - 1);
    18.                 end--;
    19.             }
    20.             *pos = x;
    21.             ++_finish;
    22.             return pos;
    23.         }

    11.push_back

    尾插 直接调用insert 在_finish位置去插入

    1. void push_back(const T& x)
    2.         {
    3.             insert(_finish, x);
    4.         }

    12.erase

    erase函数可以删除所给迭代器pos位置的数据

    在删除数据前需要判断容器释放为空

    若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖即可。 

    1. iterator erase(iterator pos)
    2.         {
    3.             //判断pos是否合法
    4.             assert(pos > _finish);
    5.             assert(pos < _start);
    6.             assert(!empty());
    7.  
    8.             iterator begin = pos + 1;
    9.             while (begin < _finish)
    10.             {
    11.                 *(begin - 1) = *begin;
    12.                 ++begin;
    13.             }
    14.             --_finish;
    15.             return pos;
    16.         }

    13.pop_back

    pop_back直接调用erase去_finish位置进行删除

    1.  void pop_back()
    2.         {
    3.             erase(_finish);
    4.         }

    14.empty

    进行判空 直接看_finish == _start是否相同就可以了

    1. bool empty() const
    2.         {
    3.             return _finish == _start;
    4.         }
  • 相关阅读:
    Spring Boot整合Swagger报错："this.condition" is null
    读书笔记： 如何把一件事做到最好
    POST注入/HEAD注入
    zookeeper应用之leader选举
    Linux死锁
    C++模拟实现——红黑树
    【Python零基础入门篇 · 13】：字符串判断扩展、变量作用域、global和nonlocal的使用
    Win10 基于Docker使用tensorflow serving部署模型
    表单提交，页面滚动到必填项位置
    第二证券|抖音发布三季度安全透明度报告，整治贩卖焦虑广告近3万条
  • 原文地址：https://blog.csdn.net/weixin_55582891/article/details/133867708