E

EdwardWong

V1

2022/11/30阅读:20主题:姹紫

STL序列型容器之deque

deque容器

dequedouble-ended queue的缩写,又称双端队列容器。

dequevector容器很多地方类似,比如:

  • deque容器擅长在序列尾部添加或删除元素(时间复杂度为O(1)),而不擅长在序列中间添加或删除元素。

  • deque容器也可以根据需要修改自身容量和大小

vector不同的是,deque还擅长在序列头部添加或删除元素,所耗费的时间复杂度也是O(1),并且最重要的不同是vector存储的元素在内存中是连续的,而deque容器中存储的元素并不能保证所有元素都连续的存储

deque容器以模板类deque<T>的形式存储在<deque>头文件中,且位于std命名空间中,因此在使用该容器之前,需要包含下面的代码:

#include<deque>

using namespace std;// 或者std::deque

deque的创建

创建空deque容器

std::deque<int> d

与空的array容器不同的是,空的deque容器在创建之后可以做添加或删除的操作。

创建一个具有n个元素的deque容器,其中每个元素都采用对应类型的默认值:

std::deque<int> d(10)

这样创建了一个具有10个默认元素为0的deque容器。

创建deque容器的同时为每个元素都指定初始值。

std::deque<int> d(10,5)

这样就创建了一个包含10个元素(值都为5)的deque容器。

可以通过拷贝容器创建一个新的deque容器

std::deque<int> d1(5);

std::deque<int> d2(d1);

采用这种方式需要保证新旧容器存储的元素类型一致

可以拷贝其他类型容器中指定区域内的元素(可以是普通数组),从而创建数组。

//拷贝普通数组,创建`deque`容器

int a[]={1,2,3,4,5};

std::deque<int> d(a,a+1);

//适用于所有类型的容器

std::array<int,5> arr{11,12,13,14,15};

std::deque<int> d(arr.begin()+2,arr.end()); //拷贝arr容器中的13,14,15

deque容器可利用的成员函数

因为deque双端队列的特点,该容器包含一些arrayvector容器没有的成员函数。

vector容器相比,额外增加了实现在容器头部添加和删除元素的成员函数,同时删除了capacity()reserve()data()成员函数。

c++11标准库新增的begin()end()这两个全局函数也适用于deque容器,如果函数的操作对象是容器,则与容器内部的begin()end()相同,如果函数的操作函数是数组,则begin()函数返回的是指向数组第一个元素的指针,end()函数返回指向数组中最后一个元素之后一个位置的指针.

#include <iostream>
#include <deque>
using namespace std;
int main()
{
//初始化一个空deque容量
deque<int>d;
//向d容器中的尾部依次添加 1,2,3
d.push_back(1); //{1}
d.push_back(2); //{1,2}
d.push_back(3); //{1,2,3}
//向d容器的头部添加 0
d.push_front(0); //{0,1,2,3}

//调用 size() 成员函数输出该容器存储的字符个数。
printf("元素个数为:%d\n", d.size());

//使用迭代器遍历容器
for (auto i = d.begin(); i < d.end(); i++) {
cout << *i << " ";
}
cout << endl;
return 0;
}

deque容器的迭代器用法

deque容器迭代器的类型为随机访问迭代器

对于迭代器的用法与vector迭代器的用法相同,可参考STL序列型容器之vector

deque容器的功能是遍历容器,在遍历的同时可以访问或者修改容器中的元素,但是迭代器不能用来初始化空的deque容器

下面这段代码试图通过迭代器初始化元素,是错误的,可以通过push_back,push_front(),resize()成员函数添加元素。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int>values;
auto first = values.begin();
//*first = 1;
return 0;
}

当向deque容器添加元素时,**deque容器会申请更多的内存空间,同时其包含的所有元素会被复制或移动到新的内存地址(原来占用的内存会被释放),这会导致之前创建的迭代器失效。**

#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int>d;
d.push_back(1);
auto first = d.begin();
cout << *first << endl;
//添加元素,会导致 first 失效
d.push_back(1); //这行代码增加元素会申请新的内存地址,从而使之前的`first`迭代器失效,下面继续使用会报错
cout << *first << endl;
return 0;
}

在对容器添加元素的操作之后,如果仍继续使用之前创建好的迭代器,最好重新生成。

deque容器底层实现原理

deque 容器的存储结构

vector容器采用连续的线性空间不同,deque容器存储数据的空间由一段一段等长的连续空间构成,各段空间之间并不一定是连续的,可以在内存的不同区域。

为了管理这些连续空间,deque容器用数组(数组名假设为map)存储着各个连续空间的首地址,也就是说,map数组中存储的都是指针,指向那些真正用来存储数据的各个连续空间。

这样通过建立map数组,deque容器申请的这些分段的连续空间就能实现整体连续的效果。 当deque容器需要在头部或尾部增加存储空间时,会申请一段新的连续空间,同时在map数组的开头或者结尾添加指向该空间的指针,由此该空间就串接到了deque容器的头部或尾部。

如果map数组满了之后,就会申请一块更大的连续空间供map数组使用,将原有数据(很多指针)拷贝到新的map数组中,然后释放旧的空间。

deque容器迭代器的底层实现

deque容器底层将序列中的元素分别存储到了不同段的连续空间中,因此要想实现迭代器的功能,需解决如下问题:

  • 迭代器在遍历deque容器时,必须能确认各个连续空间在map数组中的位置

  • 迭代器在遍历某个具体的连续空间时,必须能够判断自己是否已经处于空间的边缘位置,如果是,一旦前进或后退,就需要跳跃到上一个或者下一个连续空间中。

deque迭代器定义了以下的结构:

template<class T>
struct __deque_iterator{
...
T* cur; //指向当前正在遍历的元素
T* first; //指向当前连续空间的首地址
T* last; //指向当前连续空间的尾地址
map_pointer node; // map_pointer等价于T** 是一个二级指针
//指向`map`数组中存储的指向当前连续空间的指针

}

借助这4个指针,deque迭代器对随机访问迭代器支持的各种运算符进行了重载,能对deque分段连续空间中存储的元素进行遍历。

//当迭代器处于当前连续空间边缘的位置时,如果继续遍历,就需要跳跃到其它的连续空间中,该函数可用来实现此功能
void set_node(map_pointer new_node){
node = new_node;//记录新的连续空间在 map 数组中的位置
first = *new_node; //更新 first 指针
//更新 last 指针,difference_type(buffer_size())表示每段连续空间的长度
last = first + difference_type(buffer_size());
}
//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}
//重载前置 ++ 运算符
self & operator++(){
++cur;
//处理 cur 处于连续空间边缘的特殊情况
if(cur == last){
//调用该函数,将迭代器跳跃到下一个连续空间中
set_node(node+1);
//对 cur 重新赋值
cur = first;
}
return *this;
}
//重置前置 -- 运算符
self& operator--(){
//如果 cur 位于连续空间边缘,则先将迭代器跳跃到前一个连续空间中
if(cur == first){
set_node(node-1);
cur == last;
}
--cur;
return *this;
}

deque容器的底层实现

deque容器除了维护先前讲过的map数组外,还需要维护startfinish这两个deque迭代器,以下为deque容器的定义:

template<class _Ty, class _Alloc=allocator<_Ty>>

class deque{
...
protected:
iterator start;
iterator finish;
map_pointer map;
...
}

其中start迭代器记录着map数组中首个连续空间的信息,finish迭代器记录着map数组中最后一个连续空间的信息。另外需要注意的是,和普通的deque迭代器不同,start迭代器中的cur指针指向的是连续空间中首个元素,而finish迭代器中的cur指针指向的是连续空间最后狗一个元素的下一个位置。

借助startfinish,以及deque迭代器中重载的诸多运算符,就可以实现deque容器提供的大部分成员函数,比如:

/begin成员函数

iterator begin(){return start;}

//end成员函数

iterator end() {return finish;}

//front 成员函数

reference front(){return *start;}

//back成员函数

reference back(){
iterator tmp =finish;
--tmp;
return *tmp;
}

//size()成员函数

size_type size() const {return finish-start} //deque迭代器chong重载了-运算符

//empty()成员函数

bool empty() const {return finish==start;}

deque容器访问元素(4种方法)

  1. 普通数组访问元素的方式
#include<iostream>

#include<deque>

using namespace std;

int main(){
deque<int> d{1,2,3,4};
cout <<d[1]<<endl;
//修改指定小标位置处的元素
d[1]=5;
cout<<d[1]<<endl;
}

使用**容器[n]**的这种方式,不仅可以访问容器中的元素,还可以对其进行修改,但是使用此方法需确保下标n的值不会超过容器中存储元素的个数,容易出现越界访问的情况。

如果想要避免越界访问,可以使用deque模板类提供的at()成员函数,at函数会返回容器中指定位置处元素的引用形式,因此利用该函数的返回值,既可以访问指定位置处的元素,如果需要还可以对其进行修改。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int>d{ 1,2,3,4 };
cout << d.at(1) << endl;
d.at(1) = 5;
cout << d.at(1) << endl;
//下面这条语句会抛出 out_of_range 异常
//cout << d.at(10) << endl;
return 0;
}

deque容器还提供了2个成员函数,即front()back(),他们分别返回vector容器中第一个和最后一个元素的引用,通过利用它们的返回值,可以访问/修改容器中的首尾元素。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> d{ 1,2,3,4,5 };
cout << "deque 首元素为:" << d.front() << endl;
cout << "deque 尾元素为:" << d.back() << endl;
//修改首元素
d.front() = 10;
cout << "deque 新的首元素为:" << d.front() << endl;
//修改尾元素
d.back() = 20;
cout << "deque 新的尾元素为:" << d.back() << endl;
return 0;
}

vector容器不同,deque容器没有提供data()成员函数,同时deque容器在存储元素时,也无法保证其会将元素存储在连续的内存空间中,因此尝试使用指针去访问deque容器中指定位置处的元素,是非常危险的。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> d{ 1,2,3,4,5 };
//从元素 2 开始遍历
auto first = d.begin() + 1;
//遍历至 5 结束(不包括 5)
auto end = d.end() - 1;
while (first < end) {
cout << *first << " ";
++first;
}
return 0;
}

deque容器添加和删除元素

deque添加和删除元素,只能借助deque模板类提供的成员函数。

实际应用中,常用emplace()emplace_back()emplace_front()代替insert()push_back()push_front()

#include <deque>
#include <iostream>
using namespace std;
int main()
{
deque<int>d;
//调用push_back()向容器尾部添加数据。
d.push_back(2); //{2}
//调用pop_back()移除容器尾部的一个数据。
d.pop_back(); //{}

//调用push_front()向容器头部添加数据。
d.push_front(2);//{2}
//调用pop_front()移除容器头部的一个数据。
d.pop_front();//{}

//调用 emplace 系列函数,向容器中直接生成数据。
d.emplace_back(2); //{2}
d.emplace_front(3); //{3,2}
//emplace() 需要 2 个参数,第一个为指定插入位置的迭代器,第二个是插入的值。
d.emplace(d.begin() + 1, 4);//{3,4,2}
for (auto i : d) { //对有迭代器的容器,可以使用for-based的循环
cout << i << " ";
}
//erase()可以接受一个迭代器表示要删除元素所在位置
//也可以接受 2 个迭代器,表示要删除元素所在的区域。
d.erase(d.begin());//{4,2}
d.erase(d.begin(), d.end());//{},等同于 d.clear()
return 0;
}
#include <iostream>
#include <deque>
#include <array>
using namespace std;
int main()
{
std::deque<int> d{ 1,2 };
//第一种格式用法
d.insert(d.begin() + 1, 3);//{1,3,2}

//第二种格式用法
d.insert(d.end(), 2, 5);//{1,3,2,5,5}

//第三种格式用法
std::array<int, 3>test{ 7,8,9 };
d.insert(d.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}

//第四种格式用法
d.insert(d.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}

for (int i = 0; i < d.size(); i++) {
cout << d[i] << " ";
}
return 0;
}

emplace()函数的优势

#include <deque>
#include <iostream>
using namespace std;
class testDemo
{
public:
testDemo(int num) :num(num) {
std::cout << "调用构造函数" << endl;
}
testDemo(const testDemo& other) :num(other.num) {
std::cout << "调用拷贝构造函数" << endl;
}
testDemo(testDemo&& other) :num(other.num) {
std::cout << "调用移动构造函数" << endl;
}
testDemo& operator=(const testDemo& other);
private:
int num;
};

testDemo& testDemo::operator=(const testDemo& other) {
this->num = other.num;
return *this;
}
int main()
{
//emplace和insert
cout << "emplace:" << endl;
std::deque<testDemo> demo1;
demo1.emplace(demo1.begin(), 2);
cout << "insert:" << endl;
std::deque<testDemo> demo2;
demo2.insert(demo2.begin(), 2);

//emplace_front和push_front
cout << "emplace_front:" << endl;
std::deque<testDemo> demo3;
demo3.emplace_front(2);
cout << "push_front:" << endl;
std::deque<testDemo> demo4;
demo4.push_front(2);

//emplace_back()和push_back()
cout << "emplace_back:" << endl;
std::deque<testDemo> demo5;
demo5.emplace_back(2);

cout << "push_back:" << endl;
std::deque<testDemo> demo6;
demo6.push_back(2);
return 0;
}

分类:

后端

标签:

C++

作者介绍

E
EdwardWong
V1