vector介绍

1. vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好

vector使用

本文介绍的是vector的部分常用接口，大佬们想了解更多关于vector类的细节，一定要请前往官方文档（点击跳转）查阅学习！

1. 默认成员函数

vector的成员变量就是三个指针

template<class T>
class vecotr
{
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;
};

其中，_start指向空间起始位置，_finish指向最后一个有效元素的下一个位置，_end_of_storage指向已开辟空间的终止位置

1.1 默认构造

vector支持三种默认构造

1. 默认构造大小为0的对象
2. 构造n个值为value的对象
3. 通过迭代器区间构造自定义元素类型

int main()
{
	vector<int> v1; //构造值为int的对象
	vector<char> v2(12, 'c'); //构造12个值为c的对象
	string s = "happ";
	vector<char> v3(s.begin(), s.end()); //构造s区间内的元素对象
	vector<int> v4 = { 4,1,2 }; //调用了拷贝构造
	return 0;
}

1.2 拷贝构造

拷贝构造：通过拷贝原有对象，来创建新的相同值的对象

int main()
{
	vector<int> v1 = { 1,2,3 };
	vector<int> v2(v1);
	return 0;
}

1.3 析构函数

析构函数：释放动态开辟的的空间，由于vector对象的空间是连续的，释放时直接delete[] _start即可

内部主要代码：

delete[] _start;
_start = _finish = _end_of_storage = nullptr;

析构函数会在对象生命周期结束时自动调用，平时使用vector时无需担心

1.4 赋值重载

赋值重载：对原有对象的值进行重写

int main()
{
	vector<int> v1 = { 1,2,3 };
	vector<int> v2; //空对象
	v2 = v1; //将v1的值赋给v2
	return 0;
}

赋值重载函数有返回值，也适用于连续赋值

vector<int> v1;
vector<int> v2;
vector<int> v3 = { 4,1,2 };
v2 = v1 = v3; //将v3赋值给v1，v2

2. 迭代器

迭代器的出现使得各种各样的容器都能以同一种方式访问数据，vector和string的迭代器本质上就是原生指针，与之相比其他容器的迭代器就比较复杂了，后面都会一一介绍

迭代器分为三类：

• 单向迭代器：只支持单向操作
• 双向迭代器：支持双向移动
• 随机迭代器：支持双向移动，还能指定移动长度

string和vector的迭代器就是随机迭代器，可以随意指定移动

2.1 正向迭代器

正向迭代器用于从前往后遍历容器中的数据

开始位置：

结束位置：

这里begin()是第一个有效元素的地址，end()是最后一个有效元素的下一个地址

int main()
{
	const char* pa = "hello world";
	vector<char> v1(pa, pa + strlen(pa)); //迭代器构造
	vector<char>::iterator it = v1.begin(); //创建迭代器
	while (it != v1.end())
	{
		cout << *it;
		it++;
	}
	return 0;
}

注意：

使用迭代器遍历数据时，结束条件要写 it != v.end()，而不能写成 it < v.end()，因为对于有些容器的空间不是连续的，如list，这时判断小于就是错误的！

vector是随机迭代器，所以支持随机访问遍历

auto it = v.begin() + 6; //auto自动推导类型，随机位置开始遍历

2.2 反向迭代器

反向迭代器用于从后往前遍历容器中的数据

开始位置：

结束位置：

这里rbegin()是对象中最后一个有效元素的地址，rend()是对象中

int main()
{
	const char* ps = "happy new year";
	vector<char> v1(ps, ps + strlen(ps));
	vector<char>::reverse_iterator rit = v1.rbegin();
	while (rit != v1.rend())
	{
		cout << *rit;
		rit++;
	}
	return 0;
}

3. 容量操作

3.1 获取空间数据

• size()接口：获取有效数据大小
• capacity()接口：获取空间容量大小
• empty()接口：判空

指针 - 指针 = 两个指针间的元素个数

int main()
{
	vector<int> v1 = { 4,1,2,8,8,8 };
	cout << "size: " << v1.size() << endl;
	cout << "capacity: " << v1.capacity() << endl;
	cout << "empty: " << v1.empty() << endl;
	return 0;
}

3.2 空间扩容

reserve()接口：vector对象空间扩容

int main()
{
	vector<int> v1;
	cout << "capacity: " << v1.capacity() << endl;
	v1.reserve(88);
	cout << "capacity: " << v1.capacity() << endl;
	return 0;
}

当n < capacity时，reserve()接口不会进行任何操作

下面来看一段代码，观察vector在VS下和Linux下的扩容机制

int main()
{
	vector<int> v1;
	size_t capacity = v1.capacity();
	cout << "capacity:" << capacity << endl;
	int i = 0;
	while (i < 100)
	{
		v1.push_back(12); //尾插
		//不相等则说明发生了扩容
		if (capacity != v1.capacity())
		{
			capacity = v1.capacity();
			cout << "capacity:" << capacity << endl;
		}
		i++;
	}
	return 0;
}

观察上面的运行结果可以看出，VS下采用的是1.5倍扩容法，Linux下采用的是2倍扩容法，当所需容量较小时，VS采用的方法更浪费空间，而所需容量较大，Linux采用的方法更浪费空间。

如果知道所需内存进行提前扩容，两种版本所申请的容量就是一样的，且不会造成过多的内存碎片，达到节约空间的效果

3.3 大小调整

resize()接口：调整vector对象大小（调整_finish位置）

第二个参数val是缺省值，为对应对象的默认构造值，如int的默认构造为0

int main()
{
	vector<int> v1;
	v1.resize(12); //使用缺省值
	vector<int> v2;
	v2.resize(12, 8); //使用指定值
	return 0;
}

resize和reserve都能起到扩容的效果，二者的区别在于：

• resize扩容的同时还能起到初始化的效果，而reserve不能
• resize会改变_finish的位置，而reserve不会
• 当n < capacity时，resize会将size初始化到capacity空间

3.4 空间缩容

shrink_to_fit()接口：对vector对象的空间进行缩容

这个接口的缩容步骤是：首先开辟一个容量小于原空间的新空间，然后将原空间的数据转移到新空间，超出的部分就丢弃，最后释放原空间，完成缩容

缩容的代价和风险都是很大的，官方文档上都加了一个警告标志，不推荐使用此接口

4. 数据访问

由于vector是连续的空间，所以不仅可以通过迭代器遍历，还能通过下标随机访问

4.1 下标随机访问

下标随机访问的原理就是operator[]运算符重载

int main()
{
	const char* pb = "happy";
	vector<char> v1(pb, pb + strlen(pb)); //迭代器区间构造
	const vector<char> cv1(pb, pb + strlen(pb)); //迭代器区间构造
	size_t pos = 0; //下标
	while (pos < v1.size())
	{
		cout << v1[pos]; //访问普通对象
		//cout << v1.at(pos); //与上一条等价
		pos++;
	} 
	cout << endl;
	size_t _pos = 0; //下标
	while (_pos < cv1.size())
	{
		cout << cv1[_pos]; //访问const对象
		_pos++;
	}
	return 0;
}

这里的at方法也可以起到遍历访问的功能，它实际上就是对operator[]的封装

4.2 获取首尾元素

front()接口：获取首元素

back()接口：获取结尾元素

int main()
{
	vector<int> v1 = { 4,1,2 };
	cout << "front: " << v1.front() << endl;
	cout << "back: " << v1.back() << endl;
	return 0;
}

front() 返回的就是 *_start，back() 返回的就是 *_finish

5. 数据修改

5.1 尾插尾删

push_back()尾插接口和pop_back()尾删接口，都是老朋友了，下面直接演示用法

int main()
{
	vector<int> v1 = { 4,1,2 };
	v1.push_back(6);
	vector<int>::iterator _it = v1.begin();
	while (_it != v1.end())
	{
		cout << *_it;
		_it++;
	}
	_it = v1.begin();
	cout << endl;
	v1.pop_back();
	while (_it != v1.end())
	{
		cout << *_it;
		_it++;
	}
	return 0;
}

5.2 任意位置插入删除

insert()接口：任意位置插入

erase()接口：任意位置删除

下面还是直接来演示用法

int main()
{
	int _arr[] = { 8,8,8 };
	vector<int> v1 = { 1,2 };
	//在指定位置前插入一个值（找不到默认尾插）
	v1.insert(find(v1.begin(), v1.end(), 2), 6); //1 6 2
	//在指定位置前插入n个值
	v1.insert(find(v1.begin(), v1.end(), 6), 3, 7); //1 7 7 7 6 2
	//在指定位置前插入一段迭代器区间（数据中有相同的数时默认在第一次找到的该数前插入）
	v1.insert(find(v1.begin(), v1.end(), 7), _arr, _arr + (sizeof(_arr[0]) - 1)); //1 8 8 8 7 7 7 6 2
	//删除指定位置的元素
	v1.erase(find(v1.begin(), v1.end(), 1)); //8 8 8 7 7 7 6 2
	//删除一段区间
	v1.erase(v1.begin() + 1, v1.end()); //8
	return 0;
}

这里还有一个迭代器失效的场景：

int main()
{
	vector<int> v = { 4,1,2 };
	auto it = v.end();
	for (int i = 0; i < 5; i++)
	{
		v.insert(it, 10);
		it++; //再次使用迭代器会发生失效
	}
	return 0;
}

在进行插入或删除操作后，由于没有及时更新，可能会导致迭代器的指向位置失效

具体原因和解决方案我会在下篇模拟实现中讲解

5.3 交换和清理

swap()接口：交换

clean()接口：清理

int main()
{
	vector<int> v1 = { 1,2,3 };
	vector<int> v2 = { 4,5,6 };
	vector<int> v3 = { 7,8,9 };
	v1.swap(v2); //交换v1、v2
	v3.clear();  //清理v3
	return 0;
}

这里有个问题，std 中已经提供了全局的 swap 函数，为什么vector中还要再提供一个呢？

• std::swap在交换时，需要调用多次拷贝构造和赋值重载函数，是深拷贝，用于vector中效率是很低的
• vector::swap 在交换时，是交换三个成员变量，由于都是指针，只需要三次浅拷贝，就能很高效的完成任务

---

C++【STL】之vector的使用，到这里就介绍结束了，本篇文章对你由帮助的话，期待大佬们的三连，你们的支持是我最大的动力！

文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正！