• vector的模拟实现

    完整代码

    • 这是一个简单的C++实现的vector类模板。vector是一种动态数组，可以根据需要自动扩容和缩容，提供了常用的操作函数如插入、删除、访问等。

    • 该vector类模板包含以下成员函数：

    1. begin()和end()：返回迭代器，用于指向vector的起始和结束位置。

    2. cbegin()和cend()：返回常量迭代器，用于指向vector的起始和结束位置。

    3. capacity()：返回vector的容量，即分配的内存空间大小。

    4. size()：返回vector中元素的个数。

    5. resize()：调整vector的大小，如果n小于当前容量，则直接修改size()的值；如果n大于当前容量，则先通过reserve()函数进行内存的重新分配，再插入新的元素。

    6. swap()：交换两个vector对象的内容。

    7. reserve()：申请至少能容纳n个元素的内存空间，如果n大于当前容量，则重新分配内存；否则不进行操作。

    8. pop_back()：删除vector的最后一个元素。

    9. push_back()：在vector的末尾添加一个元素。

    10. insert()：在指定位置插入一个元素。

    11. erase()：删除指定位置的元素。

    12. 此外，还包括构造函数、拷贝构造函数、赋值运算符重载和析构函数。

    1. #pragma once
    2. #include<assert.h>
    3. namespace hqj
    4. {
    5.  template<class T>
    6.  class vector
    7.  {
    8.  public:
    9.   typedef T* iterator;
    10.   typedef const T* const_iterator;
    11.   //迭代器部分
    12.   iterator begin()
    13.   {
    14.    return _start;
    15.   }
    16.   iterator end()
    17.   {
    18.    return _finish;
    19.   }
    20.  
    21.   const_iterator cbegin()const
    22.   {
    23.    return _start;
    24.   }
    25.  
    26.   const_iterator cend()const
    27.   {
    28.    return _finish;
    29.   }
    30.  
    31.   size_t capacity()const
    32.   {
    33.    return _endOfStorage - _start;
    34.   }
    35.   size_t size()const
    36.   {
    37.    return _finish - _start;
    38.   }
    39.   void resize(size_t n, const T& val = T())
    40.   {
    41.    if (n < capacity())
    42.    {
    43.     _finish = _start+n ;
    44.    }
    45.    else
    46.    {
    47.     reserve(n);
    48.     for (int i = 0; i < n; i++)
    49.     {
    50.      push_back(val);
    51.     }
    52.    }
    53.   }
    54.   //交换函数
    55.   void swap(vector<T>& v)
    56.   {
    57.    std::swap(_start, v._start);
    58.    std::swap(_finish, v._finish);
    59.    std::swap(_endOfStorage, v._endOfStorage);
    60.   }
    61.   //申请内存
    62.   void reserve(size_t n)//返回类型是引用
    63.   {
    64.    if (n > capacity())
    65.    {
    66.     T* tmp = new T[n];
    67.     int sz = size();
    68.  
    69.     if (_start != nullptr)
    70.     {
    71.      for (int i = 0; i < size(); i++)
    72.      {
    73.       tmp[i] = _start[i];
    74.      }
    75.     }
    76.     delete[] _start;
    77.     _start = tmp;
    78.     _endOfStorage = _start + n;
    79.     _finish = _start + sz;
    80.    }
    81.   }
    82.   //尾删
    83.  
    84.   void pop_back()
    85.   {
    86.    assert(size() >= 0);
    87.    _finish--;
    88.   }
    89.   //尾插
    90.   void push_back(const T& x)
    91.   {
    92.    if (_finish == _endOfStorage)
    93.    {
    94.     reserve(capacity() == 0 ? 4 : 2 * capacity());
    95.    }
    96.    *_finish = x;
    97.    _finish++;
    98.   }
    99.   //构造函数
    100.   template<class InputIterator>
    101.  
    102.   vector(InputIterator first, InputIterator last)
    103.   {
    104.    while (first != last)
    105.    {
    106.     push_back(*(InputIterator));
    107.     first++;
    108.    }
    109.   }
    110.  
    111.   vector(const vector<T>& v)
    112.    :_start(nullptr)
    113.    , _finish(nullptr)
    114.    , _endOfStorage(nullptr)
    115.   {
    116.    reserve(v.size());
    117.    for (auto i = v.cbegin();i!=v.cend();i++)
    118.    {
    119.     push_back(*i);
    120.    }
    121.   }
    122.  
    123.   vector<T>& operator= (vector<T> v)
    124.   {
    125.    vector<int> tmp(v);
    126.    swap(tmp);
    127.   }
    128.  
    129.   vector()
    130.    : _start(nullptr)
    131.    , _finish(nullptr)
    132.    , _endOfStorage(nullptr)
    133.   {}
    134.  
    135.   vector(int n, const T& val = T())
    136.   {
    137.    for (int i = 0; i < n; i++)
    138.    {
    139.     push_back(val);
    140.    }
    141.   }
    142.   //析构函数
    143.   ~vector()
    144.   {
    145.    delete[] _start;
    146.    _start = nullptr;
    147.    _finish = nullptr;
    148.    _endOfStorage = nullptr;
    149.   }
    150.   //[]运算符重载
    151.   T& operator[](size_t pos)
    152.   {
    153.    return _start[pos];
    154.   }
    155.   const T& operator[](size_t pos)const
    156.   {
    157.    return _start[pos];
    158.   }
    159.   //随机插入，随机删除
    160.   iterator insert(iterator pos, const T& x)
    161.   {
    162.    assert(pos >= _start);
    163.    assert(pos <= _finish);
    164.  
    165.    if (_finish == _endOfStorage)
    166.    {
    167.     int sz = pos - _start;//记录pos与_start的相对位置
    168.     reserve(capacity() == 0 ? 4 : 2 * capacity());//注意迭代器失效
    169.     pos = _start + sz;//重置迭代器
    170.    }
    171.  
    172.    iterator en = _finish-1;
    173.    while (en >= pos)
    174.    {
    175.     *(en+1) = *(en);
    176.     en--;
    177.    }
    178.  
    179.    *pos = x;
    180.    _finish++;
    181.    return pos;
    182.   }
    183.  
    184.   iterator erase(iterator pos)
    185.   {
    186.    assert(pos >= _start);
    187.    assert(pos <= _finish);
    188.  
    189.    iterator a = pos+1;
    190.    while (a != _finish)
    191.    {
    192.     *(a-1) = *a;
    193.     a++;
    194.    }
    195.  
    196.    _finish--;
    197.    return pos;
    198.   }
    199.  private:
    200.   iterator _start;
    201.   iterator _finish;
    202.   iterator _endOfStorage;
    203.  };

    私有成员

    • _start 是指向存储区域的起始位置的迭代器，表示第一个元素的位置。

    • _finish 是指向实际存储数据区域的最后一个元素之后的空闲位置的迭代器，表示当前已经存储的元素数量。

    • _endOfStorage 是指向分配的内存空间的最后一个位置之后的位置的迭代器，表示当前 vector 可以存储的最大元素数量。如果 _finish 等于 _endOfStorage，那么 vector 已达到最大容量，此时需要扩容才能继续添加元素。

    1. private:
    2.   iterator _start;
    3.   iterator _finish;
    4.   iterator _endOfStorage;

    迭代器部分

    • 在该代码中，通过使用typedef关键字将T和const T定义为iterator和const_iterator类型，分别表示可修改和只读的迭代器。

    • 然后，定义了以下成员函数来获取迭代器：

    1. begin()：返回一个指向vector起始位置的迭代器。

    2. end()：返回一个指向vector结束位置的迭代器，即最后一个元素的下一个位置。

    3. cbegin()：返回一个指向vector起始位置的常量迭代器，不允许修改元素。

    4. cend()：返回一个指向vector结束位置的常量迭代器，不允许修改元素。 通过使用迭代器，可以方便地遍历vector容器中的元素

    1. typedef T* iterator;
    2.   typedef const T* const_iterator;
    3.   //迭代器部分
    4.   iterator begin()
    5.   {
    6.    return _start;
    7.   }
    8.   iterator end()
    9.   {
    10.    return _finish;
    11.   }
    12.  
    13.   const_iterator cbegin()const
    14.   {
    15.    return _start;
    16.   }
    17.  
    18.   const_iterator cend()const
    19.   {
    20.    return _finish;
    21.   }
    22.

    capacity函数

    • 在实现中，使用指针之间的减法运算符来计算 _endOfStorage - _start 的值。其中 _endOfStorage 表示已分配内存空间的尾部位置， _start 表示 vector 的起始位置。

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

    size函数

    • 在实现中，使用指针之间的减法运算符来计算偏移量，从而得到 _finish - _start 的值。其中 _finish 表示 vector 的结束位置， _start 表示 vector 的起始位置。

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

    resize函数

    • 在函数实现中，首先判断 n 是否小于当前的容量 capacity()。如果是，则直接将结束位置 _finish 设置为 _start + n，即截断 vector，不需进行内存重新分配。

    • 如果 n 大于或等于当前的容量，意味着需要重新分配内存空间。此时调用 reserve(n) 函数来扩展 vector 的容量至至少 n，确保有足够的空间容纳新的元素。然后使用循环将元素 val 依次添加到 vector 中，使用 push_back() 函数将元素添加至末尾。这样就实现了重新分配内存并初始化新元素的功能。

    1. void resize(size_t n, const T& val = T())
    2.   {
    3.    if (n < capacity())
    4.    {
    5.     _finish = _start+n ;
    6.    }
    7.    else
    8.    {
    9.     reserve(n);
    10.     for (int i = 0; i < n; i++)
    11.     {
    12.      push_back(val);
    13.     }
    14.    }
    15.   }

    reserve函数

    • 在函数实现中，首先判断 n 是否大于当前的容量 capacity()。如果是，则需要重新分配内存空间。

    • 首先创建一个临时指针 tmp，调用 new 运算符申请一个大小为 n 的新数组。然后通过循环将原始 vector 中的元素逐个复制到新的数组中。

    • 接下来释放原始内存空间，使用 delete[] 运算符删除原始指针 _start 所指向的数组。然后将新的数组指针 tmp 赋值给 _start，以更新 vector 的起始位置。

    • 同时，更新 vector 的结束位置 _endOfStorage 为 _start + n，表示分配的内存空间的末尾位置。将 vector 的实际使用大小 _finish 更新为之前的大小 sz。

    1. //申请内存
    2.   void reserve(size_t n)//返回类型是引用
    3.   {
    4.    if (n > capacity())
    5.    {
    6.     T* tmp = new T[n];
    7.     int sz = size();
    8.  
    9.     if (_start != nullptr)
    10.     {
    11.      for (int i = 0; i < size(); i++)
    12.      {
    13.       tmp[i] = _start[i];
    14.      }
    15.     }
    16.     delete[] _start;
    17.     _start = tmp;
    18.     _endOfStorage = _start + n;
    19.     _finish = _start + sz;
    20.    }
    21.   }

    pop_back函数

    • 在函数实现中，首先利用 assert() 函数对 vector 的大小进行检查，确保 vector 不为空。如果 vector 为空，则会触发断言错误，程序终止运行。

    • 然后将 vector 的 _finish 指针向前移动一位，指向新的最后一个元素。由于 _finish 是指向最后一个元素的下一个位置，因此该操作实际上是将最后一个元素“弹出”了 vector。

    1. //尾删
    2.  
    3.   void pop_back()
    4.   {
    5.    assert(size() >= 0);
    6.    _finish--;
    7.   }

    push_back函数

    • 在函数实现中，首先判断 _finish 是否达到 vector 可用空间的末尾 _endOfStorage。如果是，则表示当前的内存空间已经完全使用，需要进行内存重新分配。

    • 在重新分配内存空间时，调用 reserve() 函数，将 vector 的容量扩展为原来的两倍（或4，如果当前容量为0）。

    • 然后，将新元素 x 赋值给 _finish 所指向的位置，即插入到 vector 的末尾。最后，将 _finish 指针向后移动一位，表示 vector 的大小增加了1。

    1. void push_back(const T& x)
    2.   {
    3.    if (_finish == _endOfStorage)
    4.    {
    5.     reserve(capacity() == 0 ? 4 : 2 * capacity());
    6.    }
    7.    *_finish = x;
    8.    _finish++;
    9.   }

    构造函数

    • vector(InputIterator first, InputIterator last) 构造函数使用迭代器范围 [first, last) 内的元素来初始化 vector。通过循环遍历迭代器范围内的每个元素，并调用 push_back() 函数将其添加到 vector 中。

    • vector(const vector& v)构造函数使用另一个 vector 对象 v 来初始化新创建的 vector 对象。首先通过 reserve() 函数为新 vector 分配与 v 相同大小的内存空间。然后通过循环遍历 v 中的每个元素，并调用 push_back() 函数将其添加到新 vector 中。

    • vector() 默认构造函数创建一个空的 vector 对象，没有分配任何内存空间。所有指针成员 _start、_finish 和 _endOfStorage 都被设置为 nullptr。

    • vector(int n, const T& val = T()) 构造函数创建一个包含 n 个元素的 vector 对象，并使用参数 val 的值进行初始化。通过循环调用 push_back() 函数 n 次，将 val 添加到 vector 中。

    1. //构造函数
    2.   template<class InputIterator>
    3.  
    4.   vector(InputIterator first, InputIterator last)
    5.   {
    6.    while (first != last)
    7.    {
    8.     push_back(*(InputIterator));
    9.     first++;
    10.    }
    11.   }
    12.  
    13.   vector(const vector<T>& v)
    14.    :_start(nullptr)
    15.    , _finish(nullptr)
    16.    , _endOfStorage(nullptr)
    17.   {
    18.    reserve(v.size());
    19.    for (auto i = v.cbegin();i!=v.cend();i++)
    20.    {
    21.     push_back(*i);
    22.    }
    23.   }
    24. vector()
    25.    : _start(nullptr)
    26.    , _finish(nullptr)
    27.    , _endOfStorage(nullptr)
    28.   {}
    29.  
    30.   vector(int n, const T& val = T())
    31.   {
    32.    for (int i = 0; i < n; i++)
    33.    {
    34.     push_back(val);
    35.    }
    36.   }

    swap函数

    • 函数使用 std::swap() 函数来交换 _start、_finish 和 _endOfStorage 指针成员的值。通过调用 std::swap() 函数，将当前 vector 对象的指针成员与参数 v 的对应指针成员进行交换，实现两个 vector 对象之间的内容交换。

    1.   //交换函数
    2.   void swap(vector& v)
    3.   {
    4.    std::swap(_start, v._start);
    5.    std::swap(_finish, v._finish);
    6.    std::swap(_endOfStorage, v._endOfStorage);
    7.   }                                

    =运算符重载

    • 函数创建了一个临时的 vector 对象 tmp，并将参数 v 复制到该对象中。然后通过调用成员函数 swap() 将当前对象和临时对象的内容进行交换，从而实现将当前 vector 对象赋值为参数 v 的操作。

    1.   vector<T>& operator= (vector<T> v)
    2.   {
    3.    vector<int> tmp(v);
    4.    swap(tmp);
    5.   }

    析构函数

    • 析构函数首先使用 delete[] 关键字释放 _start 指针指向的动态分配的数组内存空间。然后将 _start、_finish 和 _endOfStorage 的值设置为 nullptr，以避免悬挂指针的问题。

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

    []运算符重载

    • T& operator[](size_t pos) 是非常规则的重载函数，用于通过下标 pos 访问 vector 中的元素，并返回对应位置的引用。在函数体内部，它直接返回 _start[pos] 的引用，从而允许调用者对该元素进行读写操作。

    • const T& operator[](size_t pos)const 是常规则的重载函数，用于在常量对象上进行下标访问。它与第一个版本的区别在于，在函数声明中加入了 const 限定符，表明该函数不会修改 vector 对象的内容。在函数体内部，它同样返回 _start[pos] 的引用，但由于函数是 const 成员函数，所以返回的引用是常量引用，只能用于读取元素的值，不能进行写操作。

    1.   //[]运算符重载
    2.   T& operator[](size_t pos)
    3.   {
    4.    return _start[pos];
    5.   }
    6.   const T& operator[](size_t pos)const
    7.   {
    8.    return _start[pos];
    9.   }

    insert函数

    • 首先，函数使用 assert() 断言来确保插入位置 pos 在有效范围内，即在 _start 和 _finish 之间（包括 _start 和 _finish）。

    • 然后，函数检查当前 vector 是否已经满了，即 _finish 是否等于 _endOfStorage。如果是满的，则需要进行扩容操作。函数通过调用 reserve() 来扩容，扩容大小为当前容量的两倍。值得注意的是，由于扩容操作可能导致原来的迭代器失效，所以在扩容之前需要记录插入位置 pos 相对于 _start 的偏移量 sz，然后在扩容后重新计算插入位置 pos。

    • 接下来，函数利用迭代器将从 pos 到 _finish-1 的所有元素向后移动一个位置。具体而言，迭代器 en 初始化为 _finish-1，然后循环将 en 指向的元素复制到 en+1 指向的位置，直到 en 等于 pos。

    • 最后，将元素 x 赋值给 pos 指向的位置，增加 _finish 的值，并返回指向插入位置的迭代器 pos。

    1.   //随机插入
    2.   iterator insert(iterator pos, const T& x)
    3.   {
    4.    assert(pos >= _start);
    5.    assert(pos <= _finish);
    6.  
    7.    if (_finish == _endOfStorage)
    8.    {
    9.     int sz = pos - _start;//记录pos与_start的相对位置
    10.     reserve(capacity() == 0 ? 4 : 2 * capacity());//注意迭代器失效
    11.     pos = _start + sz;//重置迭代器
    12.    }
    13.  
    14.    iterator en = _finish-1;
    15.    while (en >= pos)
    16.    {
    17.     *(en+1) = *(en);
    18.     en--;
    19.    }
    20.  
    21.    *pos = x;
    22.    _finish++;
    23.    return pos;
    24.   }

    erase函数

    • 首先，函数使用 assert() 断言来确保删除位置 pos 在有效范围内，即在 _start 和 _finish 之间（包括 _start 和 _finish）。

    • 然后，函数利用迭代器将从 pos+1 到 _finish-1 的所有元素向前移动一个位置。具体而言，迭代器 a 初始化为 pos+1，然后循环将 a 指向的元素复制到 a-1 指向的位置，直到 a 等于 _finish。

    • 最后，将 _finish 减一，并返回指向删除位置的迭代器 pos。需要注意的是，虽然 pos 已经失效了，但是这里返回的仍然是指向原来的位置的迭代器，因为要保证与 STL 标准库的接口兼容。

    1.   iterator erase(iterator pos)
    2.   {
    3.    assert(pos >= _start);
    4.    assert(pos <= _finish);
    5.  
    6.    iterator a = pos+1;
    7.    while (a != _finish)
    8.    {
    9.     *(a-1) = *a;
    10.     a++;
    11.    }
    12.  
    13.    _finish--;
    14.    return pos;
    15.   }
  • 相关阅读:
    怎么压缩ppt大小？快速压缩ppt文件
    【python学习】Day-023 正则表达式
    Spring-Cloud-Openfeign如何支持数据压缩？
    为什么重写equals方法,还必须要重写hashcode方法，重写equals()和hashCode()方法实例
    使用canal解决Mysql和Redis数据同步(TCP)
    [附源码]java毕业设计视屏网站论文
    永远在路上
    95. 最长公共子序列
    Java基础面经1
    perl下mysql同步监控
  • 原文地址：https://blog.csdn.net/ZHENGZJM/article/details/133496848