🔭vector简介

1. vector是表示大小可变数组的序列容器。
2. vector采用连续的存储空间来存储元素。可用下标的方式对vector中元素进行访问，非常高效。
3. vector会分配一些额外的空间存储数据，以适应可能的增长，即存储空间比实际需要的存储空间大。不同的编译器的库采用了不同的方式权衡空间的使用和分配方式。
4. 与其它动态序列容器相比，vector在访问元素的时候更加高效，在末尾插入和删除元素相对高效。而在任意位置插入和删除相较而言效率低下，不建议经常使用。

🔭vector构造函数

int main()
{
	vector<int> v1;                         //无参构造
	vector<int> v2(5, 7);                   //用5个7构造v2
	vector<int> v3(v2.begin(), v2.end());   //指定v2的区间构造v3
	vector<int> v4(v3);                     //用v3拷贝构造v4
	return 0;
}

🔭vector空间增长问题

👾reserve 、resize

• reserve只负责开辟空间，若知道需要多少空间，reserve可以减缓vector频繁增容的代价。
• resize开空间的同时对其进行初始化，影响size的大小。

resize的使用情况：

reserve使用情况:

👾size 、empty

👾capacity

测试capacity的增容机制：

void test_capacity()
{
	size_t size;
	vector<int> foo;
	size = foo.capacity();
	cout << "making v grow；" << endl;
	for (int i = 0;i < 100;++i)
	{
		foo.push_back(i);
		if (size != foo.capacity())
		{
			size = foo.capacity();
			cout << "capacity changed: " << size << endl;
		}
	}
}
int main()
{
	test_capacity();
	return 0;
}

vs2022下和Linux下的运行结果对比：

总结：上述探索capacity的增容机制的代码在vs和g++下运行发现，vs下capacity是按照1.5倍增长，g++下是按照2倍增长。单次增容次数越多，增容次数就少，效率更高同时可能空间浪费更严重。单次增容空间少，会导致频繁增容，从而效率低下。若提前知道vector中要存储多少数据，可以提前用reserve将空间开好。

🔭vector中迭代器使用

template <class T>
void PrintVector(const vector<T>& v)
{
	class std::vector<T>::const_iterator it = v.begin();
	while (it != v.end())
	{
		*it += 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

🔭vector的增删查改

👾push_back 、pop_back

int main()
{
	vector<string> v1;
	string s("hello");
	v1.push_back(s);

	vector<int> v2;
	for (int i = 0;i < 10;++i)
	{
		v2.push_back(i);
	}
	v2.pop_back();
	return 0;
}

👾operator[]

🔎operator[]在vector中的使用场景：

// operator[]+index和c++中vector的for+auto的遍历
int main()
{
	vector<int> v{ 1,2,3,4,5,6,7 };

	// 通过[]更改下标为2位置的数据并访问
	v[2] = 33;
	cout << v[2] << endl;

	// 使用for+[]方式遍历vector
	for (size_t i = 0;i < v.size();++i)
	{
		cout << v[i] << " ";
	}
	cout << endl;

	return 0;
}

👾insert 、erase 、find

🔎vector中insert和erase的用法：

//任意位置插入:insert 和 erase,以及查找find
int main()
{
	// 使用列表方式初始化，c++11的新语法
	vector<int> v{ 1,2,3,4,5,6,7 };
	
	//insert：在指定位置插入值为val的元素，在1之前插入0，若找不到1，则不插入
	//使用find查找1的位置
	vector<int>::iterator pos = find(v.begin(), v.end(),1);
	if (pos != v.end())
	{
		//在pos位置之前插入0
		v.insert(pos, 0);
	}

	//erase:删除指定位置数据，删除4
	pos = find(v.begin(), v.end(), 4);
	//删除pos位置数据
	v.erase(pos);

	return 0;
}

🔭vector的迭代器失效问题

迭代器的作用是让算法能够不用关心底层的数据结构，迭代器其底层就是指针或对指针进行了封装。因此迭代器失效实际就是底层对指针所指向的空间被销毁了，使用一块已经被释放的空间。若继续使用已失效的迭代器，程序可能会崩溃。

💻可能会导致vector迭代器失效的几种可能：
1、引起其底层空间改变的操作，都可能使vector的迭代器失效，如：reserve、resize、insert、push_back等操作。

int main()
{
	vector<int> v{ 1,2,3,4,5,6,7,8,9 };
	auto it = v.begin();

	//插入元素期间，可能会引起扩容，从而导致空间被释放
	v.insert(v.begin(), 0);
	v.push_back(9);

	//给vector重新赋值，可能会引起底层容量的改变
	v.assign(100, 10);

    while(it!=v.end())
    {
         cout<<*it<<" ";
         ++it; 
    }
	return 0;
}

🪐迭代器失效原因：以上操作，都有可能导致vector扩容，vector底层旧空间被释放，再次访问it时，it还使用原来的空间，对it进行访问时，访问的是一块已经释放的空间，而导致程序运行时奔溃。
对于以上问题，我们需要让it指向新的空间并访问，对it进行重新赋值。

2、指定位置元素的删除导致迭代器失效

❓接下来我们来看一个问题，删除所有vector中所有的偶数，怎么设计代码是正确的？

首先我们来看一个错误的示例：❌

int main()
{
	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;
	}
	return 0;
}

代码的运行测试及分析：

改进之后的代码，解决迭代器失效问题：✔️

int main()
{
	vector<int> v{ 1,2,3,4,5,6,7 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			//erase(it) 之后，it失效，不能++，erase会返回删除位置it的下一个位置
			it = v.erase(it);
		}
		else
			++it;
	}
	for (auto e : v)
		cout << e << " ";
	return 0;
}

运行测试及分析:

3、Linux下，g++编译器对迭代器的失效检测并没有vs下严格，处理方式相较没有那么极端

//扩容之后，迭代器已经失效了，程序虽可以运行，但是运行结果并不对
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;
	//扩大vector容器空间，使迭代器失效
	v.reserve(100);
	cout << "扩容后vector容量：" << v.capacity() << endl;

	//经过上述的reserve之后，it迭代器失效了，在vs下程序直接崩溃，在Linux下则不会（可能运行成功，但结果不对）
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	return 0;
}

代码在vs2022下运行结果：

看看此代码在Linux下运行的结果：

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;
	}
	return 0;
}

📖erase删除任意位置数据后，Linux下迭代器没有失效，因为空间没变，后面的元素往前移，it的位置依然有效，但若erase删除的是最后一个元素，删除后it越界，++it导致程序崩溃。erase的失效都是意义变了或者不在有效访问数据范围内。

📄总结一下：对于insert和erase造成的迭代器失效问题，Linux g++ 平台检测相对没有那么严格，基本依靠操作系统自身对野指针的越界检查机制，Windows下vs系列的检查更为严格，使用了强制检查的机制，即使是迭代器没有越界，仅仅是意义变了也可以检查出来。

👾迭代器失效场景总结

vector迭代器失效有两种情况：
1、插入元素、扩容导致空间改变，导致野指针式迭代器失效。
2、迭代器指向的空间位置意义变了。程序运行结果错误或导致崩溃。