【C++指南】STL容器的安全革命：如何封装Vector杜绝越界访问与迭代器失效？

发布于：2025-05-14 ⋅ 阅读:(11) ⋅ 点赞:(0)

🌟 各位看官好，我是egoist2023！

🌍 种一棵树最好是十年前，其次是现在！

🚀 使用STL的三个境界：能用，明理，能扩展

👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦！

了解vector常用接口

vector是C++标准模板库中的部分内容，中文偶尔译作“容器”，但并不准确。它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

常见构造

(constructor) 构造函数声明
接口说明
vector() （重点）
无参构造
vector （ size_type n, const value_type& val = value_type()）
构造并初始化 n 个 val
vector (const vector& x); （重点）
拷贝构造
vector (InputIterator first, InputIterator last);
使用迭代器进行初始化构造

迭代器 

iterator 的使 用
接口说明
begin + end （重点）
获取第一个数据位置的 iterator/const_iterator ， 获取最后一个数据的下
一个位置的 iterator/const_iterator
rbegin +  rend
获取最后一个数据位置的 reverse_iterator ，获取第一个数据前一个位置的reverse_iterator

容量操作 

容量空间
接口说明
size
获取数据个数
capacity
获取容量大小
empty
判断是否为空
resize （重点）
改变 vector 的 size
reserve （重点）
改变 vector 的 capacity

修改操作

vector 增删查改
接口说明
push_back （重点）
尾插
pop_back （重点）
尾删
find
查找。（注意这个是算法模块实现，不是 vector 的成员接口）
insert
在 position 之前插入 val
erase
删除 position 位置的数据
swap
交换两个 vector的数据空间
operator[] （重点）
像数组一样访问

vector实现

底层结构

在C语言实现当中，vector实现中并没有迭代器的支持，因此底层结构设计并不复杂。

typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

为了提供迭代器的支持，可以像指针一样遍历数组，因此对vector的底层封装采用如下。

template<class T>

class vector
{
public:
    typedef T* iterator;
	typedef const T* const_iterator;
    //...

private:
	//给缺省值
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;
};

迭代器

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

memcpy拷贝问题

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t oldsize = size();
		T* tmp = new T[n];
		memcpy(tmp, _start, sizeof(T) * oldsize);
		delete[] _start;

		_start = tmp;
		_finish = _start + oldsize;
		_end_of_storage = _start + n;
	}
}

实际上，上面这段程序在内置类型是不会出问题的，但是针对一些场景（如自定义类型）会报错，如下图所示。

如果vector中存的是自定义类型

问题1：会导致多次析构；

问题2：一个数据的修改会影响另一个 。

问题3：memcpy则只能拷贝每个string,但还是同样指向同一个串。

为了防止浅拷贝问题，如下程序是针对自定义类型的优化。

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t oldsize = size();
		T* tmp = new T[n];
		//memcpy(tmp, _start, sizeof(T) * oldsize); //err只能针对内置类型

		for (size_t i = 0;i < oldsize;++i)
		{
			tmp[i] = _start[i]; 
			//内置类型不会有问题
			//自定义类型调用其=运算符重载函数走深拷贝,防止memcpy出现的问题
		}
		delete[] _start;

		_start = tmp;
		_finish = _start + oldsize;
		_end_of_storage = _start + n;
	}
}
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为
memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对
指针进行了封装 ，比如： vector 的迭代器就是原生态指针 T* 。因此 迭代器失效，实际就是迭代器
底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间 ，造成的后果是程序崩溃 ( 即
如果继续使用已经失效的迭代器，程序可能会崩溃 ) 。
对于 vector 可能会导致其迭代器失效的操作有：
1. 会引起其底层空间改变的操作，都有可能是迭代器失效 ，比如： resize 、 reserve 、 insert 、
assign 、 push_back 等。 
void insert(iterator pos, const T& x)
{
	assert(pos < _finish);
	assert(pos >= _start);

	if (size() == capacity())
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}

	iterator it = _finish - 1;
	while (it >= pos)
	{
		*(it + 1) = *it;
		--it;
	}

	*pos = x;
	++_finish;
}

 在上面这段程序中，由于容量满了需要进行扩容，开辟一段新空间，将旧空间的元素拷贝到新空间上来，并更新_start，_finish，_end_of_storage。但如果迭代器it指向旧空间上的开始位置，此时进行*it会导致野指针解引用问题，这也就是所谓地迭代器失效了。

那该如何解决呢？更新迭代器指向的位置。

void insert(iterator pos, const T& x)
{
	assert(pos < _finish);
	assert(pos >= _start);
    
    //防止迭代器失效
	if (size() == capacity())
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		pos = _start + len;
	}

	//...
}

更新了迭代器位置后，解引用还是会报错，这是为什么呢？这里看似解决了问题，但是别忘了形参的改变并不能影响实参，即实参中的迭代器依然指向旧空间的位置，依旧会使迭代器失效。那我让形参的改变影响实参可行吗，即加上引用呢？

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

而我们设计初心是想要pos可以随意访问数组中的元素，当想访问数组中的第三个元素时

v.insert(v.begin()+3,3);

 由于是左值引用右值，需要是const左值引用才能引用右值，那么再进行更改。

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

这里会发现由于const的修饰，会导致insert函数内部是无法修改迭代器pos位置的，因此这种方案也是不可取的。

总之，insert以后，默认迭代器都失效了（尽管在insert函数里修复了迭代器指向位置，但由于形参并不会实参）。

2. 指定位置元素的删除操作 -->  erase 
		void erase(iterator pos)
		{
			assert(pos < _finish);
			assert(pos >= _start);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}
		  --_finish;
		}

这里的删除依然存在着一个隐秘的问题 -->那它又是如何导致的呢？

	auto it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			v1.erase(it);
		}

		++it;
	}
erase 删除 pos 位置元素后， pos 位置之后的元素会往前搬移，没有导致底层空间的改变， 理
论上讲迭代器不应该会失效 ，但是：如果 pos 刚好是最后一个元素， 删完之后pos刚好是end
的位置，而end位置是没有元素的，那么pos就失效了（即it和_finish刚好错过了，循环判断依然成立，此时继续执行会出现错误）。
按照上面的说法，那么改下判断条件不就能使it等于_finish了吗？（如下代码所示）但运行之后依然会报错，这是因为 删除 vector中任意位置上元素时，vs就认为该位置迭代器失效了，即在 vs下检查严格 。（Linux 下， g++ 编译器对迭代器失效的检测并不是非常严格，处理也没有 vs 下极端） 
	auto it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			v1.erase(it);
		}
		else
		{
			++it;
		}
	}

因此，使用erase接口时并不能依赖于编译器，应注意需要手动更新迭代器防止迭代器失效问题。

在stl库中也是这么解决的。

迭代器失效解决办法：在使用前，对迭代器重新赋值即可 。 
	auto it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			it = v1.erase(it);
		}
		else
		{
			++it;
		}
	}

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

总的来说：vector特别需要注意的是在使用insert和erase接口应注意迭代器失效问题，这样才能让我们在使用stl库接口时应对自如。

initializer_list实现

		void push_back(const T& x)
		{
			if (size() == capacity())
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}
			*_finish = x;
			_finish++;
		}

		vector(initializer_list<T> il)
		{
			reserve(il.size());
			for (auto& ch : il)
			{
				push_back(ch);
			}
		}

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布