vector-序列式迭代器

Prpp

774人浏览 · 2025-08-12 17:23:14

Prpp · 2025-08-12 17:23:14 发布

1、vector容器

vector容器是STL最常用的容器之一，和arra容器很相似，但是array是静态数组，而vector实现的是一个动态数组，可以进行元素的插入和删除，在此过程中，vector会动态调整所占用的内存空间，整个过程无需人工干预。

vector--向量容器，该容器擅长在尾部插入或删除元素，时间复杂度为O(1),但是对于容器头部或者中部插入元素或删除元素则花费的时间较长，时间复杂度为线性阶O(n)。

1.1 创建vector容器的方式

（1）创建存储double类型元素的一个vector容器

std::vector<double>values;

这只是一个空的vector容器，因为容器中没有元素，没有为其分配空间。当添加第一个元素时，vector会自动分配内存。

（2）在创建好容器的基础上可以通过调用reserve()成员函数来增加容器的容量

values.reserve(20);

设置了容器的内存分配，至少可以容纳20个元素。

需要注意的是，如果调用reserve()来增加容器容量，之前创建好的任何迭代器都可能会失效，这是因为，为了增加容器容量，vector<T>容器的元素可能已经被复制或移到了新的内存地址，后续再使用这些迭代器的时候最好再重新生成一下。

（3）还可以在创建的同时指定初始值以及元素个数

std::vector<int> v{1,3,5,7,9};

（4）可以指定元素个数

std::vector<double> v(20);

这样容器开始时就有20个元素，它们的默认初始值都为0。

注意：（20）和 {20} 的区别，前者表示元素的个数，而后者表示容器只有一个元素20

（5）可以在指定元素个数的前提下，指定一个其他值

std::vector<int> v(20,6);

第一个参数指定了元素的个数，第二个参数指定了所有元素的初始值，都是6.

（6）也可以通过变量的方式表示

int num=20;
double v=1.0;
std::vector<double> v(num,v);

（7）简单实现一下vector容器的部分成员函数的功能

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	//初始化一个vector容器
	vector<char> v;
	//尾部插入字符
	v.push_back('S');
	v.push_back('T');
	v.push_back('L');
	//元素个数
	printf("元素个数为：%d\n",v.size());
	//使用迭代器遍历数组
	for (auto i = v.begin(); i < v.end(); i++)
	{
		cout << *i << " ";
	}
	cout << endl;
	//在开头插入字符
	v.insert(v.begin(), 'C');
	cout << "第一个元素为：" << v.at(0) << endl;
	return 0;
}

输出结果为：

元素个数为：3

S T L;

第一个元素为：C

2、 vector容器迭代器用法

vector容器支持迭代器的成员函数

（1）begin()和end()函数

begin()指向【首元素】，而end()指向【尾元素+1】

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int>v{ 1,2,3,4,5 };
	auto first = v.begin();
	auto end = v.end();
	while (first != end)
	{
		cout << *first << endl;
		first++;
	}
	return 0;
}

输出结果为：1 2 3 4 5

（2）反向迭代器rbegin()和rend()用于以逆序的方式遍历容器中的元素，将上列代码的第八第九行改为

auto first=v.rbegin()

auto end=v.rend()

那么结果输出为：5 4 3 2 1

（3）vector容器和array容器不同，前者可以随着存储元素的增加自行申请更多的存储空间，在创建vector对象时，可以直接创建一个空的vector容器，不会影响后续使用该容器

但是在初始化vector容器时，不能使用迭代器

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int>v{ 1,2,3,4,5 };
	int val = 1;

	for(auto first = v.begin(); first < v.end();first++,val++)
	{
		*first = val;
		cout << *first ;
		
	}
	return 0;
}

运行程序可知，什么也没有输出，所以说对于空的vector容器来说，begin()和end()成员函数返回的迭代器是相等的，他们指向的是同一个位置

所以对于空的vector来说，可以通过调用push_back()或者借助resize()成员函数实现初始化容器的目的

3、vector访问元素的方式

3.1 访问vector容器中单个元素

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int> v{ 1,2,3,4,5 };
	//获取首个元素
	cout << v[0] << endl;
	//修改容器下标为0的元素
	v[0] = v[1] + v[2] + v[3] + v[4];
	cout << v[0] << endl;
	return 0;
		
}

当用容器名[n]这种获取元素的方式，需要确保下标n的值不会超过容器的值，否则会发生越界访问的错误。

3.2 front()和back()

这两个成员函数分别返回vector容器种的第一个和最后一个元素的引用，通过利用这2个函数返回的引用，可以访问甚至修改容器种的首尾元素。

int main()
{
    vector<int> v{1,2,3,4,5};
    cout<<"首元素为："<<v.front()<<endl;
    cout<<"尾元素为："<<v.back()<<endl;
    //修改元素
    v.front()=10;
    v.back()=20;
    
    return 0;
}

3.2 data()

该函数的功能是返回指向容器种首个元素的指针，通过这个指针也可以访问甚至修改容器种的元素

int main()
{
  vector<int> v{1,2,3,4,5};
   //输出容器第三个元素
    cout<<*(v.data()+2)<<endl;
   //修改容器种第二个元素

    *(v.data()+2)=10;
    <<cout<<*(v.data()+1)<<endl;
   return 0;
}

3.3 访问vector容器中多个元素

（1）size()可以返回容器种实际存储的元素个数

for(int i=0;i<v.size();i++)
{
  cout<<v.[i]<<endl;
}

注意：capacity()返回的是容器的容量，不是实际存储元素的个数

（2）基于范围的循环

int main()
{
 vector<int> values{1,2,3,4,5}
 for(auto&& value:values)
  cout<<value<<" ";
   return 0;
}

（3）迭代器遍历

int main()
{
 vector<int> v{1,2,3,4,5};
 for(auto first=v.begin();first<v.end();first++)
  {  
     cout<<*first<<endl;
  } 
  return 0;
}

4、vector容器的底层实现机制

vector是使用3个迭代器来表示的：

//_Alloc 表示内存分配器，此参数几乎不需要我们关心
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;//指向的是vector容器对象的起始字节位置
    pointer _Mylast;//指向当前最后一个元素的末尾字节
    pointer _Myend;//指向整个容器所占用内存空间的末尾字节
};

如下图所示：

这就可以表示出一个已容纳2个元素，容量5的vector容器。

4.1 vector扩大容量的本质

当vector的大小和容量人相等，也就是满载的时候，如果再向其添加元素，那么vector就需要扩容

完全弃用现有的内存空间，重新申请更大的内存空间
将旧内存空间中的数据，按原有顺序移动到新的内存空间中
组后将旧的内存空间释放

4.2 vector添加元素

（1） push_back()

该成员函数的功能是在容器尾部添加一个元素

#include<iostream>
#include<vector>
using namspace std;
int main()
{  
 vector<int> v{ };
v.push_back(1);
v.push_back(2);
for(int i=0;i<v.size();i++)
 {
    cout<<v[i]<<endl;
    return 0;  
 }
}

（2）emplace_back()和push_back()

这两者的区别在于底层实现的机制不同，前者是直接在容器尾部创建这个元素，不需要拷贝或者移动元素，需要注意的是emplace()只能在容器中每次插入一个元素，不能多个。而后者向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）。

4.3 vector插入元素

（1）insert()

该成员函数功能是在容器的指定位置中插入一个或者多个元素

#include<iostream>
#include<vector>
#include<array>
using namespace std;
int  main()
{
	std::vector<int>v{ 1,2 };
	//在首元素之后插入元素3
	v.insert(v.begin() + 1, 3);  //{1,3,2}
	//在尾元素后插入元素2，5
	v.insert(v.end(), 2, 5); //{1,3,2,5,5}
	//定义一个含有三个元素的array容器
	std::array<int, 3>test{ 7,8,9 };
	//在vector容器的尾部元素中插入范围为test_begin()~test_end()的元素
	v.insert(v.end(), test.begin(), test.end()); //{1,3,2,5,5,7,8,9}
	//在vector容器尾部插入元素10，11
	v.insert(v.end(), { 10,11 });
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";

	}
	return 0;
}

运行结果为：1 3 2 5 5 7 8 9 10 11

4.4 vector删除元素

（1）pop_back()

该成员函数为删除容器的最后一个元素，该容器大小会减小，但容量不变

#include<iostream>
#include<vector>
#include<array>
using namespace std;
int  main()
{
	vector<int>v{ 1,2,3,4,5 };
	v.pop_back();
	cout << "size is:" << v.size() << endl;
	cout << "capacity is:" << v.capacity() << endl;
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}
	return 0;
}

（2）erase()

该成员函数功能为删除容器中指定位置处的元素

#include<iostream>
#include<vector>
using namespace std;
int  main()
{
	vector<int>v{ 1,2,3,4,5 };
	auto iter = v.erase(v.begin()+1);
	cout << "size is:" << v.size() << endl;
	cout << "capacity is:" << v.capacity() << endl;
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << *iter << endl;
	return 0;
}

运行结果为：

size is:4

capacity is:5

1 3 4 5 3

4.5 remove()

如果要删除容器中和指定元素相同的所有元素，可以使用remove()函数，该函数定义在<algorithm>头文件中

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int  main()
{
	vector<int>v{ 1,2,3,3,4,5 };
	//删除头元素到尾元素中包含3的元素
	auto iter = std::remove(v.begin(), v.end(), 3);
	cout << "size is:" << v.size() << endl;
	cout << "capacity is:" << v.capacity() << endl;
	for (auto first = v.begin(); first < iter; first++)
	{
		cout << *first << endl;
	}
	return 0;
}

size is:6

capacity is:6

运行结果为：1 2 4 5

可见，在对容器执行完remove()之后，由于该函数并没有改变容器原来的大小和容量，所以是无法使用之前的遍历方法来遍历容器，要借助remove返回的迭代器完成正确的遍历。

remove()实现的原理是：在遍历容器中的元素时，一旦遇到目标元素3，就做上标记，然后继续遍历，直到找到一个非目标元素4，用此目标元素4将最先做标记的位置3覆盖掉，同时将此非目标元素4所在的位置也做上标记，等待找到新的非目标元素将其覆盖，如果我们按照v[i]输出，得到的结果应该是{1,2,4,5,4,5}

我们可以用erase()来删除掉无用的元素，也就是在remove语句后面加上一条语句：

v.erase(iter,v.end());

5 vector去除多余容量

我们在使用vector容器中，容器会根据需要进行自动扩增，我们也可以用reserve()进行手动提升当前容器容量。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int  main()
{
	vector<int>v{};
	cout << "当前容器元素个数为：" << v.size() << "容量为：" << v.capacity() << endl;
	for (int i = 0; i <10; i++)
	{
		v.push_back(i);
	}
	cout << "存储10个元素后容器的元素个数为：" << v.size() << "容量为：" << v.capacity() << endl;
	v.reserve(1000);
	cout << "手动扩容后容器的元素个数为：" << v.size()  << "容量为：" << v.capacity() << endl;
	return 0;
}

运行结果为：

当前容器元素个数为：0 容量为：0

存储10个元素后容器的元素个数为：10 容量为：13

手动扩容后容器的元素个数为：10 容量为：1000

我们知道，vector模板类中也提供了pop_back(),erase(),clear()成员函数删除容器元素，但要注意，借助这些成员方法只能删除指定的元素，容器的大小在减少，容器的容量并不会因此改变。

5.1 shrink_to_fit()

因此提出该成员函数将容器当前的容量缩减至和实际存储元素的个数相等

v.shrink_to_fit();

cout<<"当前容器的元素个数为："<<v.size()<<“容量为：”<<v.capacity()<<endl;

运行结果为：当前容器的元素个数为：10 容量为：10

5.2 swap()

使用swap()的方法清空容器容量时，套用如下格式：

vector<T>().swap(x)

T--存储元素的类型；x--当前要操作的容器

int  main()
{
	vector<int>v{};
	v.reserve(1000);
	cout << "手动扩容后容器的元素个数为：" << v.size() << "容量为：" << v.capacity() << endl;
	v.shrink_to_fit();
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	vector<int>().swap(v);
	cout << "swap()后容器的元素个数为：" << v.size() << "容量为：" << v.capacity() << endl;
	return 0;
}

运行结果为：

手动扩容后容器的元素个数为：0 容量为：1000

swap()后容器的元素个数为：0；容量为：0