• C++ Vector的模拟实现

    vector的介绍
    1. vector是表示可变大小数组的序列容器。
    2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
    3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
    4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
    5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
    6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

    参考侯捷老师《STL源码刨析》这本书画的：

    Vector的一些接口：

    1. namespace MyVector
    2. {
    3. 	template<class T>
    4.     class vector
    5.     {
    6.              
    7.         public:
    8.  
    9.         // Vector的迭代器是一个原生指针
    10.  
    11.         typedef T* iterator;
    12.         typedef const T* const_iterator;
    13.  
    14.         iterator begin();
    15.         iterator end();
    16.         
    17.         const_iterator cbegin() const;
    18.         const_iterator cend() const;   
    19.  
    20.         // 初始化
    21.         vector();
    22.         // 析构
    23.         ~vector();
    24.  
    25.         vector(int n, const T& value = T());
    26.         vector(size_t n, const T& val = T());
    27.  
    28.         //类模板的成员函数可以是函数模板
    29.         template<class InputIterator>
    30.         vector(InputIterator first, InputIterator last);
    31.  
    32.         vector(const vector& v);
    33.         vector& operator= (vector v);
    34.         
    35.         size_t size() const;
    36.         size_t capacity() const;
    37.  
    38.         void reserve(size_t n);
    39.         void resize(size_t n, const T& value = T());
    40.         
    41.         T& operator[](size_t pos);
    42.         const T& operator[](size_t pos)const;
    43.         
    44.         bool empty();
    45.         void push_back(const T& x);
    46.         void pop_back();
    47.  
    48.         void swap(vector& v);
    49.     
    50.         iterator insert(iterator pos, const T& x);
    51.         iterator erase(iterator pos);
    52.  
    53.         private:
    54.  
    55.         iterator _start = nullptr; // 指向数据块的开始
    56.  
    57.         iterator _finish = nullptr; // 指向有效数据的尾
    58.  
    59.         iterator _endOfStorage = nullptr;// 指向存储容量的尾
    60.  
    61.     };
    62. }

    iterator begin()

    1.         iterator begin()
    2.         {
    3.             return _start;
    4.         }

    iterator end()

    1.         iterator end()
    2.         {
    3.             return _finish;
    4.         }

    const_iterator cbegin()

    1.         const_iterator cbegin()
    2.         {
    3.             return _start;
    4.         }

    const_iterator cend() const

    1.         const_iterator cend() const
    2.         {
    3.             return _finish;
    4.         }

    四个比较简单的迭代器

    vector()

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

    ~vector()

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

    初始化与析构

    1.         //类模板的成员函数可以是函数模板
    2.         template<class InputIterator> // InputIterator定义的一个迭代器类型
    3.  
    4.         vector(InputIterator first, InputIterator last)
    5.             :_start(nullptr)
    6.             , _finish(nullptr)
    7.             , _endOfStorage(nullptr)
    8.         {
    9.             while (first != last)
    10.             {
    11.                 push_back(*first);
    12.                 ++first;
    13.             }
    14.         }

    vector& operator= (vector v)

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

            // v1 = v3

    size_t size() const

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

            // 有效数据的尾减去数据块的开始就是元素个数

    size_t capacity() const

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

            // 开辟空间的容量

    void reserve(size_t n)

    1.         void reserve(size_t n)
    2.         {
    3.             if (n > capacity())
    4.             {
    5.                 T* tmp = new T[n];
    6.                 size_t old_size = size();
    7.                 for (size_t i = 0; i < old_size; i++)
    8.                 {
    9.                     tmp[i] = _start[i]; // 深拷贝
    10.  
    11.                 }
    12.                 delete[] _start;
    13.  
    14.                 _start = tmp; // 老的_start已经失效，更新一下
    15.                 _finish = tmp + old_size;
    16.                 _endOfStorage = tmp + n;
    17.             }
    18.         }

    void resize(size_t n, const T& value = T())

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

    vector(const vector& v)

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

            // v2(v1) 用已经存在的 v1 去初始化 v2

    T& operator[](size_t pos)

    const T& operator[](size_t pos)const

    1.         T& operator[](size_t pos)
    2.         {
    3.             assert(pos < size()); // 保证下标为有效数据
    4.             return _start[pos];
    5.         }
    6.  
    7.         const T& operator[](size_t pos)const
    8.         {
    9.             assert(pos < size());
    10.             return _start[pos];
    11.         }

    iterator insert(iterator pos, const T& x)

    1.         iterator insert(iterator pos, const T& x)
    2.         {
    3.             assert(pos >= _start);
    4.             assert(pos <= _finish);
    5.             if (_finish == _endOfStorage)
    6.             {
    7.                 size_t len = pos - _start;
    8.                 reserve(capacity() == 0 ? 4 : 2 * capacity());
    9.  
    10.                 //如果扩容了要更新pos
    11.                 pos = _start + len;
    12.             }
    13.             iterator it = _finish - 1;
    14.             while (it >= pos)
    15.             {
    16.                 *(it + 1) = *it;
    17.                 --it;
    18.             }
    19.             *pos = x;
    20.             ++_finish;
    21.         }

    iterator erase(iterator pos)

    1.         iterator erase(iterator pos)
    2.         {
    3.             assert(pos >= _start);
    4.             assert(pos <= _finish);
    5.             iterator it = pos + 1;
    6.             while (it < _finish)
    7.             {
    8.                 *(it - 1) = *it;
    9.                 --it;
    10.             }
    11.             --_finish;
    12.             return pos;
    13.         }

    vector(int n, const T& value = T())

    1.         vector(int n, const T& value = T())
    2.         {
    3.             reserve(n);
    4.             for (size_t i = 0; i < n; i++)
    5.             {
    6.                 push_back(value);
    7.             }
    8.         }

    vector(size_t n, const T& val = T())

    1.         vector(size_t n, const T& val = T())
    2.         {
    3.             reserve(n);
    4.             for (size_t i = 0; i < n; i++)
    5.             {
    6.                 push_back(val);
    7.             }
    8.         }

    bool empty()

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

    void push_back(const T& x)

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

    void pop_back()

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

    void swap(vector& v)

    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. #pragma once
    2.  
    3. #include 
    4.  
    5. namespace bit
    6. {
    7. 	template<class T>
    8.     class vector
    9.  
    10.     {
    11.  
    12.     public:
    13.  
    14.         // Vector的迭代器是一个原生指针
    15.  
    16.         typedef T* iterator;
    17.  
    18.         typedef const T* const_iterator;
    19.  
    20.         iterator begin()
    21.         {
    22.             return _start;
    23.         }
    24.  
    25.         iterator end()
    26.         {
    27.             return _finish;
    28.         }
    29.  
    30.         const_iterator cbegin()
    31.         {
    32.             return _start;
    33.         }
    34.  
    35.         const_iterator cend() const
    36.         {
    37.             return _finish;
    38.         }
    39.  
    40.  
    41.         // construct and destroy
    42.  
    43.         vector()
    44.             :_start(nullptr)
    45.             ,_finish(nullptr)
    46.             , _endOfStorage(nullptr)
    47.         {}
    48.  
    49.         vector(int n, const T& value = T())
    50.         {
    51.             reserve(n);
    52.             for (size_t i = 0; i < n; i++)
    53.             {
    54.                 push_back(value);
    55.             }
    56.         }
    57.  
    58.         vector(size_t n, const T& val = T())
    59.         {
    60.             reserve(n);
    61.             for (size_t i = 0; i < n; i++)
    62.             {
    63.                 push_back(val);
    64.             }
    65.         }
    66.  
    67.  
    68.         //类模板的成员函数可以是函数模板
    69.         template<class InputIterator>
    71.         vector(InputIterator first, InputIterator last)
    72.             :_start(nullptr)
    73.             , _finish(nullptr)
    74.             , _endOfStorage(nullptr)
    75.         {
    76.             while (first != last)
    77.             {
    78.                 push_back(*first);
    79.                 ++first;
    80.             }
    81.         }
    82.  
    83.  
    84.         vector(const vector& v)
    85.         {
    86.             reserve(v.capacity());
    87.             for (auto& e : v)
    88.             {
    89.                 push_back(e);
    90.             }
    91.         }
    92.  
    93.         vector& operator= (vector v)
    94.         {
    95.             swap(v);
    96.             return *this;
    97.         }
    98.  
    99.         ~vector()
    100.         {
    101.             delete[] _start;
    102.             _start = _finish = _endOfStorage;
    103.         }
    104.  
    105.  
    106.         size_t size() const
    107.         {
    108.             return _finish - _start;
    109.         }
    110.  
    111.         size_t capacity() const
    112.         {
    113.             return _endOfStorage - _start;
    114.         }
    115.  
    116.         void reserve(size_t n)
    117.         {
    118.             if (n > capacity())
    119.             {
    120.                 T* tmp = new T[n];
    121.                 size_t old_size = size();
    122.                 for (size_t i = 0; i < old_size; i++)
    123.                 {
    124.                     tmp[i] = _start[i];
    125.  
    126.                 }
    127.                 delete[] _start;
    128.  
    129.                 _start = tmp;
    130.                 _finish = tmp + old_size;
    131.                 _endOfStorage = tmp + n;
    132.             }
    133.         }
    134.  
    135.         void resize(size_t n, const T& value = T())
    136.         {
    137.             if (n > size())
    138.             {
    139.                 reserve(n);
    140.                 while (_finish < _start + n)
    141.                 {
    142.                     *_finish = value;
    143.                     ++_finish;
    144.                 }
    145.             }
    146.             else
    147.             {
    148.                 _finish = _start + n;
    149.             }
    150.         }
    151.  
    152.  
    153.  
    154.  
    155.  
    156.         T& operator[](size_t pos)
    157.         {
    158.             assert(pos < size());
    159.             return _start[pos];
    160.         }
    161.  
    162.         const T& operator[](size_t pos)const
    163.         {
    164.             assert(pos < size());
    165.             return _start[pos];
    166.         }
    167.  
    168.  
    169.  
    170.         bool empty()
    171.         {
    172.             return _start == _finish;
    173.         }
    174.  
    175.         void push_back(const T& x)
    176.         {
    177.             insert(end(), x);
    178.         }
    179.  
    180.         void pop_back()
    181.         {
    182.             erase(end() - 1);
    183.         }
    184.  
    185.  
    186.         void swap(vector& v)
    187.         {
    188.             std::swap(_start, v._start);
    189.             std::swap(_finish, v._finish);
    190.             std::swap(_endOfStorage, v._endOfStorage);
    191.         }
    192.  
    193.         iterator insert(iterator pos, const T& x)
    194.         {
    195.             assert(pos >= _start);
    196.             assert(pos <= _finish);
    197.             if (_finish == _endOfStorage)
    198.             {
    199.                 size_t len = pos - _start;
    200.                 reserve(capacity() == 0 ? 4 : 2 * capacity());
    201.  
    202.                 //如果扩容了要更新pos
    203.                 pos = _start + len;
    204.             }
    205.             iterator it = _finish - 1;
    206.             while (it >= pos)
    207.             {
    208.                 *(it + 1) = *it;
    209.                 --it;
    210.             }
    211.             *pos = x;
    212.             ++_finish;
    213.         }
    214.  
    215.         iterator erase(iterator pos)
    216.         {
    217.             assert(pos >= _start);
    218.             assert(pos <= _finish);
    219.             iterator it = pos + 1;
    220.             while (it < _finish)
    221.             {
    222.                 *(it - 1) = *it;
    223.                 --it;
    224.             }
    225.             --_finish;
    226.             return pos;
    227.         }
    228.  
    229.     private:
    230.  
    231.         iterator _start = nullptr; // 指向数据块的开始
    232.  
    233.         iterator _finish = nullptr; // 指向有效数据的尾
    234.  
    235.         iterator _endOfStorage = nullptr;// 指向存储容量的尾
    236.  
    237.     };
    238.  
    239. }

    测试代码：

    1. #include 
    2. #include
    3. #include
    4.  
    5. #include "Vector.h"
    6.  
    7. using namespace std;
    8.  
    9. int main()
    10. {
    11. 	vector<int> v;
    12. 	v.push_back(1);
    13. 	v.push_back(2);
    14. 	v.push_back(3);
    15. 	v.push_back(4);
    16. 	v.push_back(5);
    17. 	cout << v.size() << endl;
    18. 	cout << v.capacity() << endl;
    19. 	for (size_t i = 0; i < v.size(); i++)
    20. 	{
    21. 		cout << v[i] << " ";
    22. 	}
    23. 	cout << endl;
    24.  
    25. 	for (auto e : v)
    26. 	{
    27. 		cout << e << " ";
    28. 	}
    29. 	cout << endl;
    30.  
    31. 	v.reserve(30);
    32. 	cout << v.capacity() << endl;
    33. 	vector<int>::iterator it = v.begin();
    34. 	while (it != v.end())
    35. 	{
    36. 		cout << *it << " ";
    37. 		++it;
    38. 	}
    39. 	cout << endl;
    40.  
    41. 	vector<int> v1(v);
    42. 	v1.push_back(100);
    43. 	v1.push_back(200);
    44. 	v1.pop_back();
    45. 	for (auto e : v1)
    46. 	{
    47. 		cout << e << " ";
    48. 	}
    49. }

  • 相关阅读:
    中兴通讯5G为何要开拓第二曲线业务？一切都是为了得到更好的发展！
    中科创达怎么样-是外包公司吗-智能网联汽车和智能物联网推动业务快速增长
    LeetCode_单调栈_中等_456.132 模式
    含冰蓄冷空调的冷热电联供型微网多时间尺度优化调度
    11月19日绿健简报，星期六，农历十月廿六
    阅读JavaScript文档-一些常用方法
    Leetcode 104. 二叉树的最大深度
    48页智慧城市规划蓝图 解决方案
    安全算法 - 国密算法
    解释一下前端框架中的虚拟DOM（virtual DOM）和实际DOM（real DOM）之间的关系。
  • 原文地址：https://blog.csdn.net/qq_73874574/article/details/139888695