【C++进阶(三)】STL大法--vector迭代器失效&深浅拷贝问题剖析

简介: 【C++进阶(三)】STL大法--vector迭代器失效&深浅拷贝问题剖析

1. 前言

在阅读本篇文章前,一定要先看前集:

vector深度剖析(上)

本章重点:

本章会重点讲解vector迭代器失效问题
以及vector中的深浅拷贝问题
并且简单完善一下vector的自我实现

在此之前,我将在文章末尾把vector

自我实现的完整代码分享给大家


2. 什么是迭代器失效?

首先我们要清楚一点:

vector的每一次扩容都不是在
原地扩容,而是新开辟一块儿空间后
将原先的数据拷贝到新空间

请看下面的代码:

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(),v.end(),3);
v.insert(pos,30);
v.insert(pos,40);

这段代码在3前面插入一个30和40

但是这段代码会出错!

为什么呢?请看下图:

注:从四个数据插入为五个会扩容

  • 扩容前
    迭代器pos在start和finish之间
  • 扩容后
    start和finish的地址改变,pos失效
    pos不再指向现在的位置3

迭代器失效的本质原因是:

扩容后start和finish的地址发生变化

指向原先位置的迭代器统统失效!

若没发生扩容,则一切安好!


3. 迭代器失效的经典案例

除了前面讲到的insert导致迭代器失效外

erase函数也会导致迭代器失效

请看下面的案例:

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(6);
for (auto e : v)
{
  cout << e << " ";
}
cout << endl;
auto it = v.begin();
while (it != v.end())
{
  if (*it % 2 == 0)
  {
    it = v.erase(it);
  }
  ++it;
}
for (auto e : v)
{
  cout << e << " ";
}
cout << endl;

这段代码在删除顺序表中所有的偶数

但是你会发现它并没有删除完

这是为啥呢?请看下图的分析

erase删除后,后面的数据会覆盖过来
此时不让迭代器++它也指向下一个位置

注:在VS编译器中.只要使用了erase函数
编译器自动认为此位置迭代器失效
所以在VS上进行多次erase操作时
一定要不断更新迭代器的位置!


4. 迭代器失效的解决方案

  1. 对于insert来说

在pos位置使用一次insert后

不要再次直接访问pos迭代器

一定要更新了pos之后再去访问!

库中的vector提供了返回值来解决此问题:

insert会返回一个迭代器,此迭代器的
返回的是新插入元素的迭代器

请看下图理解:

所以以后我们可以这样写代码:

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(7);
vector<int>::iterator it = v.begin();
while(it!=v.end())
{
  it = insert(it,100);
  it+=2;
}
for (auto e : v)
{
  cout << e << " ";
}
cout << endl;

在每一个元素前插入一个100

  1. 对于erase来说

删除后不用再++迭代器

只用在没删除的时候再++

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
v.push_back(6);
auto it = v.begin();
while (it != v.end())
{
  if (*it % 2 == 0)
  {
    it = v.erase(it);
  }
  else
  {
    ++it;
  }
}
for (auto e : v)
{
  cout << e << " ";
}
cout << endl;

5. 对于reserve的深度剖析

众所周知,reserve只改变capacity大小

而不会改变size的大小

所以这样写代码是有问题的:

vector<int> vv;
vv.reserve(10);//开辟10份空间
for(int i=0;i<10;i++)
{
  vv[i]=i;
}

因为size此时是0,也就是有效长度为0
虽然你开辟了10份空间,但是运算符
操作[ ]的内部实现会检查下标:

T& operator[](size_t pos)
{
  assert(pos < size());
  return _start[pos];
}

所以使用reserve后直接用[ ]
访问会报错,这也是很多人会出错的地方!


6. vector深浅拷贝问题

首先来看看以下代码:

vector<vector<int>> vv(3,vector<int>(5));

这是一个二维数组,初始化为三行五列

vector<vector<int>> vv(3,vector<int>(5));
vector<vector<int>> x(vv);

这是在拷贝构造类对象x

自我实现的拷贝构造使用的是memcpy:

Vector(const Vector<T>& v)
{
  assert(v._start && v._finish && v._endofsto);
  _start = new T[v.capacity()];//给size或capacity都可以
  memcpy(_start, v._start, sizeof(T) * v.size());
}

然而memcpy是逐个字节拷贝
当数组是一维时,用memcpy没有问题
但是当数组是二维数组时,会出错!

我们在VS上调试窗口的监视查看地址信息:

会发现,虽然x的地址和vv的地址不同
但是vv中的迭代器和x中的迭代器
的地址是相同的也就是指向同一份空间

可以用下图来理解这个过程:


7. vector深浅拷贝的解决方法

由于这种深浅拷贝问题是因为memcpy

导致的,所以这里不能使用memcpy

只需要老实的使用一个for循环就能解决:

修改后的代码:

Vector(const Vector<T>& v)
{
  assert(v._start && v._finish && v._endofsto);
  _start = new T[v.capacity()];//给size或capacity都可以
  //memcpy(_start, v._start, sizeof(T) * v.size()); //使用memcpy时,数组是二维数组会发生问题
  for (size_t i = 0; i < size(); i++)
  {
    _start[i] = v._start[i];
    _finish = _start + v.size();
  }
  _endofsto = _start + v.capacity();
}

直接使用等号=是外部和内部都是
原来的一份拷贝,这样就能解决问题了


8. 总结以及拓展

vector的自我实现的目的不是
为了实现一个比库中更好的vector
而是为了带大家熟悉vector的使用
并且了解了内部实现后,以后用vector
时出现问题可以很快的排查出来!

拓展:vector自我实现全部代码链接:

gitee代码仓库


🔎 下期预告:链表接口熟悉以及模拟实现 🔍


相关文章
|
7月前
|
缓存 算法 程序员
C++STL底层原理:探秘标准模板库的内部机制
🌟蒋星熠Jaxonic带你深入STL底层:从容器内存管理到红黑树、哈希表,剖析迭代器、算法与分配器核心机制,揭秘C++标准库的高效设计哲学与性能优化实践。
C++STL底层原理:探秘标准模板库的内部机制
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
364 2
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
738 73
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
623 3
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
920 1
|
存储 算法 C++
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
498 12
|
11月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
265 0