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

从C语言到C++_15(vector的模拟实现)+迭代器失效问题(下）

2024-05-28 33
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 从C语言到C++_15(vector的模拟实现)+迭代器失效问题

从C语言到C++_15(vector的模拟实现)+迭代器失效问题（中）：https://developer.aliyun.com/article/1521294

4.2 erase

erase代码比insert简单，就是挪动数据，是这样写吗？：

    void erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个
 
      iterator left = pos + 1;
      while (left < _finish)
      {
        *(left - 1) = *left;
        ++left;
      }
      --_finish;
    }

erase 有没有迭代器失效的问题？

删除会导致 pos 失效吗？

我们用三种场景去测试：①  1 2 3 4 5  （正常，是个巧合）

  void Test4_erase()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数
    while (pos != v1.end()) 
    {
      if (*pos % 2 == 0) 
      {
        v1.erase(pos);
      }
      pos++;
    }
    for (auto e : v1) 
    {
      cout << e << " ";
    }
    cout << endl;
  }

②  1 2 3 4  （崩溃）

  void Test4_erase()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    //v1.push_back(5);
    vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数
    while (pos != v1.end()) 
    {
      if (*pos % 2 == 0) 
      {
        v1.erase(pos);
      }
      pos++;
    }
    for (auto e : v1) 
    {
      cout << e << " ";
    }
    cout << endl;
  }

③  1 2 4 5  （结果不对，没删除完）

  void Test4_erase()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    //v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数
    while (pos != v1.end()) 
    {
      if (*pos % 2 == 0) 
      {
        v1.erase(pos);
      }
      pos++;
    }
    for (auto e : v1) 
    {
      cout << e << " ";
    }
    cout << endl;
  }

erase(pos) 以后，pos 指向的意义已经变了，直接 pos++ 可能会导致一些意料之外的结果。

对于情况 ③：比如连续的偶数，导致后一个偶数没有判断，导致没有删掉。

再其次，erase 的删除有些 vector 版本的实现，不排除它会缩容。

      //if (size() < capacity()/2)
      //{
      //  // 缩容 -- 以时间换空间（虽然基本不会这么用了）
      //}

如果是这样，erase(pos) 以后，pos 也可能会是野指针，跟 insert 类似。


（SGI 和 PJ 版本 vector 都不会缩容）


对于情况 ②：如果最后一个数据是偶数，会导致 erase 以后，pos 意义变了。


再 ++ 一下，导致 pos 和 end 错过结束判断，出现越界问题。


而情况 ①： 之所以没有翻车，是因为被删除的偶数后面恰巧跟的是奇数，运气好逃过了一劫。


导致上述三种问题的本质：erase(pos) 以后，pos 的意义变了，再去 pos++ 是不对的。

为了解决这个问题，erase 是这么说明的：

规定erase返回删除位置下一个位置迭代器，改进 erase：

    iterator erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个
 
      iterator left = pos + 1;
      while (left < _finish)
      {
        *(left - 1) = *left;
        ++left;
      }
      --_finish;
      return pos;//此时pos就是删除位置下一个位置迭代器
    }

简单测一下第三个情况：（第二个情况也成功了）

  void Test4_erase()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    vector<int>::iterator pos = v1.begin();// 删除v1所有的偶数
    while (pos != v1.end()) 
    {
      if (*pos % 2 == 0) 
      {
        pos = v1.erase(pos);
      }
      else
      {
        pos++;
      }
    }
    for (auto e : v1) 
    {
      cout << e << " ";
    }
    cout << endl;
  }

01aa14985c454f6aaff51262ceb2ec2e.png

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


① 会引起其底层空间改变的操作，都有可能存在迭代器失效。


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


② 指定位置元素的删除操作：erase


erase 删除 pos 位置元素后，pos 位置之后的元素就会往前搬移，


没有导致底层空间的改变，理论上讲迭代器不应该会失效。


但是 pos 刚好是最后一个元素，删完之后 pos 刚好在 end 的位置，


而 end 位置是没有元素的，那么 pos 就失效了。


因此删除 vector 中任意位置元素时，VS 就认为该位置迭代器失效了。


还有就是我们刚才讲解的奇偶数，删除 pos 位置的数据，导致 pos 迭代器失效。


当然，vector 迭代器的失效主要发生在 insert 和 erase。vector 的其他接口基本不碰迭代器，自然也就不涉及这些问题。


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


string 的 insert 和 erase 迭代器是否会失效？string 有没有迭代器失效？


当然会，只要使用迭代器的容器，都可能会涉及迭代器失效。


只是 string 一般很少涉及迭代器失效，因为它 insert 和 erase 时主要用下标。

5. vector 深拷贝

5.1 拷贝构造

可以使用传统写法，也可以使用现代写法，看看传统写法：全都自己干，

    vector(const vector<T>& v)
    {
      reserve(v.capacity());
      for (const auto& e : v)
      {
        push_back(e);
      }
    }

老老实实开空间，老老实实拷数据。

因为我们已经实现好了 reserve，所以我们这里可以直接调用 reserve 去开空间。

注意这里不能使用 memcpy，这个我们前面已经强调过了。

现代写法：找工具人帮忙干活：— 让迭代器区间当工具人：

    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_end_of_storage, v._end_of_storage);
    }
 
    vector(const vector<T>& v)// 现代写法
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      vector<T> tmp(v.begin(), v.end());
      swap(tmp);
    }

有感觉现代写法比传统写法难？还要写swap和迭代器区间初始化？

但是这两个接口本来就是vector里面的，只是顺便实现了现代写法，简单测下： 

  void Tess5() 
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
 
    vector<int> v2(v1);
    for (const auto& e : v2)
    {
      cout << e << " ";
    }
    cout << endl;
  }

5.2 赋值 operator=

传统写法就是把 v2 赋值给 v1，自己把 v1 释放了，再去深拷贝出 v2 一样大的空间……

太麻烦了，直接用现代写法，只要有了拷贝构造，赋值都可以用现代写法。

并且，这里还可以利用 "传参调用拷贝构造" 这一特性，做到真正的 "压榨" 工具人。

所以我们去掉 const 和引用传参，为的是让形参去充当临时变量 tmp ——

    vector<T>& operator=(vector<T> v)// 现代写法
    {
      swap(v);
      return *this;
    }

想要 v1 跟 v3 有一样大的空间一样大的值，我们让传参的时候就顺便把这件事给办了。


现在 v 手上就有 v3 了，然后再用 swap 函数夺取 v 的劳动成果，最后返回 *this 就大功告成了。


这里 v1 不仅把 v 从 v3 得到的东西，还让 v 帮忙把垃圾丢了（释放空间） ——


简单测下：

  void Test5() 
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
 
    vector<int> v2(v1);
    for (const auto& e : v2)
    {
      cout << e << " ";
    }
    cout << endl;
 
    vector<int> v3;
    v3 = v2;
    for (auto e : v3)
    {
      cout << e << " ";
    }
    cout << endl;
  }

6. 两道选择题

6.1 下面程序的输出结果正确的是( )

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
  int ar[] = { 1,2,3,4,0,5,6,7,8,9 };
  int n = sizeof(ar) / sizeof(int);
  vector<int> v(ar, ar + n);
  vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    if (*it != 0)
      cout << *it;
    else
      v.erase(it);
    it++;
  }
  return 0;
}

A.程序运行崩溃

B.1 2 3 4 5 0 6 7 8 9

C.1 2 3 4 5 6 7 8 9

D.1 2 3 4 6 7 8 9

6.2 下面关于迭代器失效的描述哪个是错误的（ ）（多选）

A.vector的插入操作一定会导致迭代器失效


B.vector的插入操作有可能不会导致迭代器失效


C.vector的删除操作只会导致指向被删除元素及后面的迭代器失效


D.vector的删除操作只会导致指向被删除元素的迭代器失效


答案：


6.1 A


分析:当迭代器的值为0时，此时会进行删除，删除后如果迭代器不重新赋值，会导致原来的迭代器失效，此时针对一个已经失效的迭代器在进行++,会导致程序崩溃>


6.2 AD


A.vector的插入操作如果导致底层空间重新开辟，则迭代器就会失效。如果空间足够，不扩容时，迭代器不一定失效，比如push_back尾插，元素插入到空间末尾，在不扩容时不会对迭代器产生影响


B.参考A的解释。


C.vector删除，当前元素肯定失效，后面元素会牵扯到移动数据，因此删除元素后面的迭代器也会失效


D. vector的删除操作不光会导致指向被删除元素的迭代器失效，删除元素后面的迭代器也会失效


完整代码：

完整代码：

vector.h

#pragma once
 
#include<iostream>
#include<assert.h>
#include<string>
using namespace std;
 
namespace rtx
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
 
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {}
    ~vector()
    {
      delete[] _start;
      _start = _finish = _end_of_storage = nullptr;
    }
 
    size_t size() const
    {
      return _finish - _start;
    }
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
 
    void push_back(const T& x)
    {
      //if (_finish == _end_of_storage)
      //{
      //  reserve(capacity() == 0 ? 4 : capacity() * 2);
      //}
      //*_finish = x;
      //++_finish;
      insert(end(), x);
    }
    void reserve(size_t n)
    {
      if (n > capacity())
      {
        size_t sz = size();
        T* tmp = new T[n];
        if(_start)
        {
          //memcpy(tmp, _start, sizeof(T) * sz); //浅拷贝，不行
 
          for (size_t i = 0; i < sz; i++)// 如果T是int，一个一个拷贝没问题
          {
            tmp[i] = _start[i];// 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。
          }
          delete[] _start;
        }
        _start = tmp;
        _finish = tmp + sz;
        _end_of_storage = tmp + n;
      }
    }
 
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return *(_start + pos);
    }
    const T& operator[](size_t pos) const
    {
      assert(pos < size());
      return *(_start + pos);
    }
 
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
 
    template<class InputInterator>
    vector(InputInterator first, InputInterator last)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
 
    void resize(size_t n, const T& val = T())
    {
      if (n > capacity())
      {
        reserve(n);
      }
      if (n > size())
      {
        while (_finish != _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
      else
      {
        _finish = _start + n;
      }
    }
 
    void pop_back() 
    {
      assert(_finish > _start);
      --_finish;
    }
 
    iterator insert(iterator pos, const T& val)
    {
      assert(pos >= _start);// ①检查pos是否越界
      assert(pos <= _finish);
 
      if (_finish == _end_of_storage)// ②检查是否需要扩容
      {
        size_t len = pos - _start;// 记录一下pos到_start的距离
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos，
        //而且形参不会影响实参，传引用的话begin等就传不了，所以用返回解决
      }
 
      iterator right = _finish - 1;// ③移动数据
      while (right >= pos)
      {
        *(right + 1) = *right;
        --right;
      }
 
      *pos = val;// ④插入数据
      ++_finish;
      return pos;
    }
 
    iterator erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个
 
      iterator left = pos + 1;
      while (left < _finish)
      {
        *(left - 1) = *left;
        ++left;
      }
      --_finish;
      return pos;//此时pos就是删除位置下一个位置迭代器
    }
 
    //vector(const vector<T>& v)// 传统写法
    //{
    //  reserve(v.capacity());
    //  // memcpy(_start, v._start, v.size() * sizeof(T));  // 会翻车
    //  for (const auto& e : v)
    //  {
    //    push_back(e);
    //  }
    //}
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_end_of_storage, v._end_of_storage);
    }
 
    vector(const vector<T>& v)// 现代写法
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      vector<T> tmp(v.begin(), v.end());
      swap(tmp);
    }
 
    vector<T>& operator=(vector<T> v)// 现代写法
    {
      swap(v);
      return *this;
    }
 
  private:
    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
  };
}

本篇完。

下一部分：list的接口函数介绍，list模拟实现，再后面就是栈和队列。

文章标签：
C语言
C++
容器
关键词：
C++ c语言
C语言C++
C++ vector
C++迭代器
C++ vector迭代器
GR鲸鱼
目录
相关文章
睡觉待开机
|
2月前
|
存储 编译器 C++
【C++】vector介绍+模拟实现
【C++】vector介绍+模拟实现
睡觉待开机
34 1
sunrr
|
16天前
|
算法 机器人 C语言
ROS仿真支持C++和C语言
ROS仿真支持C++和C语言
sunrr
28 1
qq2108462953
|
2月前
|
C++ 容器
【C/C++笔记】迭代器
【C/C++笔记】迭代器
qq2108462953
18 1
大柏怎么被偷了
|
2月前
|
编译器 Linux C语言
【C++小知识】为什么C语言不支持函数重载，而C++支持
【C++小知识】为什么C语言不支持函数重载，而C++支持
大柏怎么被偷了
39 1
大柏怎么被偷了
|
2月前
|
算法 编译器 Linux
【C++】vector的模拟实现
【C++】vector的模拟实现
大柏怎么被偷了
31 1
大柏怎么被偷了
|
2月前
|
存储 算法 C语言
【C++】vector的认识与使用
【C++】vector的认识与使用
大柏怎么被偷了
45 1
可能只会写BUG
|
29天前
|
编译器 C语言 C++
从C语言到C++
本文档详细介绍了C++相较于C语言的一些改进和新特性，包括类型检查、逻辑类型 `bool`、枚举类型、可赋值的表达式等。同时，文档还讲解了C++中的标准输入输出流 `cin` 和 `cout` 的使用方法及格式化输出技巧。此外，还介绍了函数重载、运算符重载、默认参数等高级特性，并探讨了引用的概念及其应用，包括常引用和引用的本质分析。以下是简要概述： 本文档适合有一定C语言基础的学习者深入了解C++的新特性及其应用。
可能只会写BUG
16 0
hylreg
|
2月前
|
C++ 索引
C++数组、vector求最大值最小值及其下标
C++数组、vector求最大值最小值及其下标
hylreg
60 0
qq2108462953
|
2月前
|
存储 安全 程序员
【C/C++笔记】迭代器范围
【C/C++笔记】迭代器范围
qq2108462953
56 0
二二*一一
|
15天前
|
编译器 C++
C++ 类构造函数初始化列表
构造函数初始化列表以一个冒号开始，接着是以逗号分隔的数据成员列表，每个数据成员后面跟一个放在括号中的初始化式。
二二*一一
60 30