C++ | STL 浅谈deque容器

2023-08-13 21:05:04

一.简述deque容器

二.deque的创建方式

三.deque容器的插入和删除操作

四.deque的底层形式以及扩容方式。

五.deque容器底层内存连续的实现方法

一.简述deque容器

deque是一个双端队列容器，其在底层为一个双端队列，所需要的头文件为#include<deque>。

正如上图所示，双端队列的每一个端口都既能出，又能进。但我们一般在使用双端队列时，使用的都是受限的双端队列，即我们选定双端队列的某一端只能进（插）元素，相反的，另一端就只能出元素。

deque的底层是双端队列，所以底层的内存空间是连续的（其实是不连续的，后续我们会讲到这一点），因此我们可以使用指针的直接跳转来访问队列中的任何元素，也就是说，后续我们可以使用迭代器+偏移的形式来访问deque容器中的数据。所以我们将deque中的迭代器称为随机访问迭代器。

二.deque的创建方式

#include<iostream>
#include<deque>

int main()
{
	std::deque<int> dqu1;
	std::deque<int> dqu2(10);//count
	std::deque<int> dqu3(10, 20);

	int arr[] = { 12, 3, 234, 3, 6 };
	int len = sizeof(arr) / sizeof(arr[0]);
	std::deque<int> dqu4(arr, arr + len);

	return 0;
}

在构造deque容器dqu1时，调用的是deque类中默认的构造函数，（所有的容器中都有默认的构造函数），且构造的同时没有做任何事情。

在构造deque容器dqu2时，我们显式的给定了这个容器的初始大小10，并且将这10个大小的数据置为0。

在构造deque容器dqu3时，我们显式的给定了这个容器的初始大小10，且显式的将这10个大小的数据置为20。即我们给dqu3中插入了10个值为20的数据。

在构造deque容器dqu4时，我们传入的参数是一个迭代器区间，即将dqu3的开始和末尾的后一个位置传入，也就是将dqu3中的数据插入到dqu4中。

三.deque容器的插入和删除操作

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

template<typename Iterator>
void Show(Iterator first, Iterator last)
{
	for (first; first != last; first++)
	{
		std::cout << *first << " ";
	}
	std::cout << std::endl;
}

int main()
{
	std::deque<int> dqu1;

	for (int i = 0; i < 5; i++)
	{
		dqu1.push_front(i + 1);// 5 4 3 2 1
	}
	Show(dqu1.begin(), dqu1.end());

	for (int i = 0; i < 5; i++)
	{
		dqu1.push_back(i + 1);
	}
	Show(dqu1.begin(), dqu1.end());// 5 4 3 2 1 1 2 3 4 5

	dqu1.insert(dqu1.begin() + 3, 100);//随机访问迭代器
	Show(dqu1.begin(), dqu1.end());

	dqu1.pop_front();
	dqu1.pop_back();
	dqu1.erase(dqu1.begin() + 3);
	Show(dqu1.begin(), dqu1.end());

	return 0;
}

push_front即头插，在队头一端插入元素，时间复杂度为O(1)。

push_back即尾插，在队尾一端插入元素，时间复杂度为O(1)。

insert 即按位置插入元素，insert函数有以下五个重载，时间复杂度为O(n)

iterator std::deque<_Ty, _Alloc>::insert(const_iterator _Where, _Ty && _Val)，在Where位置插入一个值为Val的元素。
iterator std::deque<_Ty, _Alloc>::insert(const_iterator _Where, const _Ty & _Val)，在Where位置插入一个值为Val的元素，且这个元素的值Val不可以被修改。
iterator std::deque<_Ty, _Alloc>::insert(const_iterator _Where, size_type _Count, const _Ty & _Val)，在Where位置插入Count个值为Val的元素。
iterator std::deque<_Ty, _Alloc>::insert(const_iterator _Where, initializer_list<_Ty> _Ilist)，使用初始化列表在Where位置插入新的元素，例如
```
dqu1.insert(dqu1.begin(), { 1,3,4 });
```
iterator std::deque<_Ty, _Alloc>::insert<_Iter, >(const_iterator _Where, _Iter _First, _Iter _Last)，按Where位置插入一个区间（Iter_First~Iter_Last）里面的元素，这个区间代表的是一个迭代器区间。

pop_front 即头删，删除队列头部的元素，时间复杂度为O(1)。

pop_back 即尾删，删除队列尾部的元素，时间复杂度为O(1)。

erase 即按位置删除元素，erase函数有以下两个重载，时间复杂度为O(n)

iterator std::deque<_Ty, _Alloc>::erase(const_iterator _Where) noexcept(is_nothrow_move_assignable_v<value_type>)，删除Where这个位置的元素。
iterator std::deque<_Ty, _Alloc>::erase(const_iterator _First_arg, const_iterator _Last_arg) noexcept(is_nothrow_move_assignable_v<value_type>)，删除 iterator _First~iterator _Last这个迭代器区间的所有元素。

访问即Show函数的时间复杂度为O(1)。

deque容器的特点：“头部或尾部快速地插入或删除元素以及直接访问任何元素”。

注意：上述的所有Where都是用迭代器表示的。

四.deque的底层形式以及扩容方式。

1.deque的底层形式

deque的底层如下图

因为映射区的本质是一个指针数组，因此映射区内存放的都是地址（也可以理解为指向某一地址的指针），而这个地址指的就是数据区的地址。一开始，我们初始化一个deque容器时，映射区的大小默认为2个空间，也就是说这个指针数组只能存放两个指针。

如果我们要在deque容器中插入元素时，系统就会用malloc 或者 new在堆上申请一块大的内存空间，这块内存空间就是数据区，而这个数据区的大小也是固定的，它的大小是512字节。接着指针数组中0号下标位置会存放这块数据区的地址。

设计人员当初为了标明队列的队头和队尾，引进了两个指针。分别是队头指针 pfront 和队尾指针ptail，并且一开始队头指针和队尾指针都指向队列的中间位置。当我们要在队头插入数据时，队头指针就会向前移动一格，而要插入的数据就会存放在当前队头指针所指的位置。相反的，如果我们要在队尾插入数据时，队尾指针就会向后移动一格，而要插入的数据就会存放在当前队尾指针所指的位置。

2.deque的扩容方式

以push_front的方式插入数据（头部扩容）

假如现在我们头插的方式插入n多个值为1的元素，那么pfront指针就会一直前移，知道移动到数据区的首地址为止，这种情况下pfront就不能够继续前移了，如下图

如果现在我们还要以头插的方式插入数据，那么接下来就要进行扩容操作了，具体的扩容操作如下

首先pfront指针会查看当前映射区的上端还有没有其他空的映射区。我们知道当前映射区为0号映射区（指针数组的0号下标所代表的位置），而0号映射区的上端再无其他映射区。
如果当前映射区的上端没有其他空的映射区，那么pfront指针就会查看当前映射区的下端有没有其他空的映射区。我们知道0号映射区的下端还有其他空的映射区，即1号映射区。
如果当前映射区的下端有其他空的映射区，那么系统就会把当前的数据区中的全部内容向下挪动，让下一个映射区存放当前数据区的地址。即让1号映射区存放当前数据区的地址，如下图所示
现在0号映射区就为空了，接着系统就会再开辟一个512字节大小的数据区，接着让0号映射区存放这个新的数据区的地址。
现在deque就有新的空间了，那么pfront就会指向新数据区的末尾，接着我们就又可以进行头插操作了。
如果我们有进行了n次头插，导致pfront又指向了当前数据区的首地址，这时这个新的数据区又满了
如果此时我们还要进行头插，那么就又要进行扩容了，此时系统会通过pfront找到当前的映射区，也就是0号映射区，如果当前映射区的上端没有其他空的映射区，那么pfront指针就会查看当前映射区的下端有没有其他空的映射区。我们发现现在无论是在0号映射区的上端还是下端都没有其他空的映射区了。那么此时就会对映射区进行扩容，且映射区的扩容是以倍数的形式来增长的。
接着系统会自动的把当前所有的数据区向下挪动一个映射区，如下图
现在pfront的上端就有空的映射区了，接下来的步骤就和前面的步骤一样了。0号映射区会指向一个新的数据区，接着我们就又能进行头插操作了。
重复以上步骤。

以push_back的方式插入数据（尾部扩容）

首先我们向队列的尾部插入n多个1，一直到ptail指向队列末尾为止
如果现在我们还要进行尾插操作，那么ptail会查看当前映射区的下端是否为空。如果当前映射区的下端有其他空的映射区，例如此处的1号映射区，那么1号映射区就会指向系统新开辟的一个数据区。
现在ptai就指向这个新数据区的首地址了，那么我们就又可以进行尾插操作了，直到ptail指向当前数据区的末尾为止。
现在数据区就又满了，如果此时我们还要进行尾插操作，但ptai发现当前映射区的下端已经没有空余的空间了，那么ptail就会查看当前映射区的上端有没有空余的空间，而此时映射区的上端也没有空余的空间，那么就要对映射区进行扩容了（以2倍的形式来扩容）。映射区扩充完毕后，将所有的数据区都往映射区的中间来移动。
接下来就又从步骤1开始循环了，直到下图所示
现在所有的数据的都已经满了（不包括头插的那一部分），如果还要进行头插操作，和步骤4一样，ptai首先会查看当前映射区的上端有没有空余的空间，这时我们发现0号映射区是空的，那么系统就会将所有的数据区往上挪动。
现在ptail发现当前映射区的下端有空余空间，就又从步骤2开始循环了。