跳至主要內容

STL顺序容器：vector、deque、list

张威大约 10 分钟c/c++STL

STL顺序容器：vector、deque、list

我们经常提到STL，那么STL究竟是什么呢？

STL：其英文全称为standard template libaray，即标准模板库。我们根据需要直接实例化这些模板，提高了我们使用的效率。

一、vector容器

。 容器中对象的构造析构，内存的开辟释放通过空间配置器allocator实现：allocate(内存开辟)、deallocate(内存释放)、construct(对象构造)、destroy(对象析构)。

1.1使用方式

使用方式：使用前需要包含：#include <vector> 1.增加： ①push_back()；//在容器末尾增加一个元素，时间复杂度O(1)，会导致容器扩容。 ②insert()；//在it迭代器指向的位置增加一个元素，时间复杂度O(n)，也会导致容器扩容。

2.删除： ①pop_back()；//在容器末尾删除一个元素，时间复杂度O(1)。 ②erase();//删除it迭代器指向的元素，时间复杂度O(n)。

3.查询： ①operator[]//数据下标的随机访问vec[5]，时间复杂度O(1)。 ②iterator//迭代器进行遍历，一定要考虑迭代器失效问题。 ③find,for_each//泛型算法。 ④foreach//C++11提供的语法糖，通过迭代器iterator来实现的。 注意： [迭代器失效的底层核心原理 | 张威的编程学习笔记 (gitee.io)](https://iszhwei.gitee.io/ccpp/05 运算符重载/迭代器失效的底层核心原理.html)

4.常用方法： ①size();//返回容器底层有效元素的个数。 ②empty();//判断容器是否为空。 ③reserve();//为vector预留空间，只给容器底层开辟指定大小空间并不添加新的元素。 ④resize();//扩容。不仅给容器底层开辟指定大小空间，还会添加新的元素。 ⑤swap();//两个容器进行元素交换。

1.2使用实例

实例1：对vector容器中元素遍历。

vector<int> vec;
for (int i=0; i<20; i++)
{
	vec.push_back(rand()%100 + 1);
}

//vec的operator[]运算符重载函数进行vector遍历
int size = vec.size();
for (int i=0; i<size; ++i)
{
	cout << vec[i] << " ";
}
cout << endl;

//迭代器进行遍历
auto it1 = vec.begin();
for (; it1!=vec.end(); ++it1)
{
	cout << *it1 << " ";
}
cout << endl;

实例2：把vec容器中所有偶数全部删除。

vector<int> vec;
for (int i=0; i<20; i++)
{
	vec.push_back(rand()%100 + 1);
}

//vec的operator[]运算符重载函数进行vector遍历
int size = vec.size();
for (int i=0; i<size; ++i)
{
	cout << vec[i] << " ";
}
cout << endl;

//把vec容器中所有偶数全部删除
auto it2 = vec.begin();
while (it2!=vec.end())
{
	if (*it2 % 2 == 0)
	{
		it2 = vec.erase(it2);
	}
	else
	{
		++it2;
	}
}

//迭代器进行遍历
auto it1 = vec.begin();
for (; it1!=vec.end(); ++it1)
{
	cout << *it1 << " ";
}
cout << endl;

实例3：在2删除的基础上，给vector容器中所有的奇数前面都添加一个小于1的偶数 例:44 45。

vector<int> vec;
for (int i=0; i<20; i++)
{
	vec.push_back(rand()%100 + 1);
}

//vec的operator[]运算符重载函数进行vector遍历
int size = vec.size();
for (int i=0; i<size; ++i)
{
	cout << vec[i] << " ";
}
cout << endl;

//把vec容器中所有偶数全部删除
auto it2 = vec.begin();
while (it2!=vec.end())
{
	if (*it2 % 2 == 0)
	{
		it2 = vec.erase(it2);
	}
	else
	{
		++it2;
	}
}

//迭代器进行遍历
auto it1 = vec.begin();
for (; it1!=vec.end(); ++it1)
{
	cout << *it1 << " ";
}
cout << endl;

//给vector容器中所有的奇数前面都添加一个小于1的偶数 例:44 45
for (it1=vec.begin(); it1!=vec.end(); ++it1)
{
	if (*it1 % 2 != 0)
	{
		it1 = vec.insert(it1, *it1-1);
		++it1;
	}
}

//迭代器进行遍历
it1 = vec.begin();
for (; it1!=vec.end(); ++it1)
{
	cout << *it1 << " ";
}
cout << endl;

实例4：reserve预留空间，只给容器底层开辟指定大小空间并不添加新的元素。 默认定义的vector底层为0，第一次插入从0变更为1，再变为2，4，8…一直进行扩容，代价十分高，使用初始的内存效率太低，我们若开始知道问题的数据量大小，即可使用reserve预留空间。

vector<int> vec;//默认定义的vector底层为0
vec.reserve(20);//给vector容器预留空间
cout << vec.empty() << endl;
cout << vec.size() << endl;

for (int i=0; i<20; i++)
{
	vec.push_back(rand()%100 + 1);
}
cout << vec.empty() << endl;
cout << vec.size() << endl;

输出结果: empty()是1为空，0为非空。我们发现刚开始为空，reserve(20)并没有为我们容器添加元素，只是为容器底层开辟空间，容器里面元素个数依旧是0。再添加20个元素的时候，不需要扩容了，效率提高。

实例5：。 resize()不仅给容器底层开辟指定大小空间，还会添加新的元素，元素值为0。

vector<int> vec;//默认定义的vector底层为0
vec.resize(20);
cout << vec.empty() << endl;
cout << vec.size() << endl;

for (int i=0; i<20; i++)
{
	vec.push_back(rand()%100 + 1);
}
cout << vec.empty() << endl;
cout << vec.size() << endl;

二、deque容器

2.1底层实现

。

我们来看一下deque容器基本结构： 其底层为动态开辟的二维数组。其有两个宏：MAP_SIZE，为2；QUE_SIZE，为，T为实际的类型。底层有2个维度，还有一个mapper指针，指向第一维的一维数组，默认大小为MAP_SIZE 2；第二维为动态开辟的QUE_SIZE的大小，例如：我们使用整型时会有1024个元素。 双端队列两端都可以做为队头与队尾，现在可以从队尾入，队尾出，也可以队头入，队头出；我们就简单画了一个方向。first与last处于最中间的位置，便于两头都预留足够的空间，每一边都可以进行插入。

deque容器内存的扩容方式： 当我们元素的不断增加，相应的指示位置向后移动，如图2；当元素入满时候，还要从last方向入队，已经没有空间了，就需要再开辟一个二维数组，last移动到第二行开始部分，如图2，3，4；当我们再继续添加元素时，发现满了，再想继续添加元素deque就需要扩容，此时需要扩容第一维了，按照2倍大小扩容为4，如图5，6；刚才的第二维移动到第一维中间部分(oldsize/2)，方便任何一边的元素改动。若需再次扩容，同理。

2.2使用方式

使用方式：使用前需要包含：#include <deque> 1.增加： ①push_back();//从末尾添加元素，时间复杂度O(1)，可能引起扩容。 ②push_front();//从首部添加元素，时间复杂度O(1)，可能引起扩容。vector中没有该方法，需要使用insert()，为O(n)。 ③insert();//迭代器指向的位置添加元素，时间复杂度O(n)。

2.删除： ①pop_back();//从末尾删除元素，时间复杂度O(1)。 ②pop_front();//从首部删除，时间复杂度O(1)。 ③erase();//迭代器指向的位置进行元素删除，时间复杂度O(n)。

3.查询： ①iterator//迭代器进行遍历，一定要考虑迭代器失效问题。

4.常用方法： ①size();//返回容器底层有效元素的个数。 ②empty();//判断容器是否为空。 ③resize();//扩容。不仅给容器底层开辟指定大小空间，还会添加新的元素。 ④swap();//两个容器进行元素交换。 使用实例与vector类似

三、list容器

list：链表容器，底层数据结构为双向循环链表。使用方式：使用前需要包含：#include <list> 与deque使用方式一模一样，只是有的地方时间复杂度不同。 1.增加： ①push_back();//从末尾添加元素，时间复杂度O(1)，可能引起扩容。 ②push_front();//从首部添加元素，时间复杂度O(1)，可能引起扩容。vector中没有该方法，需要使用insert()，为O(n)。 ③insert();//迭代器指向的位置添加元素，时间复杂度O(1)。往往链表进行insert()时，要先进行query()操作，效率就慢了。

2.删除： ①pop_back();//从末尾删除元素，时间复杂度O(1)。 ②pop_front();//从首部删除，时间复杂度O(1)。 ③erase();//迭代器指向的位置进行元素删除，时间复杂度O(1)。

3.查询： ①iterator//迭代器进行遍历，一定要考虑迭代器失效问题。

4.常用方法： ①size();//返回容器底层有效元素的个数。 ②empty();//判断容器是否为空。 ③resize();//扩容。不仅给容器底层开辟指定大小空间，还会添加新的元素。 ④swap();//两个容器进行元素交换。 使用实例与vector类似。

四、vector、deque、list对比分析

容器使用场景：

deque底层内存是否是连续的？

不是，deque底层是动态开辟的二维数组空间，第二维都是独立开辟的空间，每一个第二维是连续的，但所有的二维不是连续的。

vector与deque容器之间的区别：

vector特点： 底层是一个动态开辟的数组，内存是连续的，2倍的方式进行扩容。当我们默认定义一个vector时候，容器底层没有开辟空间，当添加元素时候才从：0-1-2-4-8…进行扩容，扩容效率低。reserve函数可以预留空间，并未添加元素。deque特点： 区别： 1.底层数据结构：vector底层是一个动态开辟的数组，内存是连续的；deque底层是动态开辟的二维数组空间，内存不连续。 2.前中后删除元素的时间复杂度：它们中间与末尾插入删除一样为O(1)，但最前面进行元素添加时候deque为O(1)，vector为O(n)。 3 4.

vector与list容器之间的区别：

vector特点： 底层是一个动态开辟的数组，内存是连续的，2倍的方式进行扩容。当我们默认定义一个vector时候，容器底层没有开辟空间，当添加元素时候才从：0-1-2-4-8…进行扩容，扩容效率低。reserve函数可以预留空间，并未添加元素。 list特点： 底层是一个双向循环链表。

区别:即数组与链表区别 数组增加删除为O(n)，查询O(n)，随机访问为O(1)；链表增加删除一个结点本身为O(1)，但搜索的时间为O(n)。如果增加删除使用多，优先使用list；随机访问使用多，优先使用vector。

Copyright © 2024 张威