vector

vector的常用接口

vector的构造

vector()                                        无参构造

vector(size_type n, const value_type& val = value_type())          构造并初始化n个val

vector (const vector& x)                拷贝构造

vector (InputIterator first, InputIterator last)                         使用迭代器构造

vector iterator的使用 

begin() + end()                                 获取第一个元素的位置和最后一个元素的下一个位置

rbegin() + rend()                               获取最后一个元素的位置和第一个元素的前一个位置

vector容量操作接口

size()                                                获取元素个数

capacity()                                         获取容量大小

empty()                                             判断是否为空

resize(n, val)                                    改变vector的size

reserve                                             改变vector的capacity

注意：使用resize接口时，val是一个缺省的，默认给vector元素的初始值。当改变的size小于原本的size，那么直接截断多余的部分；当改变的size大于原本的size，那么多余的部分用val的值填充；当改变的size大于原本的capacity，那么会对原本的vector进行扩容操作。具体文档如下：

reseve开辟空间在vs下capacity是按照1.5倍进行增长的，g++是按照2倍进行增长的。2倍增长时间效率更优，但可能会造成空间上的浪费（相对于1.5倍增长）。不需要纠结具体多少倍比较合适，按照实际的需求去定义增长的倍数。

vector的增删改查

push_back                                       尾插

pop_back                                         尾删

find                               查找（注意这是algorithm库中的函数模块，并不是vetor的成员函数）

inser                                              在pos位置插入val，后面的元素后移（注意pos是迭代器）

erase                                              删除pos位置的元素，后面的元素前移

swap                                               交换两个vector的元素空间

operator[]                                         让vector像数组一样访问

vector迭代器失效问题

1、会引起底层空间改变的操作，都可能引起迭代器失效，比如：resize、reserve、insert、assign、push_back等。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int>v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3); 
	v1.push_back(4);
	v1.push_back(5);
	vector<int>::iterator it = v1.begin();
	v1.push_back(6);
	//v1.push_back(7);

	while (it != v1.end())
	{
		cout << *it << ' ';
		it++;
	}
	cout << endl;
	return 0;
}

上面这个代码注释尾插7就可以运行。插入操作是需要扩容的，扩容是新开辟一块大的空间，然后把旧的空间复制给新的空间，然后释放旧的空间。当插入7的时候，需要扩容，那么这个it指向释放了的空间。所以使用迭代器需要在可能对容量操作的代码之后。

2、指定位置元素的删除操作（erase)

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int>v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3); 
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
			v1.erase(it); // it = v1.erase(it); 对迭代器重新赋值就可以了。
		else
			it++;
	}
	for (int e : v1)
		cout << e << ' ';
	cout << endl;
	return 0;
}

对于上面代码是实现vector中偶数的删除。当it指向的元素是偶数，那么就会删除it指向的元素，然后后面的元素往前移。假如没有指向偶数那么it++。并没有改变底层的空间，但是还是会报错。这是因为当it指向最后一个位置是偶数，那么需要删除，后面元素前移，这个时候it就是指向end，那么it就失效了。所以，vector删除任意的位置，vs就认为该位置的迭代器失效了。

3、但是，在Linux下，g++编译器对迭代器失效并没有这么严格

对于第一种迭代器失效的情况，g++还是可以运行，但是结果是错误的。

对于第二种迭代器失效的情况，当最后一个元素没有被删除，那么就可以运行，因为当删除一个位置的元素，后面的元素会前移去填充这个删除的位置，那么这个位置在g++下认为还是可以访问的。如果最后一个元素被删了，那么就不能运行了。

总得来说：对迭代器失效得解决办法就是对迭代器重新赋值

vector的模拟实现

代码很多，放在码云上了

vector的模拟实现