[数据结构与算法]vector类（动态数组）——STL

vector

向量（动态数组），内存的分配原理跟string是一样的，是连续的空间，如果空间不够用，会申请一个更大的连续的空间，同时迭代器失效

区别于array，array是一个数组，容量固定。

• 需要添加头文件：#include <vector>

定义vector对象

定义一个int类型的向量

无参构造
	vector<int> vec ; 
	vector<int> vec2 ;
	
有参构造，含有5个元素
	vector<int> vec1(5);
	
有参构造，初始化，5个40
	vector<int> vec2(5, 40);
	
拷贝构造
	vector<int> vec3(vec1);

定义vector的迭代器

	vector<int>::iterator ite;
	<>中是参数列表， string则没有
	本质就是int* 指针，char 就是char*指针

迭代器初始化

	vector<int> vec2(5, 40);
	
	vector<int>::iterator ite = vec2.begin();
	vector<int>::iterator ite1 = vec2.end();

• begin()，指向头
• end()，指向尾巴的下一个

注意：vector的下标运算符例如a[1]，只能在以存在的数据中查找，或者修改已存在的值，不能进行赋值运算

vector容量

• 无参初始化，容量就为0
• 有参初始化，有几个元素，容量就为几
• 新增数据，容量不够时增加现有容量的一半。比如现有10个，新的就是15个（10+10/2=15），现有13个；增加13/2==6个，就是19个
• 但是新增数据时，容量的变化，不同的编译器，容量变化不同可以试验一下
• push_back实在数组后面追加一个元素

	vector<int> vec;
	cout << vec1.capacity() << endl;
	
	vector<int> vec1(5);
	cout << vec1.capacity() << endl;  //为5

	vec1.push_back(1); // 追加一个元素 
	cout << vec1.capacity() << endl; //5+5/2 == 7

	vec1.push_back(1);
	vec1.push_back(1); //7 + 7/2 == 10
	

修改容量

• 关键词：reserve()

• 修改容量，不能变小，只能变大

• 设置多大就是多大

	vector<int> vec;
	vec.resize(3);

• size()，元素个数

• resize()，重新设置元素个数

• 缩小时容量不变，放大时容量改变，缩小的时候，字符串的长度可能会被截短

• 判断对象是否有元素empty()
  为空就返回0，不为空显示1

重新分配容量后，迭代器失效

vector的操作

添加元素

1. 尾添加

void push_back( const TYPE &val );

	vec.push_back(2);

2. 中间添加

在指定迭代器的位置加入一个数据
：iterator insert( iterator loc, const TYPE &val );

	再迭代器vec下标为2，的位置添加元素12
	原数据整体向后移
	vec.insert(vec.begin()+2 , 12);

在某个迭代器后加入num个值为value的元素
：void insert( iterator loc, size_type num, const TYPE &val );

	再迭代器vec下标为2的位置，添加5个12
	vec.insert(vec.begin()+2, 5 , 12 );

在某个迭代器后加入另一个向量的中间一段
：void insert( iterator loc, input_iterator start, input_iterator end );

	vector<int> vec(8,4);
	vector<int> vec1(5,1);

	在vec下标为3的位置，添加vec1中从头开始的三个元素，下标为0，1，3
	vec.insert(vec.begin()+3, vec1.begin(), vec1.begin()+3);

区别

• 由于是数组，尾添加效率非常高，不考虑重新增加空间
• 中间添加的效率很低

查找

全部输出

1. 循环添加，然后用下标法输出

	for (int i = 0; i < 10; i++)  //[]
	{
		vec.push_back(i);
	}

	for (int i = 0; i < 10; i++)
	{
		cout << vec[i] << endl;
	}

2. 迭代器输出

	vector<int> vec;
	vector<int>::iterator ite = vec.begin();
	for_each(vec.begin(), vec.end(), fun);

单个输出

1. 下标运算

	cout << vec[i] << endl;

2. at()

	cout << vec.at(i) << endl;

• at区别于下标的好处是，当下标越界的时候，at会抛出异常，但是下标方法会直接崩溃

3. back()返回尾巴的元素

	cout << vec.back();

删除

尾删除

void pop_back();

	vec.pop_back();

删除指定元素

1. 删除一个： iterator erase( iterator loc );

	删除下标为3的元素
	vec.erase(vec.begin()+3);

2. 删除一段：iterator erase( iterator start, iterator end );

	删除下标从3开始到最后的所有元素
	vec.erase(vec.begin()+3, vec.end());

3. 删除所有：void clear();

修改

用下标运算修改

交换

void swap( vector &from );

	交换连个迭代器的内容
	vec.swap(vec1);

运算符重载

算法

需要添加头文件：#include <algorithm>

排序

• 关键词：sort()，默认从小到大排序
• 添加greater<数据类型>()，指定从大到小排序

可以把整个迭代器排序，也可以拍迭代器中的一段

	vector<int> vec;
	vec.push_back(8);
	vec.push_back(51);
	vec.push_back(11);
	vec.push_back(4);
	vec.push_back(0);
	vec.push_back(10);
	vec.push_back(18);
	
	将下标从2到5的元素，从小到大排序
	sort(vec.begin()+2 , vec.begin()+5)
	将所有元素从大到小排序
	sort(vec.begin(), vec.end(), greater<int>());

随机打乱顺序

	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(4);
	vec.push_back(5);
	
	会将上面的vec随机打乱顺序输出，但是当运行多次都是第一次打乱顺序的次序
	random_shuffle(vec.begin(), vec.end());

想要让每次运行出现的值不一样，需要添加一个系统时间time(),这是需要添加一个ctime头文件。

	srand((unsigned int)time(0));

	random_shuffle(vec.begin(), vec.end());

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖