【C++】STL—容器—vector介绍

分手后的思念是犯贱 2022-11-22 00:12 395阅读 0赞

文章目录

  • 一、vector的介绍
    • 1、概念
    • 2、分配空间策略
    • 3、特点
  • 二、vector的使用
    • 1、vector的定义
    • 2、vector iterator 的使用
    • 3、vector 空间增长
    • 4、vector 增删查改
    • 5、vector 迭代器失效问题
  • 三、vector的模拟实现

一、vector的介绍

1、概念

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

2、分配空间策略

vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

3、特点

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

二、vector的使用

1、vector的定义

  1. void TestVector1()
  2. {
  4.     vector<int> v1;//无参构造
  5.     vector<int> v2(10,5);//构造10个整形5
  7.     int array[] = {
  8.      1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  9.     vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));//构造整个array数组
  11.     vector<int> v5(v3);//拷贝构造
  13.     vector<int> v6{
  14.      1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };//构造整形数组
  15. }

2、vector iterator 的使用

  1. vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));
  2. vector<int>::iterator it = v3.begin();//获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置iterator/const_iterator
  3. while (it != v3.end())
  4. {
  6.     cout << *it << " ";
  7.     ++it;
  8. }
  9. cout << endl;
  11. vector<int> v5(v3);
  13. auto rit = v5.rbegin();//获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator
  14. while (rit != v5.rend())
  15. {
  17.     cout << *rit << " ";
  18.     ++rit;
  19. }
  20. cout << endl;

在这里插入图片描述

3、vector 空间增长

  1. void TestVector2()
  2. {
  4.     vector<int> v{
  5.      1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  6.     cout << v.size() << endl;//获取数据个数
  8.     cout << v.capacity() << endl;//获取容量大小
  10.     if (v.empty())//判断是否为空
  11.     {
  13.         cout << "v empty" << endl;
  14.     }
  15.     else
  16.     {
  18.         cout << "v not empty" << endl;
  19.     }
  20. }
  22.     v.reserve(40);//将容量扩大到40
  24.     v.resize(20, 100);//将数据个数设置为20，不够用100补充

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。

4、vector 增删查改

  1. void TestVector6()
  2. {
  4.     // 注意：push_back和insert在插入元素期间，可能需要扩容
  5.     vector<int> v;
  6.     v.push_back(1);//尾插
  7.     v.push_back(2);
  8.     v.push_back(3);
  9.     v.push_back(4);
  11.     v.pop_back();//尾删
  13.     v.insert(v.begin(), 0);//头部位置插入0
  15.     // 在元素2的位置插入10个值为5的元素
  16.     v.insert(find(v.begin(), v.end(), 2), 10, 5);
  18.     //将数组array中的元素插入到v的尾部
  19.     int array[] = {
  20.      4, 5, 6, 7 };
  21.     v.insert(v.end(), array, array + sizeof(array) / sizeof(array[0]));
  22. }
  24.     vector<int> v1{
  25.      1, 2, 3 };
  26.     vector<int> v2{
  27.      4, 5, 6, 7, 8, 9 };
  28.     v1.swap(v2);//v1和v2交换
  30.     vector<int> v3{
  31.      1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  32.     v3.erase(v3.begin());//头部元素删除
  33.     v3.erase(v3.begin(), v3.begin() + 3);//头部元素开始，后3个元素删除

5、vector 迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

  1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、 push_back等

  2. 指定位置元素的删除操作–erase

    void TestVector11()
    {

    1. vector<int> v{
    2.  1, 2, 3 };
    3. auto it = v.begin();
    5. v.clear();
    6. cout << *it << endl;//迭代器失效
    8. while (it != v.end())
    9. {
    11.     it = v.erase(it);
    12.     it++;//迭代器失效
    13. }

    }

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代 器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

三、vector的模拟实现

  1. #include <assert.h>
  3. namespace bite
  4. {
  6.     template<class T>
  7.     class vector
  8.     {
  10.     public:
  11.         typedef T* iterator;
  12.     public:
  13.         vector()
  14.             : start(nullptr)
  15.             , finish(nullptr)
  16.             , endofstorage(nullptr)
  17.         {
  18.     }
  20.         vector(int n, const T& data = T())
  21.             : start(new T[n])
  22.             , finish(start + n)
  23.             , endofstorage(finish)
  24.         {
  26.             for (int i = 0; i < n; ++i)
  27.             {
  29.                 start[i] = data;
  30.             }
  31.         }
  33.         template<class Iterator>
  34.         vector(Iterator first, Iterator last)
  35.         {
  37.             // 确定该区间中有多少个元素
  38.             Iterator it = first;
  39.             size_t count = 0;
  40.             while (it != last)
  41.             {
  43.                 count++;
  44.                 ++it;
  45.             }
  47.             // 给当前对象开辟空间，并初始化成员变量
  48.             start = new T[count];
  49.             finish = start;
  50.             endofstorage = start + count;
  52.             //赋值
  53.             while (first != last)
  54.             {
  56.                 *finish++ = *first++;
  57.             }
  58.         }
  60.         vector(const vector<T>& v)
  61.         {
  63.             size_t vsize = v.size();
  64.             start = new T[vsize];
  65.             finish = endofstorage = start + vsize;
  66.             for (size_t i = 0; i < vsize; ++i)
  67.                 start[i] = v[i];
  68.         }
  70.         ~vector()
  71.         {
  73.             if (start)
  74.             {
  76.                 delete[] start;
  77.                 start = finish = endofstorage = nullptr;
  78.             }
  79.         }
  81.         iterator begin()
  82.         {
  84.             return start;
  85.         }
  87.         iterator end()
  88.         {
  90.             return finish;
  91.         }
  93.         size_t size()const
  94.         {
  96.             return finish - start;
  97.         }
  99.         size_t capacity()const
  100.         {
  102.             return endofstorage - start;
  103.         }
  105.         bool empty()const
  106.         {
  108.             return start == finish;
  109.         }
  111.         void resize(size_t newsize, const T& data = T())
  112.         {
  114.             size_t oldsize = size();
  115.             if (newsize <= oldsize)
  116.             {
  118.                 finish = start + newsize;
  119.             }
  120.             else
  121.             {
  123.                 if (newsize > capacity())
  124.                     reserve(newsize);
  125.                 for (size_t i = oldsize; i < newsize; ++i)
  126.                     start[i] = data;
  127.                 finish = start + newsize;
  128.             }
  129.         }
  131.         void reserve(size_t newcapacity)
  132.         {
  134.             size_t oldcapacity = capacity();
  135.             size_t oldsize = size();
  136.             if (newcapacity > oldcapacity)
  137.             {
  139.                 // 开辟新空间
  140.                 T* temp = new T[newcapacity];
  142.                 // 拷贝元素
  143.                 for (size_t i = 0; i < oldsize; ++i)
  144.                     temp[i] = start[i];
  146.                 // 释放旧空间
  147.                 delete start;
  149.                 start = temp;
  150.                 finish = start + oldsize;
  151.                 endofstorage = start + newcapacity;
  152.             }
  153.         }
  155.         //acess
  156.         T& operator[](size_t index)
  157.         {
  159.             assert(index < size());
  160.             return start[index];
  161.         }
  163.         const T&operator[](size_t index)const
  164.         {
  166.             assert(index < size());
  167.             return start[index];
  168.         }
  170.         T& front()
  171.         {
  173.             return start[0];
  174.         }
  176.         const T& front()const
  177.         {
  179.             return start[0];
  180.         }
  182.         T& back()
  183.         {
  185.             return start[size() - 1];
  186.         }
  188.         const T& back()const
  189.         {
  191.             return start[size() - 1];
  192.         }
  194.         void push_back(const T& data)
  195.         {
  197.             if (size() == capacity())
  198.                 reserve(capacity() * 2 + 3);
  200.             *finish++ = data;
  201.         }
  203.         void pop_back()
  204.         {
  206.             if (empty())
  207.                 return;
  209.             --finish;
  210.         }
  212.         iterator insert(iterator pos, const T& data)
  213.         {
  215.             assert(pos <= end());
  216.             if (size() == capacity())
  217.                 reserve(capacity() * 2);
  219.             auto it = end();
  220.             while (it > pos)
  221.             {
  223.                 *it = *(it - 1);
  224.                 --it;
  225.             }
  227.             *pos = data;
  228.             ++finish;
  230.             return pos;
  231.         }
  233.         iterator erase(iterator pos)
  234.         {
  236.             assert(pos < end());
  237.             if (size() == 1)
  238.             {
  240.                 pop_back();
  241.                 return end();
  242.             }
  244.             auto it = pos;
  245.             while (it < end())
  246.             {
  248.                 *it = *(it + 1);
  249.                 ++it;
  250.             }
  252.             --finish;
  253.             return pos;
  254.         }
  256.         void clear()
  257.         {
  259.             finish = start;
  260.         }
  262.         void swap(const vector<T>& v)
  263.         {
  265.             std::swap(start, v.start);
  266.             std::swap(finish, v.finish);
  267.             std::swap(endofstorage, v.endofstorage);
  268.         }
  269.     private:
  270.         iterator start;
  271.         iterator finish;
  272.         iterator endofstorage;
  273.     };
  274. }
  276. #include <iostream>
  277. using namespace std;
  279. #include <string>
  281. void TestMyvector1()
  282. {
  284.     bite::vector<int> v1;
  285.     bite::vector<int> v2(10, 5);
  287.     for (size_t i = 0; i < v2.size(); ++i)
  288.         cout << v2[i] << " ";
  289.     cout << endl;
  291.     int array[] = {
  292.      1, 2, 3, 4, 5 };
  293.     bite::vector<int> v3(array, array + 5);
  294.     auto it = v3.begin();
  295.     while (it!=v3.end())
  296.     {
  298.         cout << *it << " ";
  299.         ++it;
  300.     }
  301.     cout << endl;
  303.     std::string s("hello");
  304.     bite::vector<char> vc(s.begin(), s.end());
  305.     bite::vector<int> v4(v3);
  306.     for (auto e : v4)
  307.         cout << e << " ";
  308.     cout << endl;
  309. }
  311. void TestMyvector2()
  312. {
  314.     bite::vector<int> v;
  315.     v.push_back(1);
  316.     v.push_back(2);
  317.     v.push_back(3);
  318.     v.push_back(4);
  320.     for (auto e : v)
  321.         cout << e << " ";
  322.     cout << endl;
  324.     v.pop_back();
  325.     v.pop_back();
  327.     for (auto e : v)
  328.         cout << e << " ";
  329.     cout << endl;
  331.     v.insert(v.begin(), 0);
  332.     for (auto e : v)
  333.         cout << e << " ";
  334.     cout << endl;
  336.     v.erase(v.begin());
  337.     for (auto e : v)
  338.         cout << e << " ";
  339.     cout << endl;
  341.     v.clear();
  342.     cout << v.size() << endl;
  343.     cout << v.capacity() << endl;
  344. }
  346. void TestMyvector3()
  347. {
  349.     bite::vector<int> v;
  350.     v.push_back(1);
  351.     v.push_back(2);
  352.     v.push_back(3);
  353.     v.push_back(4);
  355.     cout << v[0] << endl;
  356.     cout << v.front() << endl;
  357.     cout << v.back() <<endl;
  359.     v.resize(8, 5);
  360.     cout << v.size() << endl;
  361.     cout << v.capacity() << endl;
  362.     for (auto e : v)
  363.     {
  365.         cout << e << " ";
  366.     }
  367.     cout << endl;
  369.     v.resize(15, 6);
  370.     cout << v.size() << endl;
  371.     cout << v.capacity() << endl;
  372.     for (auto e : v)
  373.     {
  375.         cout << e << " ";
  376.     }
  377.     cout << endl;
  379.     v.resize(20, 6);
  380.     cout << v.size() << endl;
  381.     cout << v.capacity() << endl;
  382.     for (auto e : v)
  383.     {
  385.         cout << e << " ";
  386.     }
  387.     cout << endl;
  389.     v.resize(12);
  390.     cout << v.size() << endl;
  391.     cout << v.capacity() << endl;
  392.     for (auto e : v)
  393.     {
  395.         cout << e << " ";
  396.     }
  397.     cout << endl;
  399.     v.resize(5);
  400.     cout << v.size() << endl;
  401.     cout << v.capacity() << endl;
  402.     for (auto e : v)
  403.     {
  405.         cout << e << " ";
  406.     }
  407.     cout << endl;
  408. }

发表评论

表情：
评论列表 （有 0 条评论，395人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Vector容器

    Vector 容器 一、 简介 vector 是将元素置于一个动态数组中加以管理的容器 vector可以随机存取元素（支持索引值直接存取，用\[\]操作符或at()函数）

    Love The Way You LieLove The Way You Lie/ 0 赞/ 179 阅读

    相关 Vector容器

    一、vector容器。 1、vector容器基本概念。 1）功能： vector容器数据结构与数组非常相似，也称为单端数组。 2）vector与普通数组区别？

    我不是女神ヾ我不是女神ヾ/ 0 赞/ 290 阅读

    相关 c++容器vector介绍

    vector简介     vector是STL中最常见的容器，它是一种顺序容器，支持随机访问。vector是一块连续分配的内存，从数据安排的角度来讲，和数组极其相似，不同的地

    我会带着你远行我会带着你远行/ 0 赞/ 397 阅读

    相关 Vector介绍

    C++ Vector （向量容器） 是一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作

    ╰半夏微凉°╰半夏微凉°/ 0 赞/ 488 阅读