当前位置：首页 > article >正文

C++系列-STL容器之deque

article 2024/11/16 15:23:24

STL容器之deque

deque概括
- deque与vector内存管理的区别
- - vector内存分配方式
  - deque内存分配方式
- deque与vector随机访问效率的区别
- deque与vector插入和删除操作的区别
- deque与vector适用场景
deque的构造函数
- deque的构造函数举例
deque的赋值操作
deque容器的大小操作
deque容器的插入和删除
- 两端插入和删除
- 指定位置
- 删除操作
deque容器的数据存取
deque容器排序

deque概括

deque是一种序列容器。
deque维护双端数组，头尾都可以直接插入和删除操作。

deque与vector内存管理的区别

vector内存分配方式

vector采用连续的线性内存空间，当需要增加容量时，通常会重新分配一块更大的连续内存空间，并将原有元素复制到新空间，然后释放旧空间。这可能会导致较高的时间开销，特别是当容器中元素数量较大时。

deque内存分配方式

deque有一系列固定大小的块组成，这些块可以在不连续的内存空间中，deque这些固定大小的块称为缓冲区。
在两端进行插入或删除操作时，deque可以更高效的管理内存，不像vector那样进行大量的元素移动。
为了有效的管理这些缓冲区，deque使用中控器(通常是指针数组)的结构，中控器记录每个缓冲器的地址和大小，以及deque的当前size和capacity。
当在deque的两端插入操作时，如果当前的存储块还有足够的空间，新元素就会被插入到相应的空间，否则，deque会分配一个新的缓冲区，并将其添加到合适的位置。
当deque在中间进行插入或删除操作时，deuqe调整涉及到的缓冲区中的元素，并可能需要重新分配或释放一些存储块。

deque与vector随机访问效率的区别

vector支持高效的随机访问。
也支持随机访问，但是由于其内部结构的复杂性，随机访问的效率略低于vector。

deque与vector插入和删除操作的区别

vector在尾部插入和删除操作通常是高效的。但在头部或中部插入和删除操作需要移动大量元素。
在两端插入和删除数据都非常高效。在中间插入和删除的效率相对较低，但是比vertor在中间进行插入和删除的操作要快。

deque与vector适用场景

vector适用于需要高效的随机访问和在尾部进行频繁插入和删除的场景。例如，存储一组整数并进行频繁的遍历和在尾部添加元素。
deque适用于在两端进行高效插入和删除的场景，例如，实现一个队列或栈结构。或者在容器的两端进行频繁的插入和删除操作。

deque的构造函数

默认构造函数，创建一个新的deque。

deque<T> d1;

拷贝构造函数，从一个deque对象创建一个副本。

deque<T> d2(const vector<T> &d1);

使用迭代器范围构造函数，从两个迭代器指定的范围创建deque。

deque<T> d2(obj.begin(), obj.end());

将n个elem拷贝给deque

deque<T> d1(n, elem);

deque的构造函数举例

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

void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{
	for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	int num = 0;
	deque<int> d1;			// 默认构造函数
	d1.push_front(11);
	d1.push_front(22);
	d1.push_front(33);
	cout << "---------- 默认构造函数举例 ----------" << endl;
	print_deque(d1);
	
	d1.push_back(666);
	deque<int> d2(d1);			// 拷贝构造函数
	cout << "---------- 拷贝构造函数举例 ----------" << endl;
	print_deque(d2);

	deque<int>d3(10, 888);		// n个elem初始化举例
	cout << "---------- n个elem初始化构造函数举例 ----------" << endl;
	print_deque(d3);

	deque<int>d4{1, 2, 3, 4, 5, 6, 7, 8, 9};	// 花括号初始化
	cout << "---------- 花括号初始化构造函数举例 ----------" << endl;
	print_deque(d4);

	deque<int>d5(d4.begin(), d4.end()-3);
	cout << "---------- 迭代器范围初始化构造函数举例 ----------" << endl;
	print_deque(d5);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- 默认构造函数举例 ----------
33 22 11
---------- 拷贝构造函数举例 ----------
33 22 11 666
---------- n个elem初始化构造函数举例 ----------
888 888 888 888 888 888 888 888 888 888
---------- 花括号初始化构造函数举例 ----------
1 2 3 4 5 6 7 8 9
---------- 迭代器范围初始化构造函数举例 ----------
1 2 3 4 5 6

deque的赋值操作

= 赋值，函数原型 deque& operator=(const deque&vec), 重载等号运算符。
deq1.assign(beg迭代器，end迭代器), 将[beg迭代器，end迭代器) 之间的数据拷贝给被赋值的对象。
deq1.assign(n，elem), 将n个elem的数据拷贝给被赋值的对象。

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

void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{
	for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	int num = 0;
	deque<int> d1;			// 默认构造函数
	d1.push_front(11);
	d1.push_front(22);
	d1.push_front(33);

	cout << "---------- =赋值 ----------" << endl;
	deque<int> d2 = d1;
	print_deque(d2);

	deque<int> d3;
	cout << "---------- deq.assign(n, elem)赋值 ----------" << endl;
	d3.assign(5, 555);
	print_deque(d3);

	deque<int> d4;
	d3.push_back(666);
	cout << "---------- deq.assign(deq)赋值 ----------" << endl;
	d4.assign(d3.begin(), d3.end());
	print_deque(d4);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- =赋值 ----------
33 22 11
---------- deq.assign(n, elem)赋值 ----------
555 555 555 555 555
---------- deq.assign(deq)赋值 ----------
555 555 555 555 555 666

deque容器的大小操作

没有capacity，因为它的容量是动态的，随时扩展。
| 函数原型 | 用途 |
|:--------😐 :-------------|
|empty()| 判断容器是否为空|
|size() | 返回容器中元素的个数|
|resize(int num) | 重新指定容器的长度(size)为num，若容器变长，则以默认数值填充新位置，如果容器变短，则末尾超出容器长度的元素被删除|
|resize(int num，elem) | 重新指定容器的长度(size)为num，若容器变长，则以elem填充新位置，如果容器变短，则末尾超出容器长度的元素被删除|

code:

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

void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{
	for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	int num = 0;
	deque<int> d1;
	d1.push_front(11);
	d1.push_front(22);
	d1.push_front(33);
	deque<int> d2;

	if (!d1.empty())
	{
		cout << "d1 is not empty" << endl;
		cout << "d1 size: " << d1.size() << endl;
	}
	if (d2.empty())		// 判断容器是否为空
	{
		cout << "d2 is empty" << endl;
	}

	deque<int> d3 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};	// 花括号初始化
	cout << "---------- d3 ----------" << endl;
	print_deque(d3);
	cout << "d3 size: " << d3.size() << endl;

	d3.resize(12);		// resize，默认填充0
	cout << "---------- d3.resize(12) ----------" << endl;
	print_deque(d3);
	cout << "d3 size: " << d3.size() << endl;

	d3.resize(15, 666);	// resize，填充指定数据
	cout << "---------- d3.resize(15, 666) ----------" << endl;
	print_deque(d3);
	cout << "d3 size: " << d3.size() << endl;

	d3.resize(5);		// resize，长度截短
	cout << "---------- d3.resize(5) ----------" << endl;
	print_deque(d3);
	cout << "d3 size: " << d3.size() << endl;
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
d1 is not empty
d1 size: 3
d2 is empty
---------- d3 ----------
0 1 2 3 4 5 6 7 8 9
d3 size: 10
---------- d3.resize(12) ----------
0 1 2 3 4 5 6 7 8 9 0 0
d3 size: 12
---------- d3.resize(15, 666) ----------
0 1 2 3 4 5 6 7 8 9 0 0 666 666 666
d3 size: 15
---------- d3.resize(5) ----------
0 1 2 3 4
d3 size: 5

deque容器的插入和删除

两端插入和删除

函数原型	用途
push_back(elem)	尾部插入元素elem
push_front(elem)	头部插入元素elem
pop_back()	删除尾部元素
pop_front(elem)	删除头部元素

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

void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{
	for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	int num = 0;
	deque<int> d1{0,1,2,3,4,5};
	d1.push_front(111);
	d1.push_back(222);
	cout << "---------- push front and push back ----------" << endl;
	print_deque(d1);

	d1.pop_back();
	cout << "---------- d1.pop_back() ----------" << endl;
	print_deque(d1);

	d1.pop_front();
	cout << "---------- d1.pop_front() ----------" << endl;
	print_deque(d1);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- push front and push back ----------
111 0 1 2 3 4 5 222
---------- pop_back ----------
111 0 1 2 3 4 5
---------- pop_front ----------
0 1 2 3 4 5

指定位置

函数原型	用途
insert(const_iterator pos, elem)	迭代器指向位置pos插入元素elem，返回新数据的位置，iterator类型
insert(const_iterator pos, int count, elem)	迭代器指向位置pos插入count元素elem，返回的是插入的最后一个元素的位置，iterator类型
insert(const_iterator pos, iterator pos begin, iterator pos end)	迭代器指向位置pos插入迭代器begin到迭代器end范围内的数据，返回插入的最后一个元素的位置，iterator
erase(const_iterator pos)	删除迭代器指向的元素，返回下一个元素的位置
erase(const_iterator start, const_iterator end)	删除迭代器从[start, end)之间的元素，包头不包尾，返回下一个元素的位置
clear()	删除容器中所有元素，返回下一个元素的位置

关于insert的例子

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

void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{
	for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	int num = 0;
	deque<int> d1{0,1,2,3,4,5};
	cout << "---------- d1 ----------" << endl;
	print_deque(d1);

	// insert(const_iterator pos, elem)
	deque<int>::iterator it = d1.insert(d1.begin(), 111);	// 返回插入的数据对应的位置
	cout << "---------- d1.insert(d1.begin(), 111) ----------" << endl;
	print_deque(d1);
	cout << "d1.insert(d1.begin(), 111)返回的iter指示的内容: " << * it << endl;
	
	// insert(const_iterator pos, int count, elem)
	it = d1.insert(d1.begin(), 3, 333);		// 在pos处插入count个elem
	cout << "---------- d1.insert(d1.begin(), 3, 333) ----------" << endl;
	print_deque(d1);
	cout << "*it(it是d1.insert(d1.begin(), 3, 333)的返回值): " << *it << endl;
	
	// 判断返回值指向的位置
	d1.insert(it, 666);
	cout << "---------- d1.insert(it, 666)，it是d1.insert(d1.begin(), 3, 333)的返回值 ----------" << endl;
	print_deque(d1);

	// insert(const_iterator pos, iterator pos begin, iterator pos end)
	deque<int> d2 {11, 22, 33};
	cout << "---------- d2 ----------" << endl;
	print_deque(d2);
	it = d2.insert(d2.begin(), d1.begin()+6, d1.end());
	cout << "---------- d2.insert(d2.begin(), d1.begin()+6, d1.end()) ----------" << endl;
	print_deque(d2);
	cout << "*it(it是d2.insert(d2.begin(), d1.begin()+6, d1.end()): " << *it << endl;
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- d1 ----------
0 1 2 3 4 5
---------- d1.insert(d1.begin(), 111) ----------
111 0 1 2 3 4 5
d1.insert(d1.begin(), 111)返回的iter指示的内容: 111
---------- d1.insert(d1.begin(), 3, 333) ----------
333 333 333 111 0 1 2 3 4 5
*it(it是d1.insert(d1.begin(), 3, 333)的返回值): 333
---------- d1.insert(it, 666)，it是d1.insert(d1.begin(), 3, 333)的返回值 ----------
666 333 333 333 111 0 1 2 3 4 5
---------- d2 ----------
11 22 33
---------- d2.insert(d2.begin(), d1.begin()+6, d1.end()) ----------
1 2 3 4 5 11 22 33
*it(it是d2.insert(d2.begin(), d1.begin()+6, d1.end()): 1

删除操作

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

void print_deque(const deque<int>& deq)		// 如果这里传参为const &，下面的迭代器也要用const_iterator
{
	for (deque<int>::const_iterator it = deq.begin(); it < deq.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	int num = 0;
	deque<int> d1{0, 1, 2, 3, 4, 5};
	cout << "---------- d1 ----------" << endl;
	print_deque(d1);

	deque<int>::iterator it = d1.erase(d1.begin() + 2);		// 删除d1.begin()+2处的元素，it返回begin()+3处的元素
	cout << "---------- d1.erase(it)(it = d1.begin() + 2) ----------" << endl;
	print_deque(d1);
	cout << "*it(d1.erase(d1.begin() + 2)的返回值): " << *it << endl;

	it = d1.erase(d1.begin(), d1.begin() + 2);		// 删除[d1.begin(), d1.begin() + 2)前闭后开区间的元素，it返回begin()+2处的元素
	cout << "---------- d1.erase(d1.begin(), d1.begin() + 2) ----------" << endl;
	print_deque(d1);
	cout << "*it(it是d1.erase(d1.begin(), d1.begin() + 2)的返回值): " << *it << endl;

	d1.clear();
	cout << "---------- d1.clear() ----------" << endl;
	print_deque(d1);	
	cout << "d1 size: " << d1.size() << endl;
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- d1 ----------
0 1 2 3 4 5
---------- d1.erase(it)(it = d1.begin() + 2) ----------
0 1 3 4 5
*it(d1.erase(d1.begin() + 2)的返回值): 3
---------- d1.erase(d1.begin(), d1.begin() + 2) ----------
3 4 5
*it(it是d1.erase(d1.begin(), d1.begin() + 2)的返回值): 3
---------- d1.clear() ----------

d1 size: 0

deque容器的数据存取

函数原型	用途
deq.at(int idx)	返回索引idx所指的元素
deq[idx]	返回索引idx所指的元素
deq.front()	返回容器中的第一个元素
deq.back()	返回容器中的最后一个元素

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

void print_square(const deque<int> &deq)
{
	for (int i_loop = 0; i_loop < deq.size(); i_loop++)
	{
		cout << deq[i_loop] << " ";
	}
	cout << endl;
}

void print_at(const deque<int>& deq)
{
	for (int i_loop = 0; i_loop < deq.size(); i_loop++)
	{
		cout << deq.at(i_loop) << " ";
	}
	cout << endl;
}

void test01()
{
	int num = 0;
	deque<int> d1{0, 1, 2, 3, 4, 5};
	cout << "---------- print_square ----------" << endl;
	print_square(d1);
	cout << "---------- print_at ----------" << endl;
	print_at(d1);
	cout << "---------- deq.front() ----------" << endl;
	cout << d1.front() << endl;
	cout << "---------- deq.back() ----------" << endl;
	cout << d1.back() << endl;
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- print_square ----------
0 1 2 3 4 5
---------- print_at ----------
0 1 2 3 4 5
---------- deq.front() ----------
0
---------- deq.back() ----------
5

deque容器排序

sort(iterator begin, iterator end)可以对容器进行排序。
默认升序排序，支持随机访问的迭代器的容器，都可用sort排序。
要#include

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

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

void test01()
{
	int num = 0;
	deque<int> d1{10, 55, 24, 79, 36, 5};
	cout << "---------- d1 ----------" << endl;
	print_deque(d1);
	
	cout << "---------- sort(d1.begin(), d1.end()) ----------" << endl;
	sort(d1.begin(), d1.end());		// d1会被排序，默认升序排序，支持随机访问的迭代器的容器，都可用sort排序
	print_deque(d1);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- d1 ----------
10 55 24 79 36 5
---------- sort(d1.begin(), d1.end()) ----------
5 10 24 36 55 79