C++ STL笔记三：vector容器；vector构造函数；vector赋值；vector容量和大小；vector插入和删除；vector数据存取；vector互换容器；vector预留空间。

vector数据结构和数组非常相似，也称为单端数组。

vector与普通数组的区别：数组是静态空间，而vector可以动态拓展。

数组静态空间：数组在声明时即指定了大小。无法再改变。vector动态拓展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝到新空间中，释放原空间。动态拓展机制：类似于C#种的ArrayList的Capacity拓展，当空间不足时，自动开辟。ArrayList会自动翻倍，但是vector不会翻倍，他会增加当前容量的一半。

vector v1;

cout << "v1初始化的容量：" << v1.capacity() << endl;
for (int i = 0; i < 30; i++)
{
	v1.push_back(i);
	cout << "v1加入" << i << "之后的容量为：" << v1.capacity() << endl;
}

输出： 

v1初始化的容量：0
v1加入0之后的容量为：1
v1加入1之后的容量为：2
v1加入2之后的容量为：3
v1加入3之后的容量为：4
v1加入4之后的容量为：6
v1加入5之后的容量为：6
v1加入6之后的容量为：9
v1加入7之后的容量为：9
v1加入8之后的容量为：9
v1加入9之后的容量为：13
v1加入10之后的容量为：13
v1加入11之后的容量为：13
v1加入12之后的容量为：13
v1加入13之后的容量为：19
v1加入14之后的容量为：19
v1加入15之后的容量为：19
v1加入16之后的容量为：19
v1加入17之后的容量为：19
v1加入18之后的容量为：19
v1加入19之后的容量为：28
v1加入20之后的容量为：28
v1加入21之后的容量为：28
v1加入22之后的容量为：28
v1加入23之后的容量为：28
v1加入24之后的容量为：28
v1加入25之后的容量为：28
v1加入26之后的容量为：28
v1加入27之后的容量为：28
v1加入28之后的容量为：42
v1加入29之后的容量为：42

容量扩增为当前容量的一半，1,2, 3,4, 6, 9, 13, 19, 28, 42。每次增加的都是前一刻的一半。 

vector通常，前端封闭，不允许前端插入，只允许尾插和尾删法。push_back()和pop_back()。front()代表容器中的第一个元素。back()是容器中最后一个元素。vector中有几个迭代器：

常用的是v.begin()：代表的是容器中的第一个元素的位置（迭代器指向第一个元素）。v.end()：指向容器中最后一个元素的下一个位置。v.rbegin()：指向容器中的最后一个元素，也就是从右边数第一个元素。v.rend()：指向第一个元素的前一个位置。从右侧数最后一个，即第一个。还有其他接口，比如：插入insert()以及删除erase()等。vector容器的迭代器是支持随机访问的迭代器。最强悍的迭代器：跳跃式访问。

函数原型：

vector v；                       // 采用模板实现类实现，默认构造函数vector(v.begin(), v.end())；  //将v[begin(), end())区间(前闭后开，包头不包尾)的元素拷贝给本身。vector(n, elem);                     //构造函数将n个elem拷贝给本身。vector(const vector& vec)   //拷贝构造函数。

注意第二个通过区间的方式构造，最后一个v.end()，如上图中所示，最后一个位置是取不到的。所以前闭后开，包头不包尾巴。

4种构造方法如下：

// 为了方便：我们写一个通用的打印vector类型的函数；
void printVector(vector& vec)
{
	for (vector::iterator it = vec.begin(); it !=vec.end(); it++)
	{
		cout << (*it) << " ";
	}
	cout << endl;
}

void test01()
{
	// 1、默认构造：无参构造
	vector v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);
	// 2、 通过区间的方式构造
	vector v2(v1.begin() + 1, v1.end() - 1);
	printVector(v2);

	// 3、将n个elem元素的方式构造
	vector v3(10, 100);   // 10个100；
	printVector(v3);

	// 4、拷贝构造
	vector v4(v2);
	printVector(v4);
}

函数原型：

vector& operator=(const vector &vec);//重载等号操作符

assign(v.begin(), v.end());         //将[begin, end)区间(也是前闭后开)中的数据拷贝赋值给本身。

assign(n, elem);                            //将n个elem拷贝赋值给本身。

也是两种方法：

一种是重载等号=操作符；一种是采用成员函数assign的方式。

void test02()
{
	// 声明+初始化；
	vector v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	// 赋值行为：
	
	// 第一种方式:直接等号。
	vector v2 = v1;
	printVector(v2);

	// 第二种方式:assign()
	vector v3;
	v3.assign(v1.begin(), v1.end());
	printVector(v3);

	// 第三种方式:
	vector v4;
	v4.assign(10, 100);    // 赋值方式。
	printVector(v4);
}

函数原型：

empty();                           //判断容器是否为空capacity();                     //容器的容量size();                              //返回容器中元素的个数resize(int num);             //重新指定容器的长度为num，

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

若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除

函数原型：

push_back(ele);                                        //尾部插入元素elepop_back();                                             //删除最后一个元素insert(const_iterator pos, ele);        //迭代器指向位置pos插入元素eleinsert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素eleerase(const_iterator pos);                     //删除迭代器指向的元素erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素clear();                                                        //删除容器中所有元素

void test01()
{
	vector v1;
	for (int i = 0; i < 5; i++)
	{
		v1.push_back(i * 10);
	}
	cout << "原始v1:";
	printVector(v1);

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

	cout << "头插入100:";
	printVector(v1);

	v1.insert(v1.begin(), 2, 10000);
	cout << "头插俩数：";
	printVector(v1);

	v1.erase(v1.begin());
	v1.erase(v1.begin(), v1.end());  // 全删了。不会打印任何东西。等效于clear();
	v1.clear();
}

注意：insert和erase要传入的参数是迭代器。

小结：

尾插 --- push_back

尾删 --- pop_back

插入 --- insert (位置迭代器)

删除 --- erase （位置迭代器）

清空 --- clear

函数原型：

at(int idx); //返回索引idx所指的数据  ：类似string容器。成员函数at。

operator[]; //返回索引 [idx] 所指的数据：类似string容器。

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

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

函数原型：

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

void printVector(int val)
{
	cout << val << " ";
}

void test01()
{
	vector v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	cout << "交换前v1:";
	for_each(v1.begin(), v1.end(), printVector);
	cout << endl;

	vector v2;
	for (int i = 10; i > 0; i--)
	{
		v2.push_back(i);
	}
	cout << "交换前v2:";
	for_each(v2.begin(), v2.end(), printVector);
	cout << endl;

	cout << "交换后：" << endl;
	v1.swap(v2);
	cout << "交换后v1:";
	for_each(v1.begin(), v1.end(), printVector);
	cout << endl;
	cout << "交换前v2:";
	for_each(v2.begin(), v2.end(), printVector);
	cout << endl;
}

输出：

交换前v1:0 1 2 3 4 5 6 7 8 9
交换前v2:10 9 8 7 6 5 4 3 2 1
交换后：
交换后v1:10 9 8 7 6 5 4 3 2 1
交换前v2:0 1 2 3 4 5 6 7 8 9

// 实际用途：巧用swap可以收缩内存空间。
void test02()
{
	vector v;
	for (int i = 0; i < 100000; i++)
	{
		v.push_back(i);
	}

	cout << "v的容量：" << v.capacity() << endl;
	cout << "v的大小：" << v.size() << endl;
	cout << "v的sizeof：" << sizeof(v) << endl;

	// v的容量：138255
	// v的大小：100000
	// v的sizeof：16
	v.resize(3);
	cout << "resize之后v的容量：" << v.capacity() << endl;
	cout << "resize之后v的大小：" << v.size() << endl;
	cout << "resize之后v的sizeof：" << sizeof(v) << endl;

	// resize之后v的容量：138255
	// resize之后v的大小：3
	// resize之后v的sizeof：16
	// 太浪费空间了。
	// 巧用swap来实现内存空间收缩。
	vector(v).swap(v);
	cout << "swap之后v的容量：" << v.capacity() << endl;
	cout << "swap之后v的大小：" << v.size() << endl;
	cout << "swap之后v的sizeof：" << sizeof(v) << endl;
	// swap之后v的容量：3
	// swap之后v的大小：3
	// swap之后v的sizeof：16
}

解析：

vector(v).swap(v);

这行代码中，有两个部分组成：

第一部分：vector(v)：调用拷贝构造函数利用v构造了一个新的对象这个对象不具名，匿名实现。会利用v目前所占用的内存空间来初始化。经过resize之后，v当前占用为3。第二部分：匿名对象调用swap函数，交换两个容器的元素。

匿名对象，依据当前v占用3个元素，匿名对象也占据3个元素，容量也为3，这样与v进行交换之后，实现了对v的内存压缩。

匿名对象执行完之后。立马由编译器回收。用完即删。不用担心占用内存。

总结：swap可以使两个容器互换，可以达到实用的收缩内存效果。

功能描述：

减少vector在动态扩展容量时的扩展次数

函数原型：

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

分配了内存，但是这块内存没有初始化，所以不可访问。

void test01()
{
	vector v1;
	int num = 0;
	int* p = NULL;
	for (int i = 0; i < 100000; i++)
	{
		v1.push_back(i);
		if (p != &v1[0])
		{
			p = &v1[0];
			num++;
		}
	}
	cout << "动态拓展容量的次数 num = " << num << endl;   // 动态拓展容量的次数。
}

动态拓展容量的次数 num = 30

十万数据，vector容量动态拓展30次，每一次拓展，都要把原来的数据重新开辟空间，然后将数据拷贝过去，然后把原空间释放。这样是对资源和效率的浪费。

所以有了预留空间。

假设我们需要预留的空间很大，而且可以预估我们需要的空间。那我们可以采用预留空间的方式，来提高效率。

void test01()
{
	vector v1;
	v1.reserve(100000);
	int num = 0;
	int* p = NULL;
	for (int i = 0; i < 100000; i++)
	{
		v1.push_back(i);
		if (p != &v1[0])
		{
			p = &v1[0];
			num++;
		}
	}
	cout << "动态拓展容量的次数 num = " << num << endl;   // 动态拓展容量的次数。
}

动态拓展容量的次数 num = 1