目录

deque容器基本概念

 一、构造函数

二、赋值操作

三、大小操作

四、插入和删除

五、数据存取

六、排序操作

评委打分系统 

---

deque容器基本概念

功能：双端数组，头尾都能进行插入删除操作

与vector的区别:

1.vector对于头部的插入删除效率低，数据越多，效率越低

2.deque对头部删除插入的速度快，效率高

3.vector访问内部元素时的速度比deque快

注：图片来自STL源码剖析

 这是一个双端队列，deque的内部实现很复杂，依靠中控器管理多个缓冲区

依靠相当复杂的迭代器实现，我还没这个能力去实现

 一、构造函数

打印函数

void printDeque(deque<int>&d)//可用const_iterator限定只读
{
	/*for (deque<int>::const_iterator i = d.begin(); i != d.end(); i++)
		cout << *i << " ";
	cout << endl;*/
	for (auto i : d)
		cout << i << " ";
	cout << endl;
}

auto可自动推导类型，用const_iterator可防止数据被修改 

可采用无参构造，指定迭代器区间构造，指定个数的元素赋值，以及拷贝构造

void test01()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
		d1.push_back(i);
	printDeque(d1);
	deque<int>d2(d1.begin(), d1.end());
	printDeque(d1);
	deque<int>d3(7, 3);
	printDeque(d1);
	deque<int>d4(d3);
	printDeque(d1);
}

二、赋值操作

void test02()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
		d1.push_back(i);
	printDeque(d1);
	deque<int>d2;
	d2 = d1;
	printDeque(d2);
	deque<int>d3;
	d3.assign(d1.begin(), d1.end());
	printDeque(d3);
	deque<int>d4;
	d4.assign(7, 3);
	printDeque(d4);
}

 赋值可采用重载=号运算符以及使用assign函数

三、大小操作

void test03()
{
	deque<int>d1;
	for (int i = 0; i < 10; i++)
		d1.push_front(i);
	printDeque(d1);
	if (d1.empty())
		cout << "d1为空" << endl;
	else
		cout << "d1不为空，大小为" << d1.size() << endl;
	d1.resize(5);//缩小舍去多余元素
	printDeque(d1);
	d1.resize(15, 7);//扩大并初始化新开辟的空间
	printDeque(d1);
}

deque没有容量的概念，可以不断从两端开辟空间的。因此没有reserve预开辟空间，resize指定空间大小。

四、插入和删除

void test04()
{
	deque<int>d1, d2;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_front(10);
	d1.push_front(20);
	d2 = d1;
	printDeque(d1);
	d1.pop_back();
	d1.pop_front();
	printDeque(d1);
	d2.insert(d2.begin(), 2333);
	printDeque(d2);
	d2.insert(d2.begin(), 3, 7);
	printDeque(d2);
	deque<int>d3;
	d3.push_back(1);
	d3.push_back(2);
	d3.push_back(3);
	d2.insert(d2.begin(),d3.begin(), d3.end());
	printDeque(d2);
 
	d2.erase(d2.begin()+1);
	printDeque(d2);
	d2.erase(d2.begin(), d2.end()-1);
	printDeque(d2);
	d2.clear();
	printDeque(d2);
}

 deque可以头插尾插，也可以头删尾删，insert插入有三种

1、向指定位置插入一个数据

2、向指定位置插入n个数据

3、将某一deque对象的某一区间数据插入到该deque对象的某一位置后面

此外erase删除函数，删除单个或指定区间的数据

clear函数清空所有数据

五、数据存取

void test05()
{
	deque<int>d;
	d.push_back(1);
	d.push_back(2);
	d.push_back(3);
	d.push_front(1);
	d.push_front(2);
	d.push_front(3);
	for (int i = 0; i < d.size(); i++)
		cout << d[i] << " ";
	cout << endl;
	for (int i = 0; i < d.size(); i++)
		cout << d.at(i) << " ";
	cout << endl;
	d.pop_back();
	cout << d.front() << endl;
	cout << d.back() << endl;
}

重载[]，使用at方法访问deque容器存储的数据 

六、排序操作

void test06()
{
	deque<int>d;
	d.push_back(1);
	d.push_back(10);
	d.push_back(100);
	d.push_front(1000);
	d.push_front(500);
	d.push_front(250);
	printDeque(d);
	//对支持随机访问的迭代器都可用sort函数进行排序
	sort(d.begin(), d.end());
	printDeque(d);
	
}

对支持随机访问的迭代器都可用sort函数进行排序，sorth函数需要引用头文件algorithm

sort默认从小到大排序，可以使用重载版本，传入第三个参数——自定义比较函数的地址，即函数名，设置排序依据。

评委打分系统 

目的功能：有5名选手ABCDE，有10名评委对其打分，去掉一个最高分和一个最低分，再取平均分作为其成绩。

#include<iostream>
#include<deque>
#include<vector>
#include<algorithm>//sort排序算法
#include<string>
#include<time.h>//生成随机成绩，设置时间戳
#include<iomanip>//设置打印格式
using namespace std;
class Participant//创建参赛者类
{
	string m_name;
	double m_grade;
public:
	Participant(string name, double grade=0)//将成绩初始化为0
	{
		this->m_grade = grade;
		this->m_name = name;
	}
	void setScore(double grade)
	{
		this->m_grade = grade;
	}
	double getSore()
	{
		return this->m_grade;
	}
	string getName()
	{
		return this->m_name;
	}
};
void setParticipant(vector <Participant>&v)//设置参赛者名字
{
	string t_name = "ABCDE";
	for (int i = 0; i < 5; i++)
	{
		string name = "选手";
		name += t_name[i];
		Participant p(name);
		v.push_back(p);
	}
}
void printList(vector<Participant>&v)//打印
{
	for (auto i : v)
		cout << "姓名:" << i.getName() << "\t成绩:" << fixed << setprecision(2) << i.getSore()<<endl;//设置打印格式，保留两位小数
}
int main()
{
	srand((unsigned int)time(NULL));//时间戳，设置有效随机数
	vector<Participant>v;
	setParticipant(v);
	for (vector<Participant>::iterator i=v.begin();i!=v.end();i++)
	{
		deque<double>d;//创建deque
		double sum = 0;
		for (size_t i = 0; i <10; i++)
			d.push_back(rand() % 41 + 60);//用deque存入随机成绩(60~100)
		sort(d.begin(), d.end());//排序
		d.pop_back();//去掉最高分
		d.pop_front();//去掉最低分
		for (size_t i = 0; i < d.size(); i++)
			sum += d[i];
		i->setScore(sum /d.size());//传入平均成绩
	}
	printList(v);
	return 0;
}

 

不同容器适用于不同要求和目的。