vector(3)

vector(3)

vector 迭代器失效问题。（重点）

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

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

1.会引起其底层空间改变的操作，都有可能是迭代器失效

比如：resize、reserve、insert、 assign、push_back等.

这里拿insert来举例子：

vector.h

// 迭代器失效，本质因为一些原因，迭代器不可用
iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos <= _finish);

	if (_finish == _endofstorage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}

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

	*pos = x;
	++_finish;

	return pos;
}


void test_vector2()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	//v1.push_back(5);

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	v1.insert(v1.begin(), 30);

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

这上面的代码是正确的版本，也就是可以运行的版本

但是我们平常在写代码也会遇到好多好多问题，以下是一些常见问题：

这里的错误在于实参传递给形参，但是形参的改变不会影响实参，这里传递给前面的begin,函数的返回值，传递的是拷贝而不是值本身，因为拷贝相当于是临时对象，临时对象具有常性，就相当于被const修饰，权限给缩小了

还有哪些情况会导致产生临时对象？ 如类型转换

2.指定位置元素的删除操作–erase

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理 论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end 的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素 时，vs就认为该位置迭代器失效了。

以下代码的功能是删除vector中所有的偶数，请问那个代码是正确的，为什么？

代码1：

#include <iostream>
using namespace std;
#include <vector>
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;
}

代码2：

#include <iostream>
using namespace std;
#include <vector>
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;
}

注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。

// 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
int main()
{
vector<int> v{1,2,3,4,5};
for(size_t i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;
auto it = v.begin();
cout << "扩容之前，vector的容量为: " << v.capacity() << endl;
// 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效
v.reserve(100);
cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
// 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux
下不会
// 虽然可能运行，但是输出的结果是不对的
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
程序输出：
1 2 3 4 5
扩容之前，vector的容量为: 5
扩容之后，vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5

// 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
#include <vector>
#include <algorithm>
int main()
{
vector<int> v{1,2,3,4,5};
vector<int>::iterator it = find(v.begin(), v.end(), 3);
v.erase(it);
cout << *it << endl;
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
程序可以正常运行，并打印：
4
4 5

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
// 此时迭代器是无效的，++it导致程序崩溃
int main()
{
vector<int> v{1,2,3,4,5};
// vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
while(it != v.end())
{
if(*it % 2 == 0)
v.erase(it);
++it;
}
for(auto e : v)
cout << e << " ";
cout << endl;
return 0;
}

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

vector 空间增长问题

resize

改变vector的size

代码示例如下：

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

	v1.resize(10);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	v1.resize(15, 1);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	v1.resize(2);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

功能和在string里面差不多

拷贝构造

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

	vector<int> v2(v1);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

这里我们没有自己写拷贝构造的话，编译器会有自己生成的拷贝构造进行调用，也就是浅拷贝，值进行拷贝过去，

这样子析构的时候，会析构两次，程序出现问题

所以需要自己写深拷贝：

vector(const vector<T>&v)
{
	reserve(v.capacity());//这里是以防v1里面的数据过多，需要用reserve预留开辟一块空间
    for(auto &e:v)//这里用了范围for,用到了引用，e是v1的别名，将v1里面的元素进行遍历
    {
        push_back(e);//尾插到v2里面
    }
}

赋值拷贝

代码如下：(现代写法)

void swap(vector<T>& tmp)
{
	std::swap(_start, tmp._start);
	std::swap(_finish, tmp._finish);
	std::swap(_endofstorage, tmp._endofstorage);
}

// v1 = v3
vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

vector<int> v3 = { 10,20,30,40 };
v1 = v3;

for (auto e : v1)
{
	cout << e << " ";
}
cout << endl;

区间构造迭代器

// 类模板的成员函数，也可以是一个函数模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

// vector<double> v4(10, 1.1);
// vector<int> v4(10, 1);
vector(size_t n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}
//这里要将n前面的size_t改为int ,因为编译器会选择更其最匹配的进行调用
vector(int n, const T& val = T())
{
	reserve(n);
    //这里也需要注意
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

vector(initializer_list<T> il)
{
	reserve(il.size());

	for (auto& e : il)
	{
		push_back(e);
	}
}

只有int会有这样的问题，出现不匹配的问题，别的类型不会

使用memcpy拷贝问题

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存 空间中
2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型 元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅 拷贝。

例子如下：

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t oldSize = size();
		T* tmp = new T[n];
		if (_start)
		{
			// memcpy(tmp, _start, sizeof(T) * oldSize);
			for (size_t i = 0; i < oldSize; i++)
			{
				tmp[i] = _start[i];
			}

			delete[] _start;
		}

		_start = tmp;
		_finish = _start + oldSize;
		_endofstorage = _start + n;
	}
}


void test_vector9()
{
	vector<string> v1;
	v1.push_back("1111111111111111");
	v1.push_back("1111111111111111");
	v1.push_back("1111111111111111");
	v1.push_back("1111111111111111");
	v1.push_back("1111111111111111");

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}