• C++笔记 - - STL vector容器的使用和模拟实现

    1.vector是什么？

    1. vector是STL中表示可变大小数组的序列容器。
    2. 和数组一样，vector也可以使用下表访问，因为采用连续的空间存储。vector的大小还可以动态增长，并且由容器自动管理。
    3. 本质上，vector使用动态分配数组来存储元素，插入一个新的元素时，这个数组需要重新分配大小为了增加存储空间。其做法是，每插入一个元素，都会申请一个新的数组，将数据移到这个新的数组，时间代价相对高 ，所以每次有元素要插入时，vector不会每次都重新分配大小。
    4. vector分配空间的策略实际并不会只开实际需要的大小，而是会分配一些额外的空间以适应可能的增长。不同的库采用不同的策略来进行空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小来进行，以至于在尾部插入数据是在常数时间内完成的
    5. 因此，vector占用的更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长

    2.vector的使用 

    2.1 vector 的constructor(构造函数)

    1. 无参的构造函数 ：vector();
    2. 构造并初始化n个value : vector(size_type n,const value_type& val =value_type());         //value_type实际就是模板的参数T
    3. 拷贝构造函数 ： vector(const vector& x);
    4. 迭代器区间进行构造：vector(Inputlterator first,Inputlteratorl last);

           

    1. vector<int> v1;//无参构造
    2.   8   vector<int> v2(5,55);//构造有5个55的vector
    3.   9   vector<int> v3(v2);//拷贝构造
    4.  10   vector<int> v4(v3.begin(),v3.end());//迭代器区间构造

    2.2 vector iterator的使用

    1. begin()/end()  获取第一个数据位置的iterator/const_iterator，获取最后一个位置下一个的iterator/const_iterator

    2. rbegin()/rend()   获取最后一个数据位置的iterator/const_iterator，获取第一个位置前一个的iterator/const_iterator

    1.  vector<int>:: iterator it1 = v2.begin();
    2.  32   while(it1!=v2.end())
    3.  33   {
    4.  34     cout << *it1 << " ";
    5.  35     it1++;
    6.  36   }
    7.  37   cout << endl;
    8.  38   const vector<int> v5;
    9.  39   vector<int>::const_iterator it2 = v5.begin();
    10.  40   while(it2!=v5.end())
    11.  41   {
    12.  42     cout << *it2 << " ";                                                                                                                                                                                     
    13.  43     it2++;
    14.  44   }
    15.  45   cout << endl;
    16.  46   vector<int>:: reverse_iterator it3 = v2.rbegin();
    17.  47   while(it3!=v2.rend())
    18.  48   {
    19.  49     cout << *it3 << " ";
    20.  50     it3++;
    21.  51   }
    22.  52   cout << endl;
    23.  53   const vector<int> v6;
    24.  54   vector<int>::const_reverse_iterator it4 = v6.rbegin();
    25.  55   while(it4!=v6.rend())
    26.  56   {
    27.  57     cout << *it4 << " ";
    28.  58     it4++;
    29.  59   }
    30.  60   cout << endl;

     

     2.3 vector  空间增长

    1. size：获取数据个数
    2. capcacity：获取容量大小       
    3. empty：判断是否为空
    4. reserve：改变vector的capacity                    //reserve只负责开辟空间，如果事先知道要用多少空间，可以避免vector的扩容问题
    5. resize：改变vector的size                             //resize在开辟空间是还会初始化，影响size

         

    1. cout << v2.size() << endl;                                       
    2. cout << v2.capacity() << endl;                                 
    3. cout << v2.empty() << endl;                             
    4. v2.reserve(100);
    5. cout << v2.size() << endl;
    6. cout << v2.capacity() << endl;
    7. v2.resize(10,6);
    8. cout << v2.size() << endl;                                                                                                                                                                                 
    9. cout << v2.capacity() << endl;

    2.4 vector 增删查改

    1. push_back：尾插
    2. pop_back：尾删
    3. insert：在position的位置之前插入数据
    4. erase：删除position位置的数据
    5. operator[]：像数组一样访问
    6. swap：交换两个vector的数据空间

    1.   vector<int> vec;
    2.     vec.push_back(1);                                  
    3.     vec.push_back(2);                 
    4.     vec.push_back(3);      
    5.     vec.pop_back();                       
    6.     vec.insert(vec.end(),10);
    7.     vec.insert(vec.end(),20);
    8.     vec.insert(vec.end(),30);                                        
    9.     vec.erase(vec.begin());                                        
    10.     for(size_t i=0;isize();i++)                        
    11.     {                                   
    12.       cout << vec[i] << " ";                                                                                                                                                                                   
    13.     }                                           
    14.     cout << endl;

    3.vector 的模拟实现

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. namespace hj
    7. {
    8.   template<class T>//创建一个模板类vector
    9.     class vector{
    10.       public:
    11.         typedef T* iterator;//迭代器
    12.         typedef const T* const_iterator;
    13.         iterator begin()
    14.         {
    15.           return _start;
    16.         }
    17.         iterator end()
    18.         {
    19.           return _finish;
    20.         }
    21.         const_iterator begin()const
    22.         {
    23.           return _start;
    24.         }
    25.         const_iterator end()const
    26.         {
    27.           return _finish;
    28.         }
    29.  
    30.         //构造
    31.         vector()
    32.           :_start(nullptr),
    33.           _finish(nullptr),
    34.           _en_of_storage(nullptr)
    35.         {}
    36.         //析构
    37.         ~vector()
    38.         {
    39.           delete[] _start;
    40.           _start = _finish = _en_of_storage;
    41.         }
    42.         //迭代器区间构造
    43.         template <class InputIterator>
    44.               vector(InputIterator first, InputIterator last)
    45.                 :_start(nullptr),
    46.                 _finish(nullptr),
    47.                 _en_of_storage(nullptr)
    48.               {
    49.                 
    50.                 while(first != last)
    51.                 {
    52.                   push_back(*first);
    53.                   ++first;
    54.                 }
    55.               }
    56.        void swap(vector& v)//交换两个vector的值
    57.         {
    58.           std::swap(v._start,_start);
    59.           std::swap(v._finish,_finish);
    60.           std::swap(v._en_of_storage,_en_of_storage);
    61.         }
    62.         //拷贝构造-深拷贝
    63.         vector(const vector& v)
    64.           :_start(nullptr),
    65.           _finish(nullptr),
    66.           _en_of_storage(nullptr)
    67.         {
    68.           vector tmp(v.begin(),v.end());
    69.           swap(tmp);
    70.         }
    71.         //赋值重载
    72.         vector& operator=(vector v)
    73.         {
    74.           swap(v);
    75.           return *this;
    76.         }
    77.         size_t size()
    78.         {
    79.           return _finish - _start;
    80.         }
    81.         size_t capacity()
    82.         {
    83.           return _en_of_storage - _start;
    84.         }
    85.         void reserve(size_t n)//扩容
    86.         {
    87.           if(n > capacity())
    88.           {
    89.             size_t len = size();
    90.             T* tmp = new T[n];
    91.             if(_start)//判断是否为空
    92.             {
    93.  
    94.               for(size_t i = 0;i < len; i++)//拷贝数据
    95.               {
    96.                 tmp[i] = _start[i];
    97.               }
    98.               delete[] _start;
    99.             }
    100.             _start = tmp;
    101.             _finish = _start + len;
    102.             _en_of_storage = _start + n;
    103.           }
    104.         }
    105.         void resize(size_t n,T& val=T())//设置有效数据个数
    106.         {
    107.           if(n>capacity())//扩容
    108.           {
    109.             reserve(n);
    110.           }
    111.           if(n>size())
    112.           {
    113.             while(_finish < _start + n)
    114.             {
    115.               *_finish = val;
    116.               ++_finish;
    117.             }
    118.           }
    119.           else
    120.           {
    121.             _finish = _start + n;
    122.           }
    123.         }
    124.         void push_back(const T& val)
    125.         {
    126.           insert(_finish,val);
    127.         }
    128.         void pop_back()
    129.         {
    130.           erase(_finish-1);
    131.         }
    132.         iterator insert(iterator pos,const T& val)
    133.         {
    134.           assert(pos >=_start);
    135.           assert(pos <=_finish);
    136.           if(_finish == _en_of_storage)//判断扩容
    137.           {
    138.             size_t len = pos - _start;
    139.             reserve(capacity()==0?4:capacity()*2);
    140.             pos = _start + len;//更新扩容后pos的位置
    141.           }
    142.           iterator end = _finish-1;
    143.           while(end >= pos)
    144.           {
    145.             *(end+1) = *(end);//用end = end-1在pos为_start时会越界
    146.             end--;
    147.           }
    148.           *pos = val;
    149.           _finish++;
    150.           return pos;
    151.         }
    152.  
    153.         iterator erase(iterator pos)
    154.         {
    155.           assert(pos >= _start);
    156.           assert(pos < _finish);
    157.           iterator begin = pos+1;
    158.           while(begin < _finish)
    159.           {
    160.             *(begin-1) = *begin;
    161.             begin++;
    162.           }
    163.           _finish--;
    164.           return pos;
    165.         }
    166.         T& operator[](size_t sz)
    167.         {
    168.           assert(sz < size());
    169.           return *(_start + sz);
    170.         }
    171.         const T& operator[](size_t sz)const
    172.         {
    173.           assert(sz < size());
    174.           return *(_start + sz);
    175.         }
    176.  
    177.         T& front()
    178.         {
    179.           assert(size()>0);
    180.           return *_start;
    181.         }
    182.         T& back()
    183.         {
    184.           assert(size()>0);
    185.           return *(_finish-1);
    186.         }
    187.       private:
    188.         iterator _start;
    189.         iterator _finish;
    190.         iterator _en_of_storage;
    191.     };
    192.   void test_vector1()//测试基本功能
    193.   {
    194.     vector<int> v1;//构造
    195.     v1.push_back(1);
    196.     v1.push_back(2);
    197.     v1.push_back(3);
    198.     v1.push_back(4);
    199.     v1.push_back(5);
    200.     vector<int> v2(v1);//拷贝构造
    201.     for(auto ch : v1)//迭代器
    202.     {
    203.       cout << ch << " ";
    204.     }
    205.     cout << endl;
    206.     for(auto ch : v2)
    207.     {
    208.       cout << ch << " ";
    209.     }
    210.     cout << endl;
    211.     for(size_t i=0;isize();i++)//[]重载
    212.     {
    213.       cout << v1[i] << " ";
    214.     }
    215.     cout << endl;
    216.     vector<int> v3;
    217.     v3=v1;//赋值重载
    218.  
    219.     for(auto ch : v3)
    220.     {
    221.       cout << ch << " ";
    222.     }
    223.     cout << endl;
    224.  
    225.     v3.erase(v3.begin());//删除
    226.     v3.erase(v3.end()-1);
    227.     for(auto ch : v3)
    228.     {
    229.       cout << ch << " ";
    230.     }
    231.     cout << endl;
    232.  
    233.     cout<< "size->"<size()<
    234.     cout<< "capacity->"<capacity()<
    235.  
    236.  
    237.   }
    238. }

  • 相关阅读:
    【Vue】06 计算属性 侦听属性
    城市物流管理系统的设计与实现
    C++拿几道题练练手吧
    python笔记（input、print、多重判断、两个循环（九九乘法表））
    【JavaSE】基础笔记 - 类和对象（下）
    408计网应用层总结
    解决 Android 依赖冲突
    2022面试笔记
    MySQL8.0安装教程，在Linux环境安装MySQL8.0教程，最新教程 超详细
    LeetCode 141. 环形链表
  • 原文地址：https://blog.csdn.net/qq_64105689/article/details/126913435