• 【C++学习手札】模拟实现vector

                                                          🎬慕斯主页：修仙—别有洞天

                                                           ♈️今日夜电波：くちなしの言葉—みゆな

                                                                    0:37━━━━━━️💟──────── 5:28
                                                                        🔄   ◀️   ⏸   ▶️    ☰ 

                                          💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍

    目录

    一、vector实际的底层原理

    二、vector的模拟实现

             迭代器相关

             基本操作（迭代器失效问题）

            插入 

            删除 

            push_back（）

            pop_back（）

             swap（）

             基本成员函数

             构造函数

            拷贝构造函数 

            析构函数 

            赋值运算符 

             空间管理

            基本状态 

             扩容操作

            resize（） 

             重载[ ]（最爱的运算符！！！）

     三、整体代码

    一、vector实际的底层原理

            C++中的vector底层实现是一个动态数组，也被称为可变数组。当向vector添加元素时，如果数组已经被填满，vector会自动创建一个更大的数组，将原有数据复制到新数组中，并将新元素添加到新数组中。这种自动扩容的机制使得vector能够封装任意数量的对象，而不必关心底层的数组大小。

            vector的成员变量同前面我们学的string不一样，他是通过使用指针来控制起始位置、最后一个数据位置、最大容量位置。定义如下：

    1. class vector
    2. {
    3. public:
    4. 	typedef T* iterator;
    5. 	typedef const T* const_iterator;
    6. private:
    7. 	iterator _start;  
    8. 	iterator _finish;
    9. 	iterator _endofstorage;
    10. };

            配合图解明白： 

    二、vector的模拟实现

             迭代器相关

    1.         // Vector的迭代器是一个原生指针
    2.  
    3.         typedef T* iterator;
    4.         typedef const T* const_iterator;
    5.  
    6.         iterator begin()
    7.         {
    8.             return _start;
    9.         }
    10.  
    11.         iterator end()
    12.         {
    13.             return _finish;
    14.         }
    15.  
    16.         const_iterator begin() const
    17.         {
    18.             return _start;
    19.         }
    20.  
    21.         const_iterator end() const
    22.         {
    23.             return _finish;
    24.         }

             基本操作（迭代器失效问题）

            插入 

            在插入元素期间，可能会引起扩容，让三个指针都指向新的空间，原空间被释放，从而导致原来的迭代器指向的空间错误，对此我们可以返回新的空间的地址解决。

    1.  iterator insert(iterator pos, const T& x)//迭代器失效，返回新的迭代器解决
    2.             {
    3.                     assert(pos >= _start);
    4.                     assert(pos <= finish);
    5.  
    6.                     if (_finish == _endOfStorage)
    7.                     {
    8.                         size_t len = pos - _start;//避免位置错误,因为在扩容后_start的地址会变化
    9.                         reserve(capacity() == 0 ? 4 : capacity() * 2);
    10.                         pos = start + len;//恢复位置
    11.                     }
    12.  
    13.                     iterator end = _finish - 1;
    14.                     while (end >= pos)//从后往前挪
    15.                     {
    16.                         *(end + 1) = *end;
    17.                         --end;
    18.                     }
    19.  
    20.                     *pos = x;
    21.                     ++_finish;
    22.  
    23.                     return pos;
    24.             }
    25.

            删除 

             删除由于受限制，在这里实现的时候只能通过返回指针来控制删除。通常在使用 erase 进行删除时，我们需要额外定义一个迭代器来接受原迭代器，通过选择语句来进行批量删除的判断。有如下例子：（我们要删除迭代器中可以被2整除的数，以此解决迭代器的问题）

     

    1. iterator erase(Iterator pos)//迭代器失效，返回新的迭代器解决
    2.                 {
    3.                     assert(pos >= _start);
    4.                     assert(pos < _finish);
    5.  
    6.                     iterator it = pos + 1;//定义一个变量用于删除
    7.                     while (it < _finish)
    8.                     {
    9.                         *(it - 1) = *it;
    10.                         ++it;
    11.                     }
    12.  
    13.                     --_finish;
    14.  
    15.                     return pos;
    16.             }

            push_back（）

            复用以上insert的操作，简化代码 。

    1.  void push_back(const T& x)
    2.             {/*
    3.         if (_finish == _endofstorage)
    4.         {
    5.             reserve(capacity() == 0 ? 4 : capacity() * 2);
    6.         }
    8.         *_finish = x;
    9.         ++_finish;*/
    10.  
    11.                 insert(end(), x);
    12.             }

            pop_back（）

    1.             void pop_back()
    2.             {
    3.                 assert(!empty());
    4.  
    5.                 --_finish;
    6.             }

             swap（）

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

             基本成员函数

            主要是复用上面的基本操作以此来简化代码。 

             构造函数

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

            在构造时，由于我们都要初始化。我们可以直接给成员变量在定义时就给缺省值，剩下的两个分别是根据指定数量、指定初始化值，以及根据迭代器构造。 

    1.             vector()
    2.             {}
    3.  
    4.             vector(int n, const T& value = T())
    5.             {
    6.                 reserve(n);
    7.                 for (int i = 0; i < n; i++)
    8.                 {
    9.                     push_back(value);
    10.                 }
    11.             }
    12.  
    13.         template<class InputIterator>
    14.         vector(InputIterator first, InputIterator last)
    15.         {
    16.             while (first != last)
    17.             {
    18.                 push_back(*first);
    19.                 ++first;
    20.             }
    21.         }

            拷贝构造函数 

            特别注意，在进行拷贝构造时，不要使用memcpy，在对诸如：string等类型进行拷贝时，执行的是浅拷贝。我们在这复用push_back()来进行拷贝构造。

    1.  
    2.         vector(const vector& v)
    3.         {
    4.             reserve(v.capacity());
    5.             for (auto& e : v)
    6.             {
    7.                 push_back(e);
    8.             }
    9.             }

            析构函数 

            需要释放在堆上动态开辟的空间，并且将指针置空，防止野指针。

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

            赋值运算符 

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

             空间管理

            基本状态 

    1.         size_t capacity() const
    2.         {
    3.             return _endofstorage - _start;
    4.         }
    5.  
    6.         size_t size() const
    7.         {
    8.             return _finish - _start;
    9.         }
    10.  
    11.         bool empty()const
    12.         {
    13.             return size() == 0;
    14.         }

             扩容操作

            注意这里不能使用memcpy进行对原有数据的拷贝操作，使用memcpy对于一些存储结构，如string等所做的是浅拷贝的操作。对此，使用会造成很多问题。

    1.         void reserve(size_t n)
    2.         {
    3.             if (n > capacity())
    4.             {
    5.                 T* tmp = new T[n];
    6.                 size_t sz = size();
    7.  
    8.                 if (_start)
    9.                 {
    10.                     //memcpy(tmp, _start, sizeof(T) * sz)//这里用memcpy这里会导致string的vector出错，浅拷贝问题
    11.  
    12.                     for (size_t i = 0; i < sz; i++)
    13.                     {
    14.                         tmp[i] = _start[i];
    15.                     }
    16.  
    17.                     delete[] _start;
    18.                 }
    19.                 _start = tmp;
    20.                 _finish = _start + sz;
    21.                 _endOfStorage = _start + n;
    22.             }
    23.  
    24.         }

            resize（） 

             如果要扩的空间(n)小于当前数据个数，则截取数据。如果要扩的空间(n)大于当前数据个数则扩容。

    1.         void resize(size_t n, const T& value = T())
    2.         {
    3.             if (n < size())
    4.             {
    5.                 _finish =_start + n;
    6.             }
    7.             else
    8.             {
    9.                 reserve(n);
    10.                 while (_finish < _start + n)
    11.                 {
    12.                     *_finish = val;
    13.                     ++_finish;
    14.                 }
    15.             }
    16.  
    17.         }

             重载[ ]（最爱的运算符！！！）

    1.         T& operator[](size_t pos)
    2.         {
    3.             assert(pos < size());
    4.             
    5.             return _start[pos];
    6.             }
    7.  
    8.         const T& operator[](size_t pos)const
    9.         {
    10.             assert(pos < size());
    11.  
    12.             return _start[pos];
    13.             }

     三、整体代码

    1. #pragma once
    2. #define _CRT_SECURE_NO_WARNINGS 01
    3. #include
    4. using namespace std;
    5.  
    6. namespace lt
    7.  
    8. {
    9.  
    10.     template<class T>
    11.  
    12.     class vector
    13.  
    14.     {
    15.  
    16.     public:
    17.  
    18.         // Vector的迭代器是一个原生指针
    19.  
    20.         typedef T* iterator;
    21.         typedef const T* const_iterator;
    22.  
    23.         iterator begin()
    24.         {
    25.             return _start;
    26.         }
    27.  
    28.         iterator end()
    29.         {
    30.             return _finish;
    31.         }
    32.  
    33.         const_iterator begin() const
    34.         {
    35.             return _start;
    36.         }
    37.  
    38.         const_iterator end() const
    39.         {
    40.             return _finish;
    41.         }
    42.  
    43.  
    44.  
    45.             // construct and destroy
    46.  
    47.             vector()
    48.                 :_start(nullptr)
    49.                 ,_finish(nullptr)
    50.                 ,_endOfStorage(nullptr)
    51.             {}
    52.  
    53.             vector(int n, const T& value = T())
    54.             {
    55.                 reserve(n);
    56.                 for (int i = 0; i < n; i++)
    57.                 {
    58.                     push_back(value);
    59.                 }
    60.             }
    61.  
    62.         template<class InputIterator>
    63.         vector(InputIterator first, InputIterator last)
    64.         {
    65.             while (first != last)
    66.             {
    67.                 push_back(*first);
    68.                 ++first;
    69.             }
    70.         }
    71.  
    72.         vector(const vector& v)
    73.         {
    74.             reserve(v.capacity());
    75.             for (auto& e : v)
    76.             {
    77.                 push_back(e);
    78.             }
    79.             }
    80.  
    81.         vector& operator= (vector v)
    82.         {
    83.             swap(v);
    84.             return *this;
    85.             }
    86.  
    87.         ~vector()
    88.         {
    89.             delete[] _start;
    90.             _start = _finish = _endofstorage = nullptr;
    91.             }
    92.  
    93.             // capacity
    94.  
    95.              size_t capacity() const
    96.         {
    97.             return _endofstorage - _start;
    98.         }
    99.  
    100.         size_t size() const
    101.         {
    102.             return _finish - _start;
    103.         }
    104.  
    105.         bool empty()const
    106.         {
    107.             return size() == 0;
    108.         }
    109.  
    110.         void reserve(size_t n)
    111.         {
    112.             if (n > capacity())
    113.             {
    114.                 T* tmp = new T[n];
    115.                 size_t sz = size();
    116.  
    117.                 if (_start)
    118.                 {
    119.                     //memcpy(tmp, _start, sizeof(T) * sz)//这里用memcpy这里会导致string的vector出错，浅拷贝问题
    120.  
    121.                     for (size_t i = 0; i < sz; i++)
    122.                     {
    123.                         tmp[i] = _start[i];
    124.                     }
    125.  
    126.                     delete[] _start;
    127.                 }
    128.                 _start = tmp;
    129.                 _finish = _start + sz;
    130.                 _endOfStorage = _start + n;
    131.             }
    132.  
    133.         }
    134.  
    135.         void resize(size_t n, const T& value = T())
    136.         {
    137.             if (n < size())
    138.             {
    139.                 _finish =_start + n;
    140.             }
    141.             else
    142.             {
    143.                 reserve(n);
    144.                 while (_finish < _start + n)
    145.                 {
    146.                     *_finish = val;
    147.                     ++_finish;
    148.                 }
    149.             }
    150.  
    151.         }
    152.  
    153.  
    154.  
    155.             ///access///
    156.  
    157.         T& operator[](size_t pos)
    158.         {
    159.             assert(pos < size());
    160.             
    161.             return _start[pos];
    162.             }
    163.  
    164.         const T& operator[](size_t pos)const
    165.         {
    166.             assert(pos < size());
    167.  
    168.             return _start[pos];
    169.             }
    170.  
    171.  
    172.  
    173.             ///modify/
    174.  
    175.             void push_back(const T& x)
    176.             {/*
    177.         if (_finish == _endofstorage)
    178.         {
    179.             reserve(capacity() == 0 ? 4 : capacity() * 2);
    180.         }
    182.         *_finish = x;
    183.         ++_finish;*/
    184.  
    185.                 insert(end(), x);
    186.             }
    187.  
    188.             void pop_back()
    189.             {
    190.                 assert(!empty());
    191.  
    192.                 --_finish;
    193.             }
    194.  
    195.             void swap(vector& v)
    196.             {
    197.                 std::swap(_start, v._start);
    198.                 std::swap(_finish, v._finish);
    199.                 std::swap(_endofstorage, v._endofstorage);
    200.             }
    201.  
    202.                 iterator insert(iterator pos, const T& x)//迭代器失效，返回新的迭代器解决
    203.             {
    204.                     assert(pos >= _start);
    205.                     assert(pos <= finish);
    206.  
    207.                     if (_finish == _endOfStorage)
    208.                     {
    209.                         size_t len = pos - _start;//避免位置错误,因为在扩容后_start的地址会变化
    210.                         reserve(capacity() == 0 ? 4 : capacity() * 2);
    211.                         pos = start + len;//恢复位置
    212.                     }
    213.  
    214.                     iterator end = _finish - 1;
    215.                     while (end >= pos)//从后往前挪
    216.                     {
    217.                         *(end + 1) = *end;
    218.                         --end;
    219.                     }
    220.  
    221.                     *pos = x;
    222.                     ++_finish;
    223.             }
    224.  
    225.                 iterator erase(Iterator pos)//迭代器失效，返回新的迭代器解决
    226.                 {
    227.                     assert(pos >= _start);
    228.                     assert(pos < _finish);
    229.  
    230.                     iterator it = pos + 1;//定义一个变量用于删除
    231.                     while (it < _finish)
    232.                     {
    233.                         *(it - 1) = *it;
    234.                         ++it;
    235.                     }
    236.  
    237.                     --_finish;
    238.  
    239.                     return pos;
    240.             }
    241.  
    242.     private:
    243.  
    244.         iterator _start = nullptr; // 指向数据块的开始
    245.  
    246.         iterator _finish = nullptr; // 指向有效数据的尾
    247.  
    248.         iterator _endOfStorage = nullptr; // 指向存储容量的尾
    249.  
    250.     };
    251.  
    252. }

                           感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！ 

                                           

                                                                             给个三连再走嘛~  

  • 相关阅读:
    三川智控定时控制开关灯
    网络安全（黑客）自学
    如何使用CSS实现一个带有动画效果的折叠面板（Accordion）？
    FME在变更地类流向统计中的应用
    如何查询淘宝天猫的宝贝类目
    Java中StringBuffer.insert()方法具有什么功能呢？
    数据结构复杂度分析
    2022年Spring Cloud Alibaba快速上手教程
    LabVIEW玩转魔方
    Spark处理结构化数据：DataFrame、DataSet、SparkSQL
  • 原文地址：https://blog.csdn.net/weixin_64038246/article/details/134443726