Wiki

deque container

Updated 2023-10-05About 11 min read

Existing English translations were reused. 1 current source blocks remain in Simplified Chinese, without triggering paid translation.

1.deque container

1.1.Basic concepts of deque container

Function:

Double-ended array, allowing insertion and deletion operations at the head end

Differences between deque and vector:

vector has low efficiency for insertion and deletion at the head, and the larger the data volume, the lower the efficiency.
deque, relatively speaking, is faster than vector for insertion and deletion at the head.
vector is faster than deque when accessing elements, which is related to the internal implementation of the two.

说明: 2015-11-19_204101

Internal working principle of deque:

Inside the deque, there is acentral controllerthat maintains the contents of each buffer segment, and the buffers store the actual data.

The central controller maintains the address of each buffer, making the use of a deque resemble a contiguous memory space.

clip_image002-1547547896341

The iterator of a deque container also supports random access.

1.2.deque constructor

Function description:

deque container construction

Function prototype:

deque<T> deqT; //Default constructor form
deque(beg, end); //The constructor copies the elements in the range [beg, end) to itself.
deque(n, elem); //The constructor copies n copies of elem to itself.
deque(const deque &deq); //Copy constructor

Example:

#include <iostream>
#include <deque>

using namespace std;

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

	}
	cout << endl;
}
//deque构造
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(d2);

	deque<int>d3(10,100);
	printDeque(d3);

	deque<int>d4 = d3;
	printDeque(d4);
}

int main() {

	test01();


	return 0;
}

Operation result:

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100

**Summary:** The construction methods of the deque container and the vector container are almost the same; just use them flexibly as needed.

1.3.deque assignment operation

Function description:

Assign values to the deque container

Function prototype:

deque& operator=(const deque &deq); // Overload the assignment operator
assign(beg, end); // Copy and assign the data in the interval [beg, end) to itself.
assign(n, elem); // Copy and assign n copies of elem to itself.

Example:

#include <iostream>
#include <deque>

using namespace std;

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

	}
	cout << endl;
}
//赋值操作
void test01()
{
	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(10, 100);
	printDeque(d4);

}

int main() {

	test01();


	return 0;
}

Operation result:

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
100 100 100 100 100 100 100 100 100 100

Summary: The deque assignment operation is also the same as that of vector and must be mastered proficiently.

1.4.deque size operations

Function description:

Operate on the size of the deque container

Function prototype:

deque.empty(); //Determine whether the container is empty
deque.size(); //Return the number of elements in the container
deque.resize(num); //Respecify the length of the container as num. If the container becomes longer, fill the new positions with the default value.

//If the container becomes shorter, the elements at the end beyond the container length are deleted.
deque.resize(num, elem); //Respecify the length of the container as num. If the container becomes longer, fill the new positions with the value elem.

//If the container becomes shorter, the elements at the end beyond the container length are deleted.

Example:

#include <iostream>
#include <deque>

using namespace std;

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

	}
	cout << endl;
}

//大小操作
void test01()
{
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	//判断容器是否为空
	if (d1.empty()) {
		cout << "d1为空!" << endl;
	}
	else {
		cout << "d1不为空!" << endl;
		//统计大小
		cout << "d1的大小为：" << d1.size() << endl;
	}

	//重新指定大小
	d1.resize(15, 1);
	printDeque(d1);

	d1.resize(5);
	printDeque(d1);
}

int main() {

	test01();


	return 0;
}

Operation result:

0 1 2 3 4 5 6 7 8 9
d1不为空!
d1的大小为：10
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1
0 1 2 3 4

Summary:

deque does not have the concept of capacity
Check whether it is empty --- empty
Return the number of elements --- size
Respecify the number of elements --- resize

1.5.deque insertion and deletion

Function description:

Insert and delete data in a deque container

Function prototype:

Double-ended insertion operation:

push_back(elem); // Add a data element at the end of the container
push_front(elem); // Insert a data element at the beginning of the container
pop_back(); // Delete the last data element of the container
pop_front(); // Delete the first data element of the container

Position-specific operation:

insert(pos,elem); // Insert a copy of the element elem at position pos, returning the position of the new data.
insert(pos,n,elem); // Insert n copies of elem at position pos, no return value.
insert(pos,beg,end); // Insert the data in the range [beg,end) at position pos, no return value.
clear(); // Clear all data from the container
erase(beg,end); // Delete the data in the range [beg,end), returning the position of the next data.
erase(pos); // Delete the data at position pos, returning the position of the next data.

Example:

#include <iostream>
#include <deque>

using namespace std;

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

	}
	cout << endl;
}
//两端操作
void test01()
{
	deque<int> d;
	//尾插
	d.push_back(10);
	d.push_back(20);
	//头插
	d.push_front(100);
	d.push_front(200);

	printDeque(d);

	//尾删
	d.pop_back();
	//头删
	d.pop_front();
	printDeque(d);
}

//插入
void test02()
{
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);
	printDeque(d);

	d.insert(d.begin(), 1000);
	printDeque(d);

	d.insert(d.begin(), 2,10000);
	printDeque(d);

	deque<int>d2;
	d2.push_back(1);
	d2.push_back(2);
	d2.push_back(3);

	d.insert(d.begin(), d2.begin(), d2.end());
	printDeque(d);

}

//删除
void test03()
{
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);
	printDeque(d);

	d.erase(d.begin());
	printDeque(d);

	d.erase(d.begin(), d.end());
	d.clear();
	printDeque(d);
}

int main() {

	//test01();

	//test02();

    test03();
    

	return 0;
}

Operation result:

200 100 10 20
100 10 20

Summary:

The positions provided for insertion and deletion are iterators!
Push back --- push_back
Pop back --- pop_back
Push front --- push_front
Pop front --- pop_front

1.6.deque data access

Function description:

Access operations on data in a deque

Function prototype:

at(int idx); // Return the data indicated by index idx
operator[]; // Return the data indicated by index idx
front(); // Return the first data element in the container
back(); // Return the last data element in the container

Example:

#include <iostream>
#include <deque>

using namespace std;

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

	}
	cout << endl;
}

//数据存取
void test01()
{

	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);

	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;

	cout << "front:" << d.front() << endl;

	cout << "back:" << d.back() << endl;

}

int main() {

	test01();


	return 0;
}

Operation result:

200 100 10 20
200 100 10 20
front:200
back:20

Summary:

除了用迭代器获取deque容器中元素，[ ]和at也可以
front返回容器第一个元素
back返回容器最后一个元素

1.7.deque sort

Function description:

Use an algorithm to sort the deque container.

Algorithm:

sort(iterator beg, iterator end) //Sort the elements within the range [beg, end)

Example:

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

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

	}
	cout << endl;
}

void test01()
{

	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_front(100);
	d.push_front(200);

	printDeque(d);
	sort(d.begin(), d.end());
	printDeque(d);

}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

	test01();


	// 返回 0 表示程序正常结束。
	return 0;
}

Operation result:

200 100 10 20
10 20 100 200

Summary: The sort algorithm is very practical; to use it, simply include the header file algorithm.

2.Case - Judge Scoring

2.1.Case Description

There are 5 contestants: Contestants A, B, C, D, and E. Ten judges score each contestant individually. The highest score is removed, and the lowest score among the judges is removed, then the average score is taken.

2.2.Implementation Steps

Create five contestants and put them into a vector
Traverse the vector container, take out each contestant, and execute a for loop to store 10 scores into a deque container
Use the sort algorithm to sort the scores in the deque container, and remove the highest and lowest scores
Traverse the deque container once and accumulate the total score
Obtain the average score

Example code:

#include <iostream>

using namespace std;

//选手类
class Person
{
public:
	Person(string name, int score)
	{
		this->m_Name = name;
		this->m_Score = score;
	}

	string m_Name; //姓名
	int m_Score;  //平均分
};

void createPerson(vector<Person>&v)
{
	string nameSeed = "ABCDE";
	for (int i = 0; i < 5; i++)
	{
		string name = "选手";
		name += nameSeed[i];

		int score = 0;

		Person p(name, score);

		//将创建的person对象 放入到容器中
		v.push_back(p);
	}
}

//打分
void setScore(vector<Person>&v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		//将评委的分数 放入到deque容器中
		deque<int>d;
		for (int i = 0; i < 10; i++)
		{
			int score = rand() % 41 + 60;  // 60 ~ 100
			d.push_back(score);
		}

		//cout << "选手： " << it->m_Name << " 打分： " << endl;
		//for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		//{
		//	cout << *dit << " ";
		//}
		//cout << endl;

		//排序
		sort(d.begin(), d.end());

		//去除最高和最低分
		d.pop_back();
		d.pop_front();

		//取平均分
		int sum = 0;
		for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum += *dit; //累加每个评委的分数
		}

		int avg = sum / d.size();

		//将平均分 赋值给选手身上
		it->m_Score = avg;
	}

}

void showScore(vector<Person>&v)
{
	for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "姓名： " << it->m_Name << " 平均分： " << it->m_Score << endl;
	}
}

int main() {

	//随机数种子
	srand((unsigned int)time(NULL));

	//1、创建5名选手
	vector<Person>v;  //存放选手容器
	createPerson(v);

	//测试
	//for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
	//{
	//	cout << "姓名： " << (*it).m_Name << " 分数： " << (*it).m_Score << endl;
	//}

	//2、给5名选手打分
	setScore(v);

	//3、显示最后得分
	showScore(v);


	return 0;
}

Run results (random numbers may vary with the runtime environment; the following is an example from one run):

姓名： 选手A 平均分： 78
姓名： 选手B 平均分： 72
姓名： 选手C 平均分： 86
姓名： 选手D 平均分： 81
姓名： 选手E 平均分： 86

Summary: Selecting different container operations can improve code efficiency.