AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++】Vector -- 详解（上）

2024-05-21 51
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++】Vector -- 详解（上）

一、vector的介绍及使用

1、vector的介绍

https://cplusplus.com/reference/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 统一的迭代器和引用更好。

2、vector的使用

（1）vector的定义

https://cplusplus.com/reference/vector/vector/vector/

  • default(1)

这里给的是一个缺省值，目前只要看到 alloc 就可以直接忽略它，它是 STL 六大组件中的空间配置器。

  • fill(2)

value_type 是第一个模板参数，它是一个 ‘\0’ 。

 

  • range(3)

这里的迭代器还是一个函数模板，也就是说这里的迭代器不一定是 vector 的迭代器。

// vector的构造
int TestV1()
{
  // constructors used in the same order as described above:
  vector<int> first;                                // empty vector of ints
  vector<int> second(4, 100);                       // 4 ints with value 100
  vector<int> third(second.begin(), second.end());  // iterating through second
  vector<int> fourth(third);                        // a copy of third
 
    // 迭代器构造函数也可以使用数组来进行构造，传的区间是左闭右开
    // 因为指向数组空间的指针是天然的迭代器
  int myints[] = {16, 2, 77, 29};
    vector<int> fifth (arr, arr + 4 );
  //vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
 
  cout << "The contents of fifth are:";
  for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
  {
    cout << ' ' << *it;
  }   
  cout << '\n';
 
  return 0;
}

（2）vector iterator 的使用

// vector的迭代器
void PrintVecotr(const vector<int>& v)
{
  // const对象使用const迭代器进行遍历打印
  vector<int>::const_iterator it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}
 
void TestV2()
{
  // 使用push_back插入4个数据
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
 
  // 使用迭代器进行遍历打印
  vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
 
  // 使用迭代器进行修改
  it = v.begin();
  while (it != v.end())
  {
    *it *= 2;
    ++it;
  }
 
  // 使用反向迭代器进行遍历再打印
  // vector<int>::reverse_iterator rit = v.rbegin();
  auto rit = v.rbegin();
  while (rit != v.rend())
  {
    cout << *rit << " ";
    ++rit;
  }
  cout << endl;
 
  PrintVector(v);
}

（3） vector 空间增长问题

cplusplus.com/reference/vector/vector/reserve/

cplusplus.com/reference/vector/vector/resize/

  • reserve 只负责开辟空间，如果确定知道需要用多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。
  • resize 在开空间的同时还会进行初始化，影响 size 。 
void test()
{
  vector<int> v;
  v.reserve(10); // 有效元素个数size=0，只是开了空间capacity=10
  
    /* error
    for (size_t i = 0; i < 10; i++)
  {
    v[i] = i; // 违规访问
  }
  */
    
    // 正确做法
    for (size_t i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
}

如果不断往 vector 中尾插数据，容器会随着数据的增多而发生扩容，通过验证发现：VS 下 capacity 是按 1.5 倍增长的，G++ 是按 2 倍增长的。这个问题经常会考察，不要固化的认为，vector 增容都是 2 倍，具体增长多少是根据具体的需求定义的。VS 是 PJ 版本 STL，G++ 是 SGI 版本 STL。  

// vector的resize和reserve
// reisze(size_t n, const T& data = T())
// 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
// 注意：resize在增多元素个数时可能会扩容
void TestV3()
{
  vector<int> v;
 
  // set some initial content:
  for (int i = 1; i < 10; i++)
    v.push_back(i);
 
  v.resize(5);
  v.resize(8, 100);
  v.resize(12);
 
  cout << "v contains:";
  for (size_t i = 0; i < v.size(); i++)
    cout << ' ' << v[i];
  cout << '\n';
}

// 测试vector的默认扩容机制
// VS：按照1.5倍方式扩容
// Linux：按照2倍方式扩容
void TestVectorExpand()
{
  size_t sz;
  vector<int> v;
  sz = v.capacity();
  cout << "making v grow:\n";
  for (int i = 0; i < 100; ++i)
  {
    v.push_back(i);
    if (sz != v.capacity())
    {
      sz = v.capacity();
      cout << "capacity changed: " << sz << '\n';
    }
  }
}

VS2019： 

g++运行结果：linux下使用的STL基本是按照2倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128
（4）vector 增删查改

迭代器 的主要作用：让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T* 。

因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。

⚪对于 vector 可能会导致其迭代器失效的操作有：
a. 会引起其底层空间改变的操作，都有可能是迭代器失效。

比如：resize、reserve、insert、assign、push_back 等。

两种导致迭代器失效的操作： 

// 指定位置之前插入元素操作–insert
void TestV4()
{
  // 迭代器失效问题 -- 类似野指针问题
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
 
  vector<int>::iterator pos = find(v.begin(), v.end(), 2);
  if (pos != v.end())
  {
    v.insert(pos, 20); // 在pos之前插入20
        
        /*
        * 如果想要继续通过迭代器操作vector中的元素，需要给pos重新赋值
        * 即 pos = v.insert(pos, 20); // 函数返回指向新插入元素的迭代器
        */
  }
 
  // 在insert之后，pos迭代器位置就失效了，不能再去访问了--insert时增容导致的
  //cout << *pos << endl;
  //*pos = 200;
}

运行结果：

  • VS2019 下验证，程序崩溃。
  • Linux 下验证，虽然没有崩溃（和具体实现、增容机制以及检查机制有关），但也认为失效了。

void TestV5()
{
  // 迭代器失效问题 -- 类似野指针问题
  vector<int> v;
 
  v.reserve(5); // 提前开好空间，防止后续插入元素时发生扩容
 
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
 
  vector<int>::iterator pos = find(v.begin(), v.end(), 2); // 在2之前插入20,如果没有则不插入
  if (pos != v.end())
  {
    v.insert(pos, 20); // 在pos之前插入20
        
        /*
        * 如果想要继续通过迭代器操作vector中的元素，需要给pos重新赋值
        * 即 pos = v.insert(pos, 20); // 函数返回指向新插入元素的迭代器
        */
  }
  // 在insert时空间足够，没有增容，但我们依旧认为pos迭代器位置失效了，不能再去访问了
    // 这里的失效是指pos位置的意义变了，pos不再指向原来的值
  //cout << *pos << endl;
  //*pos = 200;
}

运行结果：

  • VS2019 下验证，程序崩溃（VS 会进行检查）。
  • Linux 下验证，虽然没有崩溃（和具体实现、检查机制有关），但也认为失效了。

【总结】

指定位置之前插入元素操作（insert）导致迭代器失效的两种场景：

  1. insert 插入元素时增容，pos 还指向已被释放的空间（非法空间），所以 pos 位置迭代器失效。
  2. insert 插入元素时没有增容，但 pos 位置意义变了，不再指向原来的值，所以 pos 位置迭代器失效。

vector 插入元素过程中可能会发生扩容，挪动数据，因此当前迭代器和后面所有元素的迭代器都失效。失效后，我们都不要去访问 pos 位置，否则可能出现各种意外情况。

b. 指定位置元素的删除操作 -- erase

// 任意位置插入：insert和erase，以及查找find
void TestV6()
{
  // 使用列表方式初始化，C++11新语法
  vector<int> v{ 1, 2, 3 };
 
  vector<int>::iterator pos = find(v.begin(), v.end(), 2);
    if (pos != v.end()) 
  {
        v.erase(pos); // 删除pos位置的数据
        /*
        * 如果想要继续通过迭代器操作vector中的元素，需要给pos重新赋值
        * 即 pos = v.erase(pos); // 返回指向被删除元素下一个w的迭代器
        */
    }
    // 在erase之后，pos迭代器位置就失效了，不能再去访问了
  // 这里的失效是指pos位置的意义变了，pos不再指向原来的值
  //cout << *pos << endl;
  //*pos = 200;
}

运行结果：

  • VS2019 下验证，程序崩溃（VS 会进行检查）。
  • Linux 下验证，虽然没有崩溃（和具体实现、检查机制有关），但也认为失效了。

分析：

对于 erase，我们在 erase 后也可能会失效，失效的原因有两种：

  1. insert 会扩容，那么 erase 也会缩容（比如有 200 个容量的空间、200 个有效数据，在删除后，只剩下 70 个有效数据，然后想把容量给缩容至一半【开 100 个容量的空间，把旧空间内容拷贝后释放，pos 就是野指针了】)
  2. erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但 pos 位置的意义变了；如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 也是失效了。

这两种方式有是有可能的，STL 并没有对它们进行规定，但是不管缩容与否，都认为它们失效了，因为意义已经变了。并且在 VS 下做了非常严格的检查（pos 仅仅是意义改变了，并没有野指针，都不能进行访问），而在 G++ 下没有问题。

注意：find 不是 vector 自身提供的方法，是 STL 提供的算法，如果要查找只能使用STL提供的全局find。若找到，返回指向该元素的迭代器，若没有找到，返回 last （开区间）。

// 传迭代器区间 [first, last) 和要查找的元素
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
{
  while (first!=last)
    {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

【总结】

vector 插入或删除元素会导致当前迭代器和后面所有元素的迭代器失效。

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

如果想要继续通过迭代器操作 vector 中的元素，需要给 pos 重新赋值

【补充】

operator[] + index 和 C++11 中 vector 的新式 for+auto 的遍历。
vector 使用这两种遍历方式是比较便捷的。

void TestV7()
{
  vector<int> v{1, 2, 3, 4};
  
  v[0] = 10; // 通过[]读写第0个位置
  cout << v[0] << endl;
 
  // 1、使用for+[]下标方式遍历
  for (size_t i = 0; i < v.size(); ++i)
  {
    cout << v[i] << " ";
  } 
  cout << endl;
 
  vector<int> swapv;
  swapv.swap(v); // 使用swap函数将原先的vector v与一个新的空vector swapv进行交换
  cout << "v data:";
    // 在输出v的数据时，可以看到原先的v已经变为空，不再包含任何元素
  for (size_t i = 0; i < v.size(); ++i)
  {
    cout << v[i] << " ";
  }   
  cout << endl;
 
  // 2、使用迭代器遍历
  cout << "swapv data:";
  auto it = swapv.begin();
  while (it != swapv.end())
  {
    cout << *it << " ";
    ++it;
  }
 
  // 3、使用范围for遍历
  for (auto x : v)
  {
    cout << x << " ";
  }   
  cout << endl;
}

operator[] 和 at 的区别是什么？

它们之间的主要区别在于对边界检查的处理方式：

  • operator[] 使用下标访问运算符 [] 可以直接通过索引来获取元素，不进行边界检查。如果使用下标访问一个越界的索引，会导致未定义行为。这种方式比较高效，适用于已经进行了边界检查或者明确知道索引是有效的情况。
  • at() 函数也用于通过索引来获取元素，但它会进行边界检查。如果传入的索引超过了有效的范围，at() 函数会抛出 std::out_of_range 异常。这种方式更安全，建议在需要进行边界检查或者对索引的有效性不确定时使用。

【总结】

operator[] 执行更快但不进行边界检查，而 at() 相对安全但速度稍慢，因为它会进行边界检查并抛出异常。

对于失效，有对应的机制来处理：比如 insert 是有一个返回值的，它返回一个迭代器指向新插入的那个元素，也就是说你想去访问那个指向的新插入的元素就可以 pos 接收 insert 的返回值。同理， erase 也是相同的，它返回被删除数据的下一个数据的位置。

【C++】Vector -- 详解（下）https://developer.aliyun.com/article/1514679?spm=a2c6h.13148508.setting.26.4b904f0ejdbHoA

文章标签：
C++
容器
索引
Linux
存储
关键词：
C++ vector
炫酷的伊莉娜
目录
相关文章
睡觉待开机
|
3月前
|
存储 编译器 C++
【C++】vector介绍+模拟实现
【C++】vector介绍+模拟实现
睡觉待开机
41 1
白子寰
|
1月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
白子寰
21 1
半截诗
|
1月前
|
安全 测试技术 C++
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化2
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化
半截诗
61 6
半截诗
|
1月前
|
安全 测试技术 C++
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化1
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化
半截诗
55 7
努力学习的小廉
|
1月前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
努力学习的小廉
32 1
半截诗
|
1月前
|
编译器 C语言 C++
【C++篇】解密 STL 动态之魂：全面掌握 C++ vector 的高效与优雅
【C++篇】解密 STL 动态之魂：全面掌握 C++ vector 的高效与优雅
半截诗
49 3
是店小二呀
|
1月前
|
C++
【C++】C++ STL探索:Vector使用与背后底层逻辑（三）
【C++】C++ STL探索:Vector使用与背后底层逻辑
是店小二呀
54 2
是店小二呀
|
1月前
|
编译器 Linux C++
【C++】C++ STL探索:Vector使用与背后底层逻辑（二）
【C++】C++ STL探索:Vector使用与背后底层逻辑
是店小二呀
41 2
是店小二呀
|
1月前
|
编译器 C++ 容器
【C++】C++ STL探索:Vector使用与背后底层逻辑（一）
【C++】C++ STL探索:Vector使用与背后底层逻辑
是店小二呀
43 1
禁默
|
1月前
|
算法 C++ 容器
C++之打造my vector篇（下）
C++之打造my vector篇（下）
禁默
27 0