【C++】STL常用容器_deque容器

博主： Fivk
发布时间：2021 年 04 月 15 日
1343 次浏览
暂无评论
1512字数
分类： C/C++

# deque容器的基本

Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的
双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以
在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。

![](https://blog.fivk.cn/usr/uploads/2021/04/1234363700.png)

Deque容器和vector容器最大的差异，一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二
在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，"旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间"这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能.

虽然deque容器也提供了Random Access lterator,但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque.

# deque 容器实现原理

Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上(1)申请更大空间(2)原 数据复制新空间(3)释放原空间三步骤，如果不是vector每次配置新的空间时都留有余裕，其成长假象所带来的代价是非常昂贵的。
Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续
定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假
象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前
进后退操作颇为繁琐。Deque 代码的实现远比vector或list都多得多。
Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，
其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。

![](https://blog.fivk.cn/usr/uploads/2021/04/1577138239.png)

# deque 容器常用API

## 构造函数

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

```C++
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

void print(int a)
{
	cout << a << ' ';
}

int main()
{
	//一、deque<T> deqT;//默认构造形式
	deque<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(4);
	v1.push_front(5);//头插

deque<int>::iterator it = v1.begin();
	cout << "v1 = ";
	for_each(it, v1.end(), print);
	cout << endl;
	//二、deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
	deque<int> v3(v1.begin() + 1, v1.end());
	it = v3.begin();
	cout << "v3(v1.begin() + 1, v1.end() =  ";
	for_each(it, v3.end(), print);
	cout << endl;

//三、deque(n, elem);//构造函数将n个elem拷贝给本身。
	deque<int> v4(10, 8);
	it = v4.begin();
	cout << "deque<int> v4(10, 8) =  ";
	for_each(it, v4.end(), print);
	cout << endl;

//四、deque(const deque &deq);//拷贝构造函数。
	deque<int> v2(v1);
	it = v2.begin();
	cout << "deque<int> v2(v1) =  ";
	for_each(it, v2.end(), print);
	cout << endl;

return 0;
}
```

## 赋值操作

> assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
> assign(n, elem);//将n个elem拷贝赋值给本身。
> deque& operator=(const deque &deq); //重载等号操作符
> swap(deq);// 将deq与本身的元素互换

```C++
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

void print(int a)
{
	cout << a << ' ';
}

int main()
{
	deque<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(4);
	v1.push_front(5);//头插

deque<int>::iterator it = v1.begin();
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

//一、assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身
	deque<int> v2;
	v2.assign(v1.begin(), v1.end()-1);
	it = v2.begin();
	cout << "v2.assign(v2.begin(), v2.end()) = ";
	for_each(it, v2.end(), print);
	cout << endl;

//二、deque& operator=(const deque &deq); //重载等号操作符
	deque<int> v3;
	v3 = v1;
	cout << "v3 = ";
	for_each(v3.begin(), v3.end(), print);
	cout << endl;

//三、swap(deq);// 将deq与本身的元素互换
	v1.swap(v2);
	cout << "v1.swap(v2) :" << endl;
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;
	cout << "v2.assign(v2.begin(), v2.end()) = ";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;
	return 0;
}
```

![](https://blog.fivk.cn/usr/uploads/2021/04/3780999464.png)

## 大小操作

> deque.size();//返回容器中元素的个数
> deque.empty();//判断容器是否为空
> deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
> deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。

```C++
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

void print(int a)
{
	cout << a << ' ';
}

int main()
{
	deque<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_front(5);//头插

cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

//一、deque.size();//返回容器中元素的个数
	cout << "v1.size() = " << v1.size() << endl;

//二、deque.empty();//判断容器是否为空
	if (v1.empty()==NULL)
	{
		cout << "容器不为空" << endl;
	}
	else {
		cout << "容器为空" << endl;
	}

//三、deque.resize(num);//重新指定容器的长度为num,若容器变长，
	//则以默认值填充新位置。如果容器变短，
	//则末尾超出容器长度的元素被删除。

v1.resize(4);
	cout << "v1.resize(4):" << endl;
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

//三、deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，
	//则以elem值填充新位置,如果容器变短，
	//则末尾超出容器长度的元素被删除。

v1.resize(10, 8);
	cout << "v1.resize(10,8):" << endl;
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;
	return 0;
}
```

![](https://blog.fivk.cn/usr/uploads/2021/04/143902142.png)

## 双端的插入和删除

> push_back(elem);//在容器尾部添加一个数据
> push_front(elem);//在容器头部插入一个数据
> pop_back();//删除容器最后一个数据
> pop_front();//删除容器第一个数据

```C++
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

void print(int a)
{
	cout << a << ' ';
}

int main()
{
	deque<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_front(5);//头插

cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

//一、push_back(elem);//在容器尾部添加一个数据
	v1.push_back(520);
	v1.push_back(1314);

//二、push_front(elem);//在容器头部插入一个数据
	v1.push_front(666);
	v1.push_front(888);

//三、pop_back();//删除容器最后一个数据
	v1.pop_back();

//四、pop_front();//删除容器第一个数据
	v1.pop_front();

deque<int>::iterator it_strct = v1.begin();
	deque<int>::iterator it_end = v1.end();
	for (; it_strct != it_end; it_strct++)
	{
		cout << *it_strct << ' ';
	}
}
```

![](https://blog.fivk.cn/usr/uploads/2021/04/3203018805.png)

## 存取操作

> at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
> operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
> front();//返回第一个数据。
> back();//返回最后一个数据

```C++
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

void print(int a)
{
	cout << a << ' ';
}

int main()
{
	deque<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_front(5);//头插

//一、at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
	cout << "v1.at(2) = " << v1.at(2) << endl;

//二、operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
	v1[2] = 10;
	cout << "v1[2] = 10 :\n" << "v1[2] = " << v1[2] << endl;
	//三、front();//返回第一个数据。
	cout << "v1.front() = " << v1.front() << endl;

//四、back();//返回最后一个数据
	cout << "v1.back() = " << v1.back() << endl;

}
```

![](https://blog.fivk.cn/usr/uploads/2021/04/3092356124.png)

## 插入操作

> insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。pos是iterator类型
>
> insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。pos是iterator类型
> insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。pos是iterator类型

```C++
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

void print(int a)
{
	cout << a << ' ';
}

int main()
{
	deque<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_front(5);//头插

//一、insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
	v1.insert(v1.begin(), 10);
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

//二、insert(pos, n, elem);//在pos位置插入n个elem数据，无返回值。
	v1.insert(v1.begin(), 5, 4);
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

//三、insert(pos, beg, end);//在pos位置插入[beg,end)区间的数据，无返回值。
	deque<int> v2;
	v2.insert(v2.begin(), v1.begin(), v1.end());
	cout << "v2 = ";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;
}
```

![](https://blog.fivk.cn/usr/uploads/2021/04/3930889860.png)

## 容器的删除操作

> clear();//移除容器的所有数据
> erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。//区间的类型是iterator
> erase(pos);//删除pos位置的数据，返回下一个数据的位置。

```C++
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

void print(int a)
{
	cout << a << ' ';
}

int main()
{
	deque<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_front(5);//头插

cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;
	cout << "v1.size() = " << v1.size() << endl;

//一、clear();//移除容器的所有数据
	v1.clear();
	cout << "v1.size() for v1.clear = " << v1.size() << endl;

//恢复
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_front(5);//头插

//二、erase(beg, end);//删除[beg,end)区间的数据，返回下一个数据的位置。
	v1.erase(v1.begin() + 3, v1.end());
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;
	cout << "v1.size() = " << v1.size() << endl;

//三、erase(pos);//删除pos位置的数据，返回下一个数据的位置。
	//这里就不是区间了
	v1.erase(v1.begin()+1);
	cout << "v1 = ";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;
	cout << "v1.size() = " << v1.size() << endl;
}
```

# 案例

**有五名选手：选手A，B，C，D，E。10个评委分别对一名选手打分，去除最高分和最低分，取平均分。**

1. 创建五名选手，放到vector中
2. 遍历vector容器，取出每一个选手，执行for循环，可以把10个评分存放到deque容器中
3. deque容器遍历一遍，累加分数，平均分=累加分数/v.size()
4. person.scorc=平均分

```C++
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

class Person
{
public:
	char ch;
	double avg;
	vector<int> v;
};

bool cmp1(int a, int b)
{
	return a < b;
}

bool cmp2(Person a, Person b)
{
	return a.avg > b.avg;
}

int main()
{
	vector<Person> v;
	Person data;
	vector<int>::iterator it;
	vector<Person>::iterator it_start;
	int t;
	double sum = 0;
	for (int i = 1; i <= 5; i++)
	{
		cin >> data.ch;
		sum = 0;
			for (int j = 1; j <= 10; j++)
			{
				cin >> t;
				data.v.push_back(t);
			}
			sort(data.v.begin(), data.v.end(), cmp1);

for (it = data.v.begin()+1; it < data.v.end() - 1; it++)
			{
				sum += *it;
			}
			sum /= 8.0;
			data.avg = sum;
			v.push_back(data);
			data.v.clear();
	}

sort(v.begin(), v.end(), cmp2);

for (it_start = v.begin(); it_start != v.end(); it_start++)
	{
		cout << it_start->ch << ' ' << it_start->avg << endl;
	}

return 0;
}
```

其实也可以不输入名字，直接循环的时候赋值就好了。

![](https://blog.fivk.cn/usr/uploads/2021/04/693248507.png)

```C++
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <time.h>
#include <algorithm>
using namespace std;
class player
{
public:
	player() {}
	player(string  name, int score)
	{
		this->name = name;
		this->score = score;
	}
	string  name;
	int score;
};
void Init_player(vector<player> &v)
{
	string str = "ABCDE";
	for (int i = 0; i < 5; i++)
	{
		string strname(1, str[i]);// strname =  'A' 0   'B' 0
		player tmp(strname, 0);
		v.push_back(tmp);
	}
}
void print_player(vector<player> &v)
{
	for (vector<player>::iterator it = v.begin(); it != v.end(); it++)
	{
		//cout << it->name << " " << it->score << endl;
		cout << (*it).name << " " << (*it).score << endl;
	}

}
void start_play(vector<player> &v)
{
	srand((unsigned int)time(NULL));
	deque<int> d;
	for (vector<player>::iterator it = v.begin(); it != v.end(); it++)
	{
		// *it ==> player

for (int i = 0; i < 10; i++)
		{
			d.push_back(60 + rand() % 41);
		}
		//去除最高和最低
		sort(d.begin(), d.end());
		d.pop_back();
		d.pop_front();
		int sum = 0;
		/*for (int i = 0; i < d.size(); i++)
		{
		sum += d[i];
		}*/
		for (deque<int>::iterator it1 = d.begin(); it1 != d.end(); it1++)
		{
			sum += *it1;
		}
		int aver = sum / d.size();

it->score = aver;
		d.clear();

}

}
int  main()
{
	vector<player> v;
	Init_player(v);
	print_player(v);
	start_play(v);
	print_player(v);
	return 0;
}
```

最后修改：2021 年 04 月 16 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

【C++】STL常用容器_deque容器

Fivk • 2021 年 04 月 15 日