vector讲解

ahao

发布于 2024-03-19 19:13:19

650

发布于 2024-03-19 19:13:19

文章被收录于专栏：学习

在学习玩string后我们开始学习vector，本篇博客将对vector进行简单的介绍，还会对vector一些常用的函数进行讲解

vector的介绍

实际上vector就是一个数组的数据结构，但是vector是由C++编写而成的，他和数组也有本质上的区别，但也有相同点，他的特征概括如下：

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

对于C语言中的数组，二者有很多的异同点，我将其概括如下：

相同点：
1 二者都是采用连续的空间来存储元素
2 二者都能通过下标进行访问
不同点：
1 vector是采用动态开辟，容器大小可以动态改变，并且是自动处理
2vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大

vector的使用

vector的定义

vector的定义就差不多是初始化以及拷贝构造和构造，这些在之前的string类函数讲解中也提到了，其实都大差不差的

构造并初始化： 第一个参数是你要初始化元素的个数，第二个参数是你要初始化成的字符这里需要注意**<>里面就是你要放入vector里元素的类型**

vector<int> v(10, 1);
for (auto ch : v)
{
	cout << ch;
}
cout << endl;

拷贝构造： 其实都大差不差，学习了前面的string和类和对象后都很简单了

	vector<int> v(10, 1);
	vector<int> v1(v);
	for (auto ch : v1)
	{
		cout << ch;
	}
	cout << endl;

vector iterator 的使用

迭代器很常用，咱们做个简单的讲解

迭代器同样地分为正向和反向：我们可以通过一个简单的代码来了解迭代器的使用

vector<int> v;
for (int i = 1; i <= 5; i++)
{
	v.push_back(i);
}
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout<< ' ' << *it;
}
cout << endl;

下面为反向迭代器：反向迭代器记得加上reverse

vector<int> v;
for (int i = 1; i <= 5; i++)
{
	v.push_back(i);
}
for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); it++)
{
	cout<< ' ' << *it;
}
cout << endl;

关于begin和rbegin，end和rend的位置的关系如下图所示，我们要记得，两种迭代器都是从begin开始遍历：通过这张图，我们需要注意到一个很重要的点： 迭代器的区间都是左闭右开的！所以end是在最后一个元素的后一个位置！

vector 空间增长问题

其实空间增长问题我在之前的string类就有提到过，都是有规律可循的： 1 capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。vector增容都是2倍，具体增长多少是根据具体的需求定义 2 reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。 3 resize在开空间的同时还会进行初始化，影响size

可以看到，resize默认就是初始化为0：同时改变了capacity和size

而reserve只改变了capacity，并且不会有初始化的功能：

vector<int> v;
v.reserve(10);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout<< ' ' << *it;
}
cout << endl;
cout << "former:" << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
v.reserve(20);
cout << endl;
cout << "after:" << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;

vector 增删查改

pushback尾插和popback尾删：

都很简单，拿一段简单的代码来演示一下吧：

vector<int> v;
v.resize(10,1);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout<< ' ' << *it;
}
cout << endl;
v.push_back(2);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;
v.pop_back();
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;

insert插入函数： 这里如果需要在其他地方插入就在begin上进行+操作

vector<int> v;
v.resize(10,1);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout<< ' ' << *it;
}
cout << endl;
vector<int>::iterator it = v.begin();
v.insert(it, 3);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;

erase函数： erase函数可以根据下标索引来删除元素，但是再insert后要重新给下标赋值，insert前的下标i已经失效了，其实这就是所说的：迭代器失效问题！

在这里我们插入了元素后会发生扩容，原空间可能已经被释放了（或者说如果erase删除了最后一个位置的元素，vector里已经没有元素可以删除，也会导致迭代器失效），但是erase后我们又使用it打印，这里的it可能使用的就是原空间，程序就会发生崩溃，所以我们需要在执行完insert后再次对it进行赋值，不然就会发生这种情况（但是一些编译器对于迭代器失效没有过于严格的检查，所以程序不会崩溃，但是程序输出的结果不对）：

erase函数返回的是在vector对象中删除元素的后一个元素的指针！

通常解决迭代器失效最简单的方法就是： 对迭代器重新赋值

vector<int> v;
v.resize(10,1);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout<< ' ' << *it;
}
cout << endl;
vector<int>::iterator i = v.begin();
v.insert(i+3, 3);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;
i = v.begin();
v.erase(i+3);
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;

swap函数： 我们通过一段简单的代码来了解一下：我们交换前打印两个vector对象中的元素，交换后再打印一次

vector<int> v1;
v1.resize(10,1);
cout << "交换前" << endl;
cout << "v1:";
for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
{
	cout<< ' ' << *it;
}
cout << endl;
vector<int> v2;
v2.resize(10, 2);
cout << "v2:";
for (vector<int>::iterator it = v2.begin(); it != v2.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;
v1.swap(v2);
cout << "交换后" << endl;
cout << "v1:";
for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;
cout << "v2:";
for (vector<int>::iterator it = v2.begin(); it != v2.end(); it++)
{
	cout << ' ' << *it;
}
cout << endl;