[C++知识库] C++经典问题

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> C++经典问题_20 STL(四) deque -> 正文阅读

[C++知识库]C++经典问题_20 STL(四) deque

文章目录

一. deque容器的基本概念

① 功能

双端数组,可以对收尾进行插入删除操作

② deque和vector的区别

vector对于头部的插入删除效率低,数据量越大,效率越低.
deque相对而言,对头部的插入和删除速度比vector快
vector访问元素时的速度比deque快,这和两者内部实现有关

③ deque的内部工作原理

deque内部有一个中控器,维护每段缓冲区中的内容,缓冲区中存放的是真实的数据
我们在操作的时候实际上操作的是中控器,然后中控器找到对应的地址,然后才访问的地址上的内容
中控器维护的每个缓冲区的地址,使得使用deque时像一片连续的内存空间
deque容器的迭代器也是支持随机访问的

二. deque的构造函数

deque<T> deq 默认构造
deque(begin,end); 构造函数将[begin,end]区间中的元素拷贝给本身
deque(n,elem); 构造函数将n个elem拷贝给本身
deque(const deque &deq); 拷贝构造函数

/*----------------------------------------------------------------
* 项目: Classical Question
* 作者: Fioman
* 邮箱: geym@hengdingzhineng.com
* 时间: 2022/3/22
* 格言: Talk is cheap,show me the code ^_^
//----------------------------------------------------------------*/

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

void print_deque(const deque<int> d)
{
	// 防止被修改
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		// 如果被修改就报错
		//*it = 100;
		cout << *it << " ";
	}
	cout << endl;
}

void test_deque(void)
{
	// 默认构造
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	print_deque(d1);

	// 使用区间构造
	deque<int> d2(d1.begin(), d1.end());
	print_deque(d2);

	// 构造函数将n个元素拷贝给自身
	deque<int> d3(10, 100);
	print_deque(d3);

	// 拷贝构造
	deque<int> d4(d3);
	print_deque(d4);
}
int main()
{
	test_deque();
	system("pause");
	return 0;
}

三. deque的赋值操作

deque& operator=(const deque& deq); // 重载等号操作符
assign(begin,end); // 将[begin,end]区间中的数据拷贝赋值给本身
assign(n,elem); // 将n个elem拷贝赋值给本身

/*----------------------------------------------------------------
* 项目: Classical Question
* 作者: Fioman
* 邮箱: geym@hengdingzhineng.com
* 时间: 2022/3/22
* 格言: Talk is cheap,show me the code ^_^
//----------------------------------------------------------------*/

#include <iostream>
using namespace std;
#include<deque>
void print_deque(const deque<int> &d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test_deque(void)
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_front(i);
	}
	print_deque(d1);

	// 1. 简单的赋值操作
	deque<int> d2 = d1;
	print_deque(d2);

	// 2. 使用assign(v.begin(),v.end())

	deque<int> d3;
	d3.assign(d2.begin(), d2.end());
	print_deque(d3);

	// 3. 将n个elm赋值给deque
	deque<int> d4;
	d4.assign(5, 10);
	print_deque(d4);
}

int main()
{
	test_deque();
	system("pause");
	return 0;
}

四. deque的容器大小操作

deque.empty(); 判断容器是否为空
deque.size(); 返回容器中元素的个数
deque.resize(num); 重新指定容器的长度为num,若容器变长,则以默认值填充新值.
如果容器变短,则末尾超出的长度元素被删除
deque.resize(num,elem); 重新指定容器的长度为num,若容器边长,则以elem填充新位置,
如果容器变短,则末尾超出容器长度的元素被删除.
deque容器是没有容量的概念的,可以无限的扩容,缓冲区可以一直开辟

/*----------------------------------------------------------------
* 项目: Classical Question
* 作者: Fioman
* 邮箱: geym@hengdingzhineng.com
* 时间: 2022/3/22
* 格言: Talk is cheap,show me the code ^_^
//----------------------------------------------------------------*/

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

void print_deque(const deque<int> d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test_01(void)
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_front(i);
	}
	print_deque(d1);

	if (d1.empty())
	{
		cout << "d1为空!" << endl;
	}
	else
	{
		cout << "d1不为空!" << endl;
		cout << "d1的size = " << d1.size() << endl;
	}

	// 更改size的大小,变大
	d1.resize(20); // 变成20,然后就是多出来的部分默认值填充一般为0
	print_deque(d1);

	d1.resize(30, 3); // 多出来的填充为3
	print_deque(d1);

	// 更改size的大小,变小
	d1.resize(10);
	print_deque(d1);
}
int main()
{
	test_01();
	system("pause");
	return 0;
}

五. deque插入和删除的操作

两端插入操作

push_back(elem); 在容器的尾部添加一个元素
push_front(elem); 在容器的头部插入一个元素
pop_back(); 删除容器的最后一个元素
pop_front(); 删除容器的第一个元素

指定位置操作:

insert(pos,elem); 在pos位置插入一个elem元素的拷贝,返回新数据的位置.
insert(pos,n,elem); 在pos位置插入n个elem,无返回值
insert(pos,begin,end); 在pos位置插入[begin,end]区间的数据,无返回值
clear(); 清空容器中的所有数据
erase(begin,end); // 删除[beg,end]区间中的所有的数据,返回下一个数据的位置
erase(pos); 删除pos位置的数据,放回下一个数据的位置.

/*----------------------------------------------------------------
* 项目: Classical Question
* 作者: Fioman
* 邮箱: geym@hengdingzhineng.com
* 时间: 2022/3/22
* 格言: Talk is cheap,show me the code ^_^
//----------------------------------------------------------------*/

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

void print_deque(const deque<int>& d)
{
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test_01(void)
{
	deque<int> d1;
	// 尾部插入
	d1.push_back(10);
	d1.push_back(20);

	// 头部插入
	d1.push_front(100);
	d1.push_front(200);
	print_deque(d1);

	// 删除头部
	d1.pop_front();
	// 删除尾部
	d1.pop_back();
	print_deque(d1);
}

void test_02(void)
{
	// 指定位置插入
	deque<int> d1;
	d1.push_back(10);
	d1.push_front(100);
	print_deque(d1); // 100 10

	// 指定位置插入
	d1.insert(d1.begin(), 1000);
	print_deque(d1); // 1000 100 10

	// 指定位置插入指定个数
	d1.insert(d1.begin(), 2, 3); 
	print_deque(d1);// 3 3 1000 100 10

	// 指定位置插入元素,这里的pos不能是简单的int类型,必须是begin() + 的形式
	d1.insert(d1.begin() + 1, 2);
	print_deque(d1); // 3 2 3 1000 100 10

	// 区间插入
	deque<int> d2;
	d2.push_back(0);
	d2.insert(d2.begin(), d1.begin(), d1.end()); 
	print_deque(d2);// 3 2 3 1000 100 10 0

	// 删除下标为2的第三个元素,也就是3
	d2.erase(d2.begin() + 2);
	print_deque(d2); // 3 2 1000 100 10 0

	// 删除中间的元素,只留下收尾
	d2.erase(d2.begin() + 1, d2.end() - 1);
	print_deque(d2); // 3 0
}	
int main()
{
	//test_01();
	test_02();
	system("pause");
	return 0;
}

六. deque的存取操作

at(int index); 返回索引为index所指的数据
operator[]; 返回索引index所指的数据
front(); 返回容器中第一个数据元素
back(); 返回容器中最后一个数据元素

/*----------------------------------------------------------------
* 项目: Classical Question
* 作者: Fioman
* 邮箱: geym@hengdingzhineng.com
* 时间: 2022/3/22
* 格言: Talk is cheap,show me the code ^_^
//----------------------------------------------------------------*/

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

void print_deque(const deque<int> &d)
{
	for (int i = 0; i < d.size(); i++)
	{
		cout << d[i] << " "; // 通过[]操作符访问
	}
	cout << endl;
}

void reverse_deque(deque<int> &d)
{
	deque<int> temp(d);
	d.clear();
	for (int i = 0; i < temp.size(); i++)
	{
		d.push_front(temp.at(i)); // 头部插入,然后就变成了逆序了
	}
}

void test_01(void)
{
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);
	print_deque(d);

	// 反转之前的第一个元素200 最后一个元素20
	cout << "反转之前的第一个元素: " << d.front() << " 最后一个元素: " << d.back() << endl;

	// 反转deque
	reverse_deque(d);
	print_deque(d);
	// 反转之后的第一个元素: 20 最后一个元素: 200
	cout << "反转之后的第一个元素: " << d.front() << " 最后一个元素: " << d.back() << endl;
}
int main()
{
	test_01();

	system("pause");
	return 0;
}

七. deque的排序

算法:
sort(iterator begin,iterrator end) 对[begin,end]区间内的元素进行排序

/*----------------------------------------------------------------
* 项目: Classical Question
* 作者: Fioman
* 邮箱: geym@hengdingzhineng.com
* 时间: 2022/3/22
* 格言: Talk is cheap,show me the code ^_^
//----------------------------------------------------------------*/

#include <iostream>
using namespace std;
#include<deque>
#include<algorithm>

void print_deque(const deque<int> &d)
{
	for (int i = 0; i < d.size(); i++)
	{
		cout << d[i] << " ";
	}
	cout << endl;
}

void test_01(void)
{
	deque<int> d;
	d.push_back(10);
	d.push_front(20);
	d.push_back(3);
	d.push_front(2);
	d.push_back(1);
	d.push_front(30);
	// 30 2 20 10 3 1
	print_deque(d);
	// 进行排序
	sort(d.begin(), d.end());
	// 排序后 1 2 3 10 20 30
	print_deque(d);

	d.push_back(4);
	d.push_front(40);

	// 对指定的区间进行排序
	sort(d.begin() + 1, d.end());
	// 排序后,首部并没有参与排序
	// 40 1 2 3 4 10 20 30 
	print_deque(d);
}

int main()
{
	test_01();
	system("pause");
	return 0;
}