【STL学习】（3）vector容器

前言

本章主要内容为两个部分：

vector是什么？
vector常用接口的使用。

一、vector的介绍

vector是表示可变大小数组的容器
就像数组一样，vector也采用的连续空间来存储元素。也意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质上，vector使用动态分配数组来存储它的元素。当新元素插入时，这个数组需要被重新分配大小。为了增加存储空间，其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因此每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因此存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其他动态序列容器相比（deque，list and forward_list），vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

vector的文档链接

二、vector常用接口的使用

1、vector是一个类模板，使用时需要显示实例化

在这里插入图片描述
tip：

vector有两个模板参数：
- T：元素的数据类型
- Alloc：空间配置器，用于定义存储分配模型的分配器对象的类型。默认情况下，使用allocator类模板，它定义了最简单的内存分配模型，并且与值无关。
空间配置器即内存池，STL中所有的容器都使用内存池，因为容器需要频繁申请和释放空间，为了提高效率，所以使用内存池。
allocator类模板，是库里面实现的一个默认分配器，如果没有指定最后一个模板参数，所有标准容器都将使用这个分配器，它是标准库中唯一的预定义分配器。
一般我们都使用库中的这个默认分配器，所以我们不需要显式实例化Alloc。
使用类模板，我们必须显式实例化。
类模板的显式实例化：类模板名字<实例化的类型>
显式模板参数实参与模板参数的匹配：
- 显式模板实参按由左至右的顺序与对应的模板参数匹配
- 第一个模板实参与第一个模板参数匹配，第二个实参与第二个参数匹配，以此类推。
- 注：只有尾部（最右）参数的显式模板实参才可以忽略，但前提是它们可以从函数参数推断出来或为缺省参数。

2、vector的构造函数

在这里插入图片描述

（construcort）构造函数声明	接口说明
explicit vector (const allocator_type& alloc = allocator_type());	默认构造函数，一般alloc空间配置器不用传参，使用缺省值。即无参构造
explicit vector (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());	构造并初始化n个val
vector (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());	使用迭代器进行初始化
vector (const vector& x);	拷贝构造

代码示例：

//vector的构造函数
void test_vector1()
{
	//1、无参构造
	vector<int> v1;//构造一个空的int类型的vector对象

	//2、构造并初始化n个val
	vector<char> v2(10, 'a');//构造一个char类型的vector，并且初始化10个字符'a'
	vector<char> v3(5);//构造一个char类型的vector，并且默认初始化5个字符

	//3、使用迭代器初始化
	//①使用自己类型的迭代器初始化
	vector<char> v4(v2.begin(), v2.end());
	//②使用其他类型的迭代器初始化
	vector<int> v5(v2.begin(), v2.end());
	//③连续存储空间的指针也属于迭代器
	int arr[] = { 1, 2, 3 };
	vector<int> v6(arr, arr + 3);

	//4、拷贝构造
	vector<int> v7(v6);
}

tip：

无参构造：一般使用最多
构造并初始化n个val：
- val为缺省参数，所以可以指定实参（使用指定的实参初始化），或不指定实参（使用缺省值）
- 值初始化： val不指定实参，库会创建一个值初始化的元素初值，把它赋个容器中的元素。这个初值由vector对象中元素的类型决定
- 如果vector对象的元素是内置类型，比如int，则元素默认初始化为0；char，则元素默认初始化为’\0’
- 如果元素是某种类类型，比如string，则元素由类默认初始化
使用迭代器初始化构造：
- InputIterator：模板参数，意味着你传什么类型的迭代器，他就实例化什么类型的迭代器初始化构造
- 连续存储空间的指针也是迭代器
- 迭代器区间：左闭合区间，[first,last)
拷贝构造：用一个已经存在的对象初始化另一个对象
类类型的隐式转换：
- 能通过一个实参调用的构造函数定义了一条从构造函数的参数类型向类类型隐式转换的规则
- 注：每次只能执行一种类类型的转换
- explicit修饰构造函数，禁止隐式类型转换

3、vector的遍历

接口名称	接口说明
operator[]	下标+[]，像数组一样可以随机访问
begin+end	获取第一个元素位置的iterator/const_iterator，获取最后一个元素的下一个位置的iterator/const_iterator
rbegin+rend	获取最后一个元素位置的reverse_iterator，获取第一个元素位置前一个位置的reverse_iterator
范围for	C++11支持的语法糖，只要支持迭代器就可以使用

代码示例：

//vector的遍历
void test_vector2()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);

	//1、operator[]——使用下标+[]
	for (size_t i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;
	
	//2、使用迭代器
	//①正向遍历
	auto vit = v1.begin();
	while (vit < v1.end())
	{
		cout << *vit << " ";
		vit++;
	}
	cout << endl;
	//①反向遍历
	auto rit = v1.rbegin();
	while (rit < v1.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;

	//3、有迭代器，就支持范围for
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

tip：

operator[]：
- operator[]越界是断言处理
- operator[]通常用两个版本：一个返回普通引用，另一个是类的常量成员并且返回常量引用，即一个可读可写版本，一个只可读不可写的版本。
- 函数重载调用，会走最匹配的
- 标准库类型限定使用的下标必须是size_t（内置类型的下标不是无符号类型）
迭代器：
- 迭代器是通用的，任何容器都支持迭代器并且用法类似
- 算法可以通过迭代器，去处理容器中的数据
范围for：C++11支持的语法糖，只要支持迭代器就可以使用（注：范围for底层被替换为begin和end，所以范围for只能正向遍历）

4、vector的容量操作

接口名称	接口说明
size	获取元素个数
capacity	获取容量大小
empty	判断是否为空
reserve	改变vector的capacity
resize	改变vector的size

（1）size&capacity&empty

void test_vector1()
{
	vector<int> v(10);//构造一个int类型的数组，并10个默认初始化的元素
	//获取vector对象的元素个数
	cout << v.size() << endl;
	//获取vector对象的容量
	cout << v.capacity() << endl;
	//判断vector对象是否为空
	cout << v.empty() << endl;

	//了解：max_size——判断当前vector对象可以容纳的最大元素数，在不同平台实现不一样，并无实际意义
	cout << v.max_size() << endl;
}

tip：

size：
- 获取vector中的元素个数的
- 注这是vector中实际对象的数量，不一定等于其存储容量
capacity：
- 获取当前为vector分配的存储空间，以元素表示
- capacity不一定等于size，它可以大于或等于
- capacity不是固定的，当此容量耗尽并需要更多容量时，vector会自动扩容
- 可以通过reserve显式改变capacity
empty：
- 判断是否为空，为空返回true，不为空返回false。（size=0即为空）
- 注：此函数不会以任何方式修改容器。要清空vector的内容，请使用clear
了解：max_size返回当前vector对象可以容纳的最大元素数，它是一个理论值，所以无实际意义

（2）reserve&resize

引入：reserve和resize

//测试vector的默认扩容机制
void test_vector2()
{
	vector<int> v;
	size_t sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed:" << sz << endl;
		}
	}
}

在这里插入图片描述

tip：

vector使用动态分配数组来存储它的元素，当这个数组的容量不够的时候，vector会自动扩容。
capacity的代码在VS和g++下分别运行会发现，VS下capacity是按1.5倍增长的，g++是按2倍增长的。 这个问题经常被考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。VS是PJ版本STL，g++是SGI版本STL。
扩容一般一次扩1.5倍或2倍，因为扩1.5倍或2倍是平衡的做法，单次扩容越多，插入N个元素，扩容次数越少，效率就越高，但是浪费空间；单次扩容越少，插入N个元素，扩容次数越多，效率就越低。

扩容是有代价的，所以vector中提供两个接口reserve和resize，可以避免多次扩容。

reserve：请求改变vector的容量

//如果已经确定vector中要存储元素的大概个数，可以提前将空间设置足够
//就可以避免插入数据多次扩容，导致的效率低下的问题
void test_vector3()
{
	vector<int> v;
	//已提前知道v中大概存储100个元素
	//所以可以提前将容量设置好，避免插入数据多次扩容
	v.reserve(100);
	//1、reserve只是单纯的开空间，不会影响字符串的长度和内容。
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	//2、观察是否避免了扩容
	size_t sz = v.capacity();
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed:" << sz << endl;
		}
	}

	//清空数据：删除所有元素，即size=0
	v.clear();
	//clear不会影响capacity
	cout << v.size() << endl;
	cout << v.capacity() << endl;
}

tip：

reserve请求改变vector的capacity：
- 如果 n 大于当前向量容量，则该函数会导致容器重新分配其存储，将其容量增加到 n（或更大）。
- 在所有其他情况下，函数调用不会导致重新分配，并且vector容量不受影响。
- 注意：reserve只是单纯开空间，不会影响vector的大小和内容。
clear清除内容：
- 删除vector中的所有元素，使size=0
- 注：clear不会影响vector的容量

resize：改变vector的size

void test_vector4()
{
	vector<int> v;
	//1、n>size&&n>capacity，开空间并初始化
	v.resize(100);
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	//2、n<size，删除超出的元素
	v.resize(10);
	cout << v.size() << endl;
	cout << v.capacity() << endl;
}

tip：

resize将容器大小调整为n：
- 如果 n 小于当前容器大小，则内容将减少到其前 n 个元素，删除超出的元素。
- 如果 n 大于当前容器大小，则通过在末尾插入所需数量的元素来扩展内容，以达到 n 的大小。如果指定了 val，则新元素将初始化为 val 的副本，否则，它们将进行值初始化。
- 注意：如果 n 也大于当前容器容量，则会自动重新分配分配的存储空间，会影响vector的容量；如果n<capacity，不会影响vector的容量。

5、vector的增删查改

接口名称	接口说明
push_back	尾插
pop_back	尾删
insert	在position之前插入val
erase	删除position位置的数据
find	查找（注意这个是算法模块实现，不是vector的成员接口）
sort	排序（注意这个也是算法模块实现，不是vector的成员接口）

（1）push_back&pop_back

void test_vector1()
{
	vector<int> v;
	//尾插1 2 3 4
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//尾删
	v.pop_back();
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

tip：

push_back：
- 尾插，在vector的末尾插入val
- 每一次尾插后size+1
- 当且仅当新的向量大小超过当前向量容量时，才会自动重新分配分配的存储空间。
pop_back：尾删，删除vector中的最后一个元素，尾删之后size-1
vector采用顺序表存储数据，所以vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作，效率更低。
所以vector没有专门头插头删的接口，但是有insert和erase。

（2）insert&erase

void test_vector2()
{
	int arr[] = { 8, 2, 3, 9, 7, 3, 5, 1, };
	vector<int> v(arr, arr + sizeof(arr) / sizeof(int));
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//头插一个10
	v.insert(v.begin(), 10);
	//在下标2元素之前插入2个1
	v.insert(v.begin() + 2, 2, 1);
	//尾插一个迭代器区间
	v.insert(v.end(), arr, arr + 2);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//头删
	v.erase(v.begin());
	//删除一个迭代器区间的元素
	v.erase(v.begin(), v.begin() + 3);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

tip：

insert：
- insert是重载函数，调用时编译器会找一个与实参最匹配的
- 在position位置的元素之前插入val
- 在position位置的元素之前插入n个val
- 在position位置的元素之前插入一个迭代器区间的元素
erase：
- erase是重载函数，调用时编译器会找一个与实参最匹配的
- 删除position位置的元素
- 删除迭代器区间的元素，注意迭代器区间为左闭合区间，即[first，last)
一般我们很少使用insert和erase，因为在尾部之外的位置插入或删除元素，效率低。

（3）find

说明：

vector中并没有find，这个find是算法（algorithm）中的。
STL中把容器（存数据）和算法（处理数据）分开的，通过迭代器将其关联。
算法中的find是一个函数模板，其功能是在一个迭代器区间[first，last)中查找一个值，找到了就返回它的迭代器（范围中与该值相等的第一个元素的迭代器），没找到就返回last。

void test_vector3()
{
	int arr[] = { 8, 2, 3, 9, 7, 3, 5, 1, };
	vector<int> v(arr, arr + sizeof(arr) / sizeof(int));
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//STL中容器和算法是分开的
	//容器存数据，算法处理数据
	//他们之间通过迭代器关联
	//例如：vector中没有find，但是算法中有，那我们可以通过迭代器将其关联
	auto pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		cout << "找到了" << endl;
		v.erase(pos);
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

（4）sort

vector中也没有sort，这个sort是算法（algorithm）中的。
STL中把容器（存数据）和算法（处理数据）分开的，通过迭代器将其关联。
这里我们只是简单介绍一下sort的使用，sort有两个版本：
- 版本1：默认升序（less <），对迭代器区间[first，last)升序
- 版本2：降序（>），需要自己再传一个仿函数，库中实现了greater，我们可以直接使用

void test_vector4()
{
	int arr[] = { 8, 2, 3, 9, 7, 3, 5, 1, };
	vector<int> v(arr, arr + sizeof(arr) / sizeof(int));
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//STL中容器和算法是分开的
	//容器存数据，算法处理数据
	//他们之间通过迭代器关联
	//例如：将vector的数据排序，可以使用算法中的sort
	//1、sort默认为升序(<)
	sort(v.begin(), v.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//1、sort降序(>)
	//①使用仿函数
	sort(v.begin(), v.end(), greater<int>());
	//②反向迭代器的升序，即降序
	//sort(v.rbegin(), v.rend());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

6、vector< char >可以替代string？

思考： vector的底层存储也是动态的顺序表，那vector能替代string吗？

不能，有如下几点原因：

从结构上，string为了兼容C在每一个string对象之后自动添加了一个’\0’字符，而vector< char >需要我们自己手动添加
从接口上，string提供了很多对字符串的专用接口，例如find，substr，+=……
string只能存储字符类型，而vector可以存储多种类型

总结：string和vector是两种最重要的标准库类型，各自有各自的价值，前者支持可变长字符串，后者则表示可变长的集合。

使用vector存储string：

void test_vector2()
{
	//vector是一个模版，只要有一个确定的类型，就可以将其实例化出来
	vector<string> v;

	//尾插string对象
	//1、先定义一个string对象
	string name = "张三";
	v.push_back(name);

	//2、匿名对象
	v.push_back(string("李四"));

	//3、隐式类类型的转换
	v.push_back("王五");

	for (auto e : v)
	{
		cout << e << endl;
	}
}

tip：

当函数参数类型为string类型时。有三种传参方式：
- 先创建一个string对象，再将string对象传过去
- 传string的匿名对象
- 直接转C字符串，隐式类类型转换为string
- 这三种传参方式，我们常常使用匿名对象
类类型隐式转换：
- 能通过一个实参调用的构造函数定义了一条从构造函数的参数类型向类类型隐式转换的规则
- 注意：编译器一次只能执行一种类类型的转换
- explicit修饰构造函数，禁止隐式类型转换
- 标准库中类含有单参数的构造函数：
  - 接收一个单参数的const char* 的string构造函数不是explicit
  - 接收一个容量参数的vector的构造函数是explicit
匿名对象：
- 匿名对象的生命周期在当前行
- 匿名对象具有常性
- const引用会延长匿名对象的生命周期，生命周期在引用对象的当前函数作用域
同一行一个表达式中连续的构造+拷贝构造，一般编译器会优化合二为一：
- 隐式类型转换传参，连续构造+拷贝构造——》优化为直接构造
- 匿名对象的传参，连续构造+拷贝构造——》优化为一个构造
- 接收非引用的自定义类型，连续拷贝构造+拷贝构造——》优化为一个拷贝构造
- 注意：一个表达式中，连续拷贝构造+赋值重载——》无法优化
- 建议在传参和接收非引用返回值等场景，使用连续构造，因为编译器会优化