vector迭代器失效问题（增删改）(push_back,pop_back,erase,clear)

Vector迭代器增、删、改导致的literator失效问题

增

capacity不足

当vector插入数据后，超过容量的情况

• 例子

//capacity()不足，在末尾添加元素
void showInfo(vector<int> &v) {
	cout << "Capacity:" << v.capacity() << endl;
	cout << "Size:" << v.size() << endl;
	cout << "vector:(value,pos)"
		<<"\t";
	for (auto& a : v) {  
		cout <<"("<< a <<"," << &a << ")"
			<< "\t";
	}
	cout << endl
		<< "iterator:(value,pos)"
		<< "\t";
	cout << "(" << *i1 << "," << &(*i1) << ")"
		<< "\t";
	cout << "(" << *i2 << "," << &(*i2) << ")"
		<< "\t";
	cout << "(" << *i3 << "," << &(*i3) << ")"  //解引用后迭代器是未定义的
		<< "\t" << endl;
	cout << endl;
}
void test() {
	vector<int> v = { 1,2};
	i1=v.begin();
	i2=++v.begin();
	i3=v.end();
	cout << "尾部插入前" << endl;
	showInfo(v);
	v.push_back(3);
	cout << "尾部插入后" << endl;
	showInfo(v);
	
}

• 分析

​ 在尾插执行完毕后，vector中所有迭代器全部失效，显然系统给整个vector重新开辟了一块内存，并将数据覆盖进去

capacity充足——首插

不用担心超出vector容量

• 例子

void test() {
	vector<int> v = { 1,2 };
	v.reserve(3);
	i1 = v.begin();
	i2 = ++v.begin();
	i3 = v.end();
	cout << "首插入前" << endl;
	showInfo(v);
	v.insert(v.begin(), 0);
	cout << "首插入后" << endl;
	showInfo(v);

}

• 分析

​ 首插后，各迭代器均指向原vector后一个值，故所有迭代器失效。

capacity充足——中插

• 例子

void test() {
	vector<int> v = { 1,3 };
	v.reserve(3);
	i1 = v.begin();
	i2 = ++v.begin();
	i3 = v.end();  //指向的是capacity的后一位
	cout << "中插入前" << endl;
	showInfo(v);
	v.insert(++v.begin(), 2);
	cout << "中插入后" << endl;
	showInfo(v);

}

• 分析

​ 插入点之后，包括插入点的迭代器均失效！

capacity充足——尾插

• 例子

void test() {
	vector<int> v = { 1,2 };
	v.reserve(3);
	i1 = v.begin();
	i2 = ++v.begin();
	i3 = v.end();
	cout << "尾插入前" << endl;
	showInfo(v);
	v.push_back(3);
	cout << "尾插入后" << endl;
	showInfo(v);
}

• 分析

​ 同上，插入点之前的迭代器均未失效

总结

1. size()==capacity()，插入数据时系统会为整个vector重新分配内存，并将原vector拷贝到新的内存空间——所有迭代器均失效
2. size()<capacity(),插入数据时系统不会重新分配内存。
   • 若迭代器指向插入位置前（不包括插入位置）的元素，其未失效。
   • 否则，失效。

​

删

尾删

包括push_back()和erase()

• 例子

void test() {
	vector<int> v = { 1,2,3};
	v.reserve(3);
	i1 = v.begin();
	i2 = ++v.begin();
	i3 = ++i2;
	iend = v.end();
	cout << "尾删前" << endl;
	showInfo(v);
	//v.pop_back(); //push_back删尾
	v.erase(i3);  //erase删尾
}

• 分析

  执行尾删后，指向删除前元素的迭代器未失效，仍然保留着删除前的数据。

头删（和中删类似）

erase

• 例子

void test() {
	vector<int> v = { 1,2,3};
	v.reserve(3);
	i1 = v.begin();
	i2 = ++v.begin();
	i3 = ++i2;
	iend = v.end();
	cout << "头删前" << endl;
	showInfo(v);
	v.erase(i1);
	cout << "头删后" << endl;
	showInfo(v);
}

• 分析

  执行删除操作后，除指向删除前的最后一个元素的迭代器和删除位置之前的元素的迭代器，其余迭代器均失效

执行clear()

• 分析

  指向clear执行前的所有元素的迭代器均未失效

总结

​ 删除数据时，系统不会重新分配一块内存给vector；从删除位置开始（包括该位置）到最后一个元素（非end()）之前，原迭代器（指向删除操作前的数据）均失效。

​ clear()仅仅将vector的size变为0，目测是逻辑删除，对内存和原迭代器无影响。

改

对迭代器所指向的值进行更改，显然不会造成迭代器失效