[C/C++ -STL]vector使用及迭代器失效问题详解

admin • 2021-11-21 20:03 • 程序人生

一、vector介绍
vector文档介绍

Vector 是序列容器，表示可以改变大小的数组。与数组一样，Vector使用其元素的连续存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中一样高效。但与阵列不同的是，它们的大小可以动态变化，其存储由容器自动处理。
在内部，Vector 使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配此数组以增大其大小，这意味着分配一个新数组并将所有元素移动到该数组中。就处理时间而言，这是一项相对昂贵的任务，因此，向量不会在每次将元素添加到容器时重新分配。
相反，vector容器可能会分配一些额外的存储以适应可能的增长，因此容器的实际容量可能大于严格要求包含其元素的存储容量（即，其大小）。库可以实现不同的增长策略，以平衡内存使用和重新分配，但在任何情况下，重新分配只应以对数增长的大小间隔进行，以便在向量末尾插入单个元素时可以提供摊销的恒定时间复杂度
因此，与阵列相比，vector消耗更多内存，以换取以高效方式管理存储和动态增长的能力。
与其他动态序列容器（deques、list和forward_list）相比，向量非常高效地访问其元素（就像数组一样），并且相对高效地从其末端添加或删除元素。对于涉及在端点以外的位置插入或删除元素的操作，它们的性能比其他操作差，并且与列表和转发列表相比，迭代器和引用的一致性较差。
二、vector使用
1.vector构造方法

vector() 无参构造
vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
vector (const vector& x); 拷贝构造
vector (InputIterator first, InputIterator last); 使用迭代器进行初始化构造

vector<int> v;
	//无参构造
	vector<int> v1(5,6);
	//构造并用5个6初始化v1
	vector<int> v2(v1);
	//拷贝构造
	vector<int> v3(v1.begin(),v1.end());
	//使用迭代器进行初始化构造

第一个是无参构造：
构造一个没有元素的空容器。
第二个是构造函数：
构造一个包含n个元素的容器。每个元素都是val的副本。
拷贝构造：
以相同的顺序构造一个容器，其中包含x中每个元素的副本。
第4个构造函：
用迭代器构造构造一个容器，其中包含与范围[first，last]相同数量的元素，每个元素都是从该范围内对应的元素以相同的顺序构造的。
2.iterator 的使用

begin + end 获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

vector<int>::iterator it = v2.begin();
		while (it != v2.end()) {
			cout << *it << " ";
			it++;
		}

正向迭代器从第一个数开始遍历，没打印一个数就就获取后一位置的迭代器一直如此直到迭代器指到容器尾部。

vector<int>::reverse_iterator it = v2.rbegin();
		while (it != v2.rend()) {
			cout << *it << " ";
			it++;
		}

反向迭代器和正向迭代器相反从容器尾部开始遍历直到遍历到容器首部就停止。
3.vector空间增长问题

size 获取数据个数
capacity 获取容量大小
empty 判断是否为空
resize 改变vector的size
reserve 改变vector放入capacity

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

	vector<int> v;
		//无参构造
		vector<int> v1(5,6);
		//构造并用5个6初始化v1
		cout<<v1.size() << endl;
		cout << v1.capacity() << endl;
		cout << v.empty() << endl;
		cout << v1.empty() << endl;

首先这里v1的size()和capacity()的大小相同但是代表的是不同含义，size()代表是有效数据长度，而capacity代表是容器的容量大小在一般情况下不相等。因为v是无参构造所以v.empty（）输出是1，而v1有数据所以输出了0.
4.vector增删查改

push_back 尾插
pop_back 尾删
find 查找。
insert 在position之前插入val
erase 删除position位置的数据
swap 交换两个vector的数据空间
operator[] 像数组一样访问

		vector<int> v;
		//无参构造
	v.push_back(0);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

		//使用迭代器进行初始化构造
		vector<int>::iterator it = v.begin();
		while (it != v.end()) {
			cout << *it << " ";
			it++;
		}
		cout << endl;
		v.pop_back();
		vector<int>::iterator it1 = v.begin();
		while (it1 != v.end()) {
			cout << *it1 << " ";
			it1++;
		}
		cout << endl;

首先对无参构造的v尾插几个数打印数，接着未删后接着打印一边数来验证函数。

vector的inseert的使用要借助迭代器

		vector<int> v;
		//无参构造
	v.push_back(0);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	 
		//使用迭代器进行初始化构造
		vector<int>::iterator it = v.begin();
		while (it != v.end()) {
			cout << *it << " ";
			it++;
		}
		cout << endl;
		v.insert(v.begin(),2, 9);
		vector<int>::iterator it1 = v.begin();
		while (it1 != v.end()) {
			cout << *it1 << " ";
			it1++;
		}
		cout << endl;
		v.insert(v.begin(), 9);
		vector<int>::iterator it11 = v.begin();
		while (it11 != v.end()) {
			cout << *it11 << " ";
			it11++;
		}
		cout << endl;

通过在指定位置的元素之前插入新元素来扩展向量，从而通过插入的元素数量有效地增加容器大小。
当且仅当新向量大小超过当前向量容量时，这会导致自动重新分配分配分配的存储空间。

	vector<int> v;
		//无参构造
		int val[5] = { 0,1,2,3,4 };
		v.insert(v.begin(), val, val + 5);
		//使用迭代器进行初始化构造
		vector<int>::iterator it = v.begin();
		while (it != v.end()) {
			cout << *it << " ";
			it++;
		}

因为向量使用数组作为其底层存储，所以在向量末端以外的位置插入元素会导致容器将位置之后的所有元素重新定位到它们的新位置。与其他类型的序列容器对相同操作执行的操作相比，这通常是一种低效的操作。

find函数底层实际上是对指针的操作

向[first，last]范围内比较等于val的第一个元素返回迭代器。如果未找到此类元素，则函数返回last。函数使用运算符==将各个元素与val进行比较。此函数模板的行为等效于：

template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

这是文档给出的解释。

	vector<int> v;
		//无参构造
		v.push_back(0);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		auto it = find(v.begin(), v.end(), 2);
		if (it != v.end()) {
			cout << "找到了" << endl;
		}
		v.erase(it);

find函数找到2的位置迭代器，然后erase删除it

	auto it1 = v.begin();
		while (it1!=v.end()) {
			if (*it1 == 2) {
				v.erase(it1);
			}
		
			it1++;
		}

这样一段程序会出错，因为vector的迭代器也是指针，如果删除这个指针所指的数据对于释放了这个空间，it就变成一个野指针对一个野指针进行 it++ 是肯定会出错的。
我们通过查阅文档可以看到erase函数的返回值是这么介绍的：一个迭代器，指定在任何删除的元素之后剩余的第一个元素，如果不存在这样的元素，则指定指向向量结尾的指针
4.vector迭代器失效问题
这里正式简单解释一下迭代器实现
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了
封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的
空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，
程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有：

会引起其底层空间改变的操作，都有可能是迭代器失效，比如：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);
// 给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就认为该位置迭代器失效了。

int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
return 0;
}
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
++it;
}
return 0;
}

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

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

1024程序员节 c++STL 容器数据结构

二维码

LeetCode 559 N叉树的最大深度[dfs bfs] HERODING的LeetCode之路

< <上一篇

【LeetCode 二叉树专项】删除二叉搜索树中的节点（450）

下一篇>>

搜索内容

[C/C++ -STL]vector使用及迭代器失效问题详解

最新文章

分类

标签云