【C++/STL】:vector容器的底层剖析&&迭代器失效&&隐藏的浅拷贝

24k纯甄 2024-07-26 16:05:03 阅读 80

目录

💡前言一,构造函数1 . 强制编译器生成默认构造2 . 拷贝构造3. 用迭代器区间初始化4. 用n个val值构造5. initializer_list 的构造

二,析构函数三,关于迭代器四,有关数据个数与容量五,交换函数swap六,赋值拷贝七,[ ]运算符八,预留空间(扩容)8.1 使用memcpy拷贝问题(重点)

九,尾插和尾删数据十,插入数据 insert十一,删除数据 erase十二,insert和erase的迭代器失效问题(重点)1. 什么是迭代器失效?2. insert 的迭代器失效2.1 insert 内部pos位置的失效2.2 insert 以后外部的实参失效

3. erase 以后的迭代器失效

💡前言

点击跳转到文章:vector容器的基本使用

上篇文章已经介绍了vector容器的基本使用,这篇文章主要选择vector中一些核心的,基本的接口进行模拟实现。

注意:由于我们模拟实现时使用了类模板所以不建议进行文件分离,不然会产生链接错误所以我们把函数都写在.h文件中,在Test.cpp文件中进行测试

首先我们先给出vector类:

<code>#include <assert.h>

#include <vector>

#include <iostream>

using namespace std;

template<class T>

class vector

{

public:

// Vector的迭代器是一个原生指针

typedef T* iterator;

typedef T* const_iterator;

//......

private:

iterator _start = nullptr;//指向开始位置的指针

iterator _finish = nullptr;//指向最后一个位置的下一个位置的指针

iterator _end_of_storage = nullptr;//指向存储容量的尾

};

一,构造函数

在vector文档中,构造函数分为好几个类型,下面分别进行介绍:

1 . 强制编译器生成默认构造

无参构造

vector() = default;

2 . 拷贝构造

//v2(v1);

vector(const vector<T>& v)

{

//提前预开空间,避免边尾插边扩容

reserve(v.capacity());

for (auto e : v)

{

//this->push_back(e);

push_back(e);

}

}

3. 用迭代器区间初始化

(1) 一个类模版的成员函数可以写成函数模版

(2) 若使用iterator做迭代器,会导致初始化的迭代器区间[first,last)只能是vector的迭代器,重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器

template <class InputIterator>

vector(InputIterator first, InputIterator last)

{

while (first != last)

{

push_back(*first);

++first;

}

}

4. 用n个val值构造

vector(size_t n, const T& val = T())

{

reserve(n);

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

vector(int n, const T& val = T())

{

reserve(n);

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

具体使用:

//初始化3个空

vector<string> v1(3);

//初始化为3个xx

vector<string> v2(3, "xx");

//初始化为3个1

vector<int> v3(3, 1);//err 非法的间接寻址.参数匹配问题

vector<int> v3(3u, 1);//ok

//如果非要这样传参数,就需要再重载一个构造

vector<int> v3(3, 1);

(1) 为什么要重载两个类似的构造

理论上将,提供了vector(size_t n, const T& value = T())之后vector(int n, const T& value = T())就不需要提供了,但是对于:vector< int > v(10, 5);

编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型, 就不会走vector(size_t n, const T& value = T())这个构造方法, 最终选择的是:vector(InputIterator first, InputIterator last)。因为编译器觉得区间构造两个参数类型一致,因此编译器就会InputIterator实例化为int,但是10和5根本不是一个区间,编译时就报错了,故需要增加该构造方法。

(2) T()是什么

T()是缺省值,注意这里不能给0,因为T可能为自定义类型,当T为内置类型的时候,也ok。因为C++对内置类型进行了升级,也有构造,为了兼容模版。

5. initializer_list 的构造

(1) C++11新增的类模板initializer_list,方便用花括号初始化

(2) 这里不需要传引用&,因为不涉及拷贝问题,它的内部其实有两个指针,一个指向第一个值的位置,一个指向最后一个值的下一个位置,并且支持迭代器

vector(initializer_list<T> il)

{

reserve(il.size());

for (auto e:il)

{

push_back(e);

}

}

具体使用:

支持被花括号括起的任意个数的值给 initializer_list

auto il1 = { 1,3,4,5,6,7 };

initializer_list<int> il2 = { 1,2,3 };

//这里的隐式类型转换不一样,参数个数不固定

vector<int> v4 = { 7,8,9,4,5 };//隐式类型转换

vector<int> v5({ 4,5,6 });//直接构造

在这里插入图片描述

二,析构函数

<code>~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

三,关于迭代

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin()const

{

return _start;

}

const_iterator end()const

{

return _finish;

}

四,有关数据个数与容量

//计算有效数据个数

size_t size()const

{

return _finish - _start;

}

//计算当前容量

size_t capacity()const

{

return _end_of_storage - _start;

}

五,交换函数swap

与string类类似,依然调用库里的swap函数,进行指针的交换。

void swap(vector<T>& v)

{

std::swap(_start, v._start);

std::swap(_finish, v._finish);

std::swap(_end_of_storage, v._end_of_storage);

}

六,赋值拷贝

与string类的现代写法相同。

//赋值拷贝

//v3 = v1;

vector<T>& operator=(const vector<T> v)

{

swap(v);

return *this;

}

七,[ ]运算符

//[]运算符

T& operator[](size_t pos)

{

//断言,避免下标越界

assert(pos < size());

return _start[pos];

}

八,预留空间(扩容)

void reserve(size_t n)

{

//由于开空间后_start指向改变,所以要提前记录原来的有效数据个数

//以便在新空间中更新_finish的位置

size_t old_size = size();

if (n > capacity())

{

T* tmp = new T[n];//开新空间

if (_start)

{

//memcpy(tmp, _start, sizeof(T) * old_size);

for (size_t i = 0; i < old_size; i++)

{

//此时这里的赋值调用的是string的赋值,肯定是深拷贝

tmp[i] = _start[i];

}

delete[] _start;//释放旧空间

}

_start = tmp;//改变指向,指向新空间

//在新空间里更新_finish,_end_of_storage的位置

_finish = _start + old_size;

_end_of_storage = _start + n;

}

}

8.1 使用memcpy拷贝问题(重点)

假设模拟实现的vector中的reserve接口中,使用memcpy进行的拷贝,以下代码会发生什么问题?

int main()

{

bite::vector<bite::string> v;

v.push_back("2222");

v.push_back("2222");

v.push_back("2222");

return 0;

}

问题分析:

(1) memcpy是内存的二进制格式拷贝,按字节拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中

(2) 如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝

图解如下:

当把原空间里的"2222"拷贝进新空间后,delete会先对原空间的每个对象调用析构函数,再把原空间销毁,但是此时tmp仍指向那块空间,变成野指针了

在这里插入图片描述

复用赋值进行修改后

此时这里的赋值调用的是string的赋值,肯定是深拷贝

在这里插入图片描述

九,尾插和尾删数据

<code>//尾插数据

void push_back(const T& x)

{

if (_finish == _end_of_storage)

{

size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;

reserve(newcapacity);

}

*_finish = x;

++_finish;

}

//尾删

void pop_back()

{

//断言,确保有数据可删

assert(size() > 0);

--_finish;

}

十,插入数据 insert

//void insert(iterator pos, const T& x)

iterator insert(iterator pos, const T& x)

{

//断言,判断下标的有效性

assert(pos >= _start && pos <= _finish);

//判断是否扩容

if (_finish == _end_of_storage)

{

size_t len = pos - _start;

size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;

reserve(newcapacity);

//insert函数的内部迭代器失效问题:类似于野指针问题

//扩容后pos位置失效,需要重新计算pos

pos = _start + len;

}

//挪动数据再插入

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

--end;

}

*(end + 1) = x;

++_finish;

//返回新插入那个位置的迭代器

return pos;

}

十一,删除数据 erase

iterator erase(iterator pos)

{

assert(pos >= _start && pos < _finish);

iterator end = pos + 1;

while (end != _finish)

{

*(end - 1) = *end;

++end;

}

--_finish;

//返回删除位置的下一个位置的迭代器

return pos;

}

十二,insert和erase的迭代器失效问题(重点)

1. 什么是迭代器失效?

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

2. insert 的迭代器失效

2.1 insert 内部pos位置的失效

当刚好执行了扩容操作这一步时,由于要开辟新空间,拷贝数据,释放空间,改变空间指向。但是此时pos位置还在原空间,这就使pos变成了野指针,如果对该位置进行访问,就会导致程序崩溃

所以在函数内部,扩容后我们要更新pos迭代器

在这里插入图片描述

2.2 insert 以后外部的实参失效

演示代码如下

<code>void vector_test2()

{

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

for (size_t i = 0; i < v1.size(); i++)

{

cout << v1[i] << " ";

}

cout << endl;

//输入x,查找是否存在,如果存在,在该位置前插入10

int x;

cin >> x;

vector<int>::iterator it = find(v1.begin(), v1.end(), x);

//用返回值接收

it = v1.insert(it, 10);

//建议失效后的迭代器不要访问,除非使用返回值。

cout << *it << endl;

for (size_t i = 0; i < v1.size(); i++)

{

cout << v1[i] << " ";

}

cout << endl;

}

insert以后it这个实参会不会失效呢?答案是:会的

在扩容的时候一定会导致迭代器失效。因为虽然在insert内部形参修正了,但是形参的改变不影响实参

在这里插入图片描述

迭代器失效的建议是:不要使用失效的迭代器

如果非要访问此时插入的那个位置,必须使用 insert 的返回值,返回的是新插入那个位置的迭代器

在这里插入图片描述

3. erase 以后的迭代器失效

erase 以后的迭代器失效问题比较复杂,它与平台相关。

代码演示如下

<code>int main()

{

int a[] = { 1, 2, 3, 4 };

vector<int> v(a, a + sizeof(a) / sizeof(int));

// 使用find查找3所在位置的iterator

vector<int>::iterator it = find(v.begin(), v.end(), 3);

// 删除it位置的数据,导致it迭代器失效。

//v.erase(it); // err

it = v.erase(it); // ok

cout << *it<< endl; // 此处会导致非法访问

return 0;

}

erase 以后it这个实参会不会失效呢?答案是:会的

erase删除pos位置元素后,it位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果it刚好是最后一个元素,删完之后it刚好是end的位置,而end位置是没有元素的,那么it就失效了或者说某个编译器有这样的机制:当删除到一定的数量时,会进行缩容处理,此时it也就相当于野指针了因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效了,后面元素会牵扯到移动数据,因此删除元素后面的迭代器也会失效

如果非要访问这个位置,也需要用返回值重新赋值,返回的是删除数据的下一个位置的迭代器!

在这里插入图片描述

以下代码的功能是删除vector中所有的偶数:

<code>int main()

{

vector<int> v{ 1, 2, 3, 4 };

auto it = v.begin();

while (it != v.end())

{

if (*it % 2 == 0)

//v.erase(it); // err

it = v.erase(it); // ok

++it;

}

return 0;

}

这个代码在VS平台下一定会运行崩溃!因为删除后it位置已经失效了,此时再对it进行访问(++操作或是解引用操作都是)会程序报错

但是在Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端,所以正常运行

注意:

与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效,但是string的插入一般由下标控制,虽然也重载了迭代器版本,但是并不常用

综上所述,迭代器失效解决办法:在使用前,对迭代器重新赋值即可



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。