序列容器vector。

iterator——迭代器

迭代器与指针类似，可以访问顺序容器与关联容器中的元素。

声明方法

容器名::iterator 变量名 //由此声名该容器的迭代器。

vector<int>::iterator iter;//声明了一个名为iter的变量

vector<int>::const_iterator cit;	//声明了一个const_iterator。

*cit++;		//正确

//(*cit)++; 错误

• const_iterator对象其自身的值可以改(可以指向其他元素)，但不能改写其指向的元素值.

begin与end迭代器

每种容器都定义了begin与end的函数，用于返回迭代器。

• begin用于返回指向第一个元素的迭代器

  vector<int>::iterator iter = vec.begin();//iter指向vec[0]

• end用于返回指向末端元素的下一个的迭代器，称为“超出末端迭代器”，即指向一个不存在的元素。

应用：遍历容器操作

for(iter=vec.begin();iter!=vec.end();iter++)
{
	cout<<*iter<<endl;
}

其他操作

指针上的操作iterator基本上都是全部满足的。而两个迭代器相减返回的是两迭代器在容器内的差值。

vector——动态数组

头文件 #include<vector>

• vector是一种可变大小数组的序列容器，采用连续的存储空间来存储元素，可以使用数组下标的方式访问vector的元素。
• 动态存储：刚开始vector会自动分配一段连续的内存空间，当存储元素超过预配空间之后，vector会重新分配空间，拷贝数据，释放旧内存。
• vector可以高效访问元素、在末尾添加元素和删除元素，但vector对元素操作的复杂度是根据到末尾的距离成正比。
• vector是一个单口的容器，适用于在末尾进行频繁的查出删除，但不适合频繁移动元素，这会引起整体元素的移动，降低效率。

vector的声明与初始化

vector<int> vec;			//声明了一个int型的空vector
vector<int> v2(vec);		//v2包含了vec所有元素的副本
vector<int> v3 = vec;		//等价于v3(vec)这种形式
vector<int> vec(5);			//声明了一个初始大小为5的，且都是默认值的vector
vector<int> vec(10,1);		//声明了一个int型的初始大小为10的并且值都是1的vector

Vector中括号初始化与返回值

vector<int> vec{a,b,c...};	//声明并用这些值对应每个位置进行初始化
vector<int> vec ={a,b,c};	//等价于vec{a,b,c...};


vector<int> twoSum(vector<int>& nums, int target) 
{
	return {i,j};
}

• vector作函数返回值时,直接返回{}这种形式也是可以的。

vector访问元素

• vector可使用数组下标的形式访问对应索引位置的元素，但是不能使用下标形式添加元素。
• at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。

vector的基本操作

empty(); //判断容器是否为空，空返回true

capacity(); //容器的容量

size(); //返回容器中元素的个数

resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
				//如果容器变短，则末尾超出容器长度的元素被删除。

resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除

push_back(ele); //尾部插入元素ele

pop_back(); //删除最后一个元素

insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele

insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele

erase(const_iterator pos); //删除迭代器指向的元素，返回指向下一个位置的迭代器！！！

erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素

clear(); //删除容器中所有元素

at(int idx); //返回索引idx所指的数据

operator[]; //返回索引idx所指的数据

front(); //返回容器中第一个数据元素

back(); //返回容器中最后一个数据元素

swap(vec); // 将vec与本身的元素互换，即实现两个容器内元素互换

reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

vector预留空间

void test1() {

	vector<int> vec;

	int num = 0;
	int* p = nullptr;

	for (int i = 0; i < 100000; i++) {
		vec.push_back(i);

		if (p != &vec[0]) {
			p = &vec[0];
			num++;
		}
	}

	cout << "不预留空间 ：num = " << num << endl;
}

void test2() {

	vector<int> vec;

	vec.reserve(100000);

	int num = 0;
	int* p = nullptr;

	for (int i = 0; i < 100000; i++) {
		vec.push_back(i);

		if (p != &vec[0]) {
			p = &vec[0];
			num++;
		}
	}

	cout << "预留空间 ：num = " << num << endl;
}

• 每当p值不等于vec的首地址时，说明vector已经自动进行了内存的扩展。

运行结果：

不预留空间 ：num = 30
预留空间 ：num = 1

如果预先知道了要使用多少存储空间，那么提前预留空间可以避免vector自动进行内存扩展，可以提高效率。

vector使用swap收缩内存

void test3() {

	//使用swap来收缩空间

	vector<int> vec;

	for (int i = 0; i < 100000; i++)
		vec.push_back(i);

	cout << "初始时：" << endl;
	cout << "vec capacity= " << vec.capacity() << endl;
	cout << "vec size= " << vec.size() << endl;

	vec.resize(3);

	cout << "重置大小之后：" << endl;
	cout << "vec capacity= " << vec.capacity() << endl;
	cout << "vec size= " << vec.size() << endl;

	//使用匿名对象和 swap 来交换内存
	vector<int>(vec).swap(vec);

	cout << "收缩内存之后：" << endl;
	cout << "vec capacity= " << vec.capacity() << endl;
	cout << "vec size= " << vec.size() << endl;

}

运行结果：

初始时：
vec capacity= 138255
vec size= 100000
重置大小之后：
vec capacity= 138255
vec size= 3
收缩内存之后：
vec capacity= 3
vec size= 3

• vector<int>(vec)表示使用vector的拷贝构造函数来创建一个匿名对象，实际上就是使用vec当前有的元素来初始化这个匿名对象的内存。
• 调用swap(vec)之后，匿名对象与vec这个容器会进行元素交换。
• 当前行执行结束之后，匿名对象会被系统释放掉，从而原来分配的那么一大段内存空间就被释放掉了。

使用情景

• 动态数组。

迭代器失效

• insert插入元素之后
  • 若引起扩容，原来所有的迭代器都失效
  • 若没有扩容，后半段迭代器失效！