8.STL中Vector容器的常见操作(附习题)

简介: 8.STL中Vector容器的常见操作(附习题)

1.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,我们也是按照这个方法去学习  Vector 向量   // 可以理解为 顺序表

2 vector的使用

vector学习时一定要学会查看文档:vector的文档介绍,vector在实际中非常的重要,在实际中我们熟悉常 见的接口就可以,下面列出了哪些接口是要重点掌握的。

2.1 vector的定义

代码示例:

void test3()
{
  // constructors used in the same order as described above:
  vector<int> first;                                // empty vector of ints
  vector<int> second(4, 100);                       // four ints with value 100
  vector<int> third(second.begin(), second.end());  // iterating through second
  vector<int> fourth(third);                       // a copy of third
}


2.2 vector iterator 的使用

由图可见,iterator在STL中的用法都是相似的

自己类型的迭代器:

void test1()
{
  vector<int> v1{ 1,2,3,4 };
  // 自己类型的迭代器
  vector<int> v3(v1.begin(), v1.end());
  for (auto e : v3)
  {
    cout << e << " ";
  }
  cout << endl;
 
  string str("hello world");
  vector<char> v4(str.begin(), str.end());
  for (auto e : v4)
  {
    cout << e << " ";
  }
  cout << endl;
 
  int a[] = { 16,2,77,29 };
  vector<int> v5(a, a + 4);
  for (auto e : v5)
  {
    cout << e << " ";
  }
  cout << endl;
}

打印:

2.3 vector 空间增长问题

  • capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。 这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义 的。vs是PJ版本STL,g++是SGI版本STL。
  • reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问 题。
  • resize在开空间的同时还会进行初始化,影响size

代码示例:

void test4()
{
  // 往vecotr中插入元素时,如果大概已经知道要存放多少个元素
// 可以通过reserve方法提前将容量设置好,避免边插入边扩容效率低
  vector<int> v;
  size_t sz = v.capacity();
  v.reserve(100);
  cout << "making bar grow:\n";
  for (int i = 0; i < 100; ++i)
  {
    v.push_back(i);
    /*for (auto e : v)
      cout << e << ' ';*/
    cout << endl;
    if (sz != v.capacity())
    {
      sz = v.capacity();
      cout << "capacity changed: " << sz << '\n';
 
    }
  }
}

2.3 vector 增删查改

1.尾插:

与三种打印方式

void test1()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  //1.语法糖
  for (auto e : v)
  {
    cout << e << ' ';
  }
  cout << endl;
  //2.迭代器
  vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    cout << *it << ' ';
    it++;
  }
  cout << endl;
  //3.i数组
  for (int i = 0; i < v.size(); i++)
    cout << v[i] << ' ';
  cout << endl;
}

2.任意位置插入:

insert和erase,以及查找find   //注意find不是vector自身提供的方法,是STL提供的算法

void test5()
{
  // 使用列表方式初始化,C++11新语法
  vector<int> v{ 1, 2, 3, 4 };
 
  // 在指定位置前插入值为val的元素,比如:3之前插入30,如果没有则不插入
  // 1. 先使用find查找3所在位置
  auto pos = find(v.begin(), v.end(), 3);
 
  if (pos != v.end()) { // 如果找到了3
    // 注意:insert返回指向新插入元素的迭代器
    auto newPos = v.insert(pos, 30);//定义新位置
 
    for (auto e : v)
      cout << e << ' ';
    cout << endl;
    v.erase(newPos); // 移除新位置
  }
  for (auto m : v)
    cout << m << ' ';
  cout << endl;
}

如果不引入newpos,要使用原pos,需要重新定义,否则就会热重载

对于函数的调用:

要包含算法的头文件   <algorithm>

按升序排序:

void test()
{
  string str("hello world");
  vector<char> v4(str.begin(), str.end());
  for (auto e : v4)
  {
    cout << e << " ";
  }
  cout << endl;
 
  int a[] = { 16,2,77,29 };
  vector<int> v5(a, a + 4);
  for (auto e : v5)
  {
    cout << e << " ";
  }
  cout << endl<<"升序:";
 
  // 升序 < 
  // less
  sort(v5.begin(), v5.end());
  //sort(v5.rbegin(), v5.rend());
  for (auto e : v5)
  {
    cout << e << " ";
  }
  cout << endl<<"降序:";
 
  // 降序 >
  //greater<int> gt;
  //sort(v5.begin(), v5.end(), gt);
 
  sort(v5.begin(), v5.end(), greater<int>());
  for (auto e : v5)
  {
    cout << e << " ";
  }
  cout << endl;
 
  //void(*func)();
 
  sort(str.begin(), str.end());
  cout << str << endl;
 
  sort(a, a + 4);
  for (auto e : a)
  {
    cout << e << " ";
  }
  cout << endl;
}

注释:对于降序的实现

greater<int>()是一个函数对象,表示按照降序(从大到小)排序。将其放在sort最后来实现

2.4 vector 迭代器失效问题

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

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

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

#include <iostream>
using namespace std;
#include <vector>
 
int main()
{
  vector<int> v{ 1,2,3,4,5,6 };
 
  auto it = v.begin();
 
  // 将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容
  // v.resize(100, 8);
 
  // reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变
  // v.reserve(100);
 
  // 插入元素期间,可能会引起扩容,而导致原空间被释放
  // v.insert(v.begin(), 0);
  // v.push_back(8);
 
  // 给vector重新赋值,可能会引起底层容量改变
  v.assign(100, 8);
 
  /*
  出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉,
   而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的
   空间,而引起代码运行时崩溃。
  解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新
   赋值即可。
  */
  while (it != v.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  return 0;
}

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

#include <iostream>
using namespace std;
#include <vector>
 
int main()
{
  int a[] = { 1, 2, 3, 4 };
  vector<int> v(a, a + sizeof(a) / sizeof(int));
 
  // 使用find查找3所在位置的iterator
  vector<int>::iterator pos = find(v.begin(), v.end(), 3);
 
  // 删除pos位置的数据,导致pos迭代器失效。
  v.erase(pos);
  cout << *pos << endl; // 此处会导致非法访问
  return 0;
}

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

3. 注意:Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端。

SGI STL中,迭代器失效后,代码并不一定会崩溃,但是运行结果肯定不 对,如果it不在begin和end范围内,肯定会崩溃的。

4. 与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效

一些建议:

  1. 如果需要在迭代过程中修改 vector,可以先将需要修改的元素标记起来,迭代完成后再进行修改。
  2. 插入迭代器可以在指定位置插入元素而不影响原有迭代器,删除迭代器可以删除指定位置的元素而不影响原有迭代器。
  3. 使用循环遍历 vector 时,可以使用索引值而不是迭代器来访问元素,这样可以避免迭代器失效的问题。
  4. 可以先将需要修改的元素拷贝到一个临时 vector 中进行操作,操作完成后再将临时 vector 的元素拷贝回原 vector。
  5. 使用 C++11 中的新特性,如移动语义和智能指针,可以减少 vector 迭代器失效的问题。移动语义可以避免不必要的拷贝操作,智能指针可以帮助管理内存,减少内存泄漏的可能性。

2.5 vector 在OJ中的使用

136. 只出现一次的数字

题解:

118. 杨辉三角(二维)

题解:

通过指定numRows来初始化vv,即开辟了numRows行。每一行可以通过vv[i]来访问,其中i表示行号。每一行中的元素可以通过vv[i][j]来访问,其中j表示列号。


相关文章
|
2天前
|
API 开发工具 数据安全/隐私保护
阿里云云效操作报错合集之流水线镜像已经生成,但容器没有出现,是什么导致的
本合集将整理呈现用户在使用过程中遇到的报错及其对应的解决办法,包括但不限于账户权限设置错误、项目配置不正确、代码提交冲突、构建任务执行失败、测试环境异常、需求流转阻塞等问题。阿里云云效是一站式企业级研发协同和DevOps平台,为企业提供从需求规划、开发、测试、发布到运维、运营的全流程端到端服务和工具支撑,致力于提升企业的研发效能和创新能力。
|
2天前
|
敏捷开发 Kubernetes 测试技术
阿里云云效产品使用合集之流水线创建时,不想选择节点和容器,该如何操作
云效作为一款全面覆盖研发全生命周期管理的云端效能平台,致力于帮助企业实现高效协同、敏捷研发和持续交付。本合集收集整理了用户在使用云效过程中遇到的常见问题,问题涉及项目创建与管理、需求规划与迭代、代码托管与版本控制、自动化测试、持续集成与发布等方面。
|
24天前
|
C++ 容器
C++之评委打分案例(vector与deque容器练习)
C++之评委打分案例(vector与deque容器练习)
17 1
|
17天前
|
存储 安全 C++
|
19天前
|
存储 算法 C语言
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
|
19天前
|
设计模式 存储 缓存
【C++】详解STL容器之一的deque和适配器stack,queue
【C++】详解STL容器之一的deque和适配器stack,queue
|
19天前
|
存储 算法 C++
【C++】详解STL容器之一的 vector
【C++】详解STL容器之一的 vector
|
19天前
|
算法 C语言 C++
【C++】详解STL的容器之一:list
【C++】详解STL的容器之一:list
|
23天前
|
C++ 容器
C++ STL标准库 《map容器详解》
C++ STL标准库 《map容器详解》
22 0
|
24天前
|
存储 C++ 容器
C++ STL标准库 《map容器详解》
C++ STL标准库 《map容器详解》
25 0