C++ STL 之 deque

本节我们将介绍 STL 中的 deque 容器使用。

---

---

deque<T>，是一个定义在 deque 头文件中的容器模板，可以生成包含 T 类型元素的容器，它以双端队列的形式组织元素，因此可以在容器的头部和尾部高效地添加或删除对象，它可以处理先进先出类型的事务，类似于栈这种数据结构，它的使用和 vector 相似，但 vector 只能在容器末尾处增加和删除元素。

deque 容器的初始化

初始化方式：
1.使用默认的构造函数生成 deque 容器，容器中没有任何元素，大小为0，当添加第一个元素，就就会有内存的分配。

deque<string> data;

2.和 vector 容器在本质上相同类似，可以生成给定元素个数的 deque 容器。

deque<string> data(7);

或者

deque<string> data(7,"seven");

3.可以用初始化列表来生成 deque 容器。

deque<string> data {"one","null","three","four","null","six","seven"};

4.也可以用由两个迭代器标识的一段元素来初始化它。

deque<string> data {"one","null","three","four","null","six","seven"};
deque<string> data_ {data};

或者

deque<string> data {"one","null","three","four","null","six","seven"};
deque<string> data_ {begin(data)+2,end(data)-2};

接下来，我们汇总下 deque 容器的初始化。
示例如下：

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<string> data_1;
    deque<string> data_2(7);
    deque<string> data_3(7,"null");
    deque<string> data_4 {"one","null","three","four","null","six","seven"};
    //全部复制
    deque<string> data_5{data_4};
    auto begin_iter = begin(data_4);
    deque<string>::iterator end_iter = end(data_4);
    begin_iter += 2;
    end_iter -= 2;
    //部分复制
    deque<string> data_6{begin_iter,end_iter};
    cout<<"data_1: "<<data_1.size()<<endl;
    for(auto d : data_1){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_2: "<<data_2.size()<<endl;
    for(auto d : data_2){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_3: "<<data_3.size()<<endl;
    for(auto d : data_3){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_4: "<<data_4.size()<<endl;
    for(auto d : data_4){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_5: "<<data_5.size()<<endl;
    for(auto d : data_5){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_6: "<<data_6.size()<<endl;
    for(auto d : data_6){
        cout<<d<<" ";
    }
    cout<<endl;
    return 0;
}

结果如下：

image.png

deque 容器的访问

和 vector 类似，我们可以使用下标索引和 at() 方法进行访问容器内的元素，使用 size() 方法得到容器的大小。
同时 at() 方法比索引方法安全，因为它增加了边界检查，越界时会抛出 out_of_range 异常。
示例如下：

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<string> data {"one","null","three","four","null","six","seven"};
    cout<<"data: "<<data.size()<<endl;
    for(int i=0;i<data.size();i++){
        cout<<data[i]<<" ";
    }
    cout<<endl;
    cout<<"data: "<<data.size()<<endl;
    //推荐使用 at() 方法
    for(int i=0;i<data.size();i++){
        cout<<data.at(i)<<" ";
    }
    cout<<endl;
    return 0;
}

结果如下：

image.png

deque 成员函数 front() 和 back() 的用法也和 vector 相同。参考之前 vector 章节内容即可。

deque 容器添加和删除元素

我们知道，在 vector 中，有 push_back() 和 pop_back() 方法，可以在 vector 容器的尾部增加和删除元素。
deque 容器不仅能在容器尾部增加和删除元素，在头部也可以增加和删除元素。

deque<string> data {"one","two","three","four"};
//在头部增加一个元素
data.push_front("zeros");
//删除头部的元素
data.pop_front();
//在尾部增加一个元素
data.push_back("five");
//删除尾部的元素
data.pop_back();

除了和 vector —样都有 emplace_back() 函数外，deque 还有成员函数 emplace_front()，可以在序列的开始位置生成新的元素。

deque<string> data {"one","two","three","four"};
string word = "zeros five";
//从word中截取,从6开始的4个字符,在尾部加入
data.emplace_back(word,6,4);
//从word中截取,从0开始的5个字符,在头部加入
data.emplace_front(word,0,5);

和 vector 一样，我们也可以使用 emplace() 或 insert() 在 deque 内部添加或移除元素。
但这个过程相对要慢一些，因为这些操作需要移动容器内现有元素。
emplace():

deque<string> data {"one","two","three","four"};
auto iter = end(data);
//使用 emplace() 容器尾部添加一个 "AAA"
data.emplace(iter,3,'A');
iter = end(data);
iter--;
//在 data 的倒数第一个元素前加上一个 "AAAA"
data.emplace(iter,4,'A');

insert():

deque<string> data {"one","two","three","four"};
deque<string> data_add {"six","seven"};
auto iter = end(data);
string goal = "five";
// 在容器后面增加一个 "five"
data.insert(iter,goal);
iter = begin(data);
iter++;
goal = "one_two";
//在容器第 0 个元素后增加一个 "one_two"
data.insert(iter,goal);
auto begin_iter = begin(data_add);
auto end_iter = end(data_add);
//插入 data_add 的一部分,在 data 尾部插入
iter = end(data);
data.insert(iter,begin_iter,end_iter);

之前系列文章中关于 vector 容器的 insert() 函数的使用也适用于 deque 容器。在 deque 的任意位置插入一个元素会让现有的迭代器全部失效，因此需要重新生成迭代器。
deque 的成员函数clear() , erase() 也和 vector 的相同。
clear():

deque<string> data {"one","two","three","four"};
//清除 deque 容器内的所有元素
data.clear();

erase():

deque<string> data {"null","one","two","three","four","five"};
auto iter = begin(data);
//删除一个元素,由一个迭代器指定位置
data.erase(iter);
//此时容器内的元素为: {"one","two","three","four","five"}
auto begin_iter = begin(data);
auto end_iter = end(data);
//使用两个迭代器，用来指定删除元素的范围
begin_iter += 2;
end_iter -= 1;
data.erase(begin_iter,end_iter);

该部分的内容和 vector 容器大同小异，更详细的可以参考之前关于 vector 方面的博客。

deque 容器修改元素

deque 的成员函数 assign() 可以替换现有的所有元素，它有三个重版版本：

1.替换的新内容是由初始化列表指定的元素
2.替换的新内容是由迭代器指定的一段元素
3.替换的新内容是一个特定对象的多个副本

使用初始化列表

deque<string> data {"one","two","three","four","five"};
auto data_ = {string{"null"},string{"nine"},string{"null"}};
data.assign(data_);

注意，此句

auto data_ = {string{"null"},string{"nine"},string{"null"}};

不能写成

auto data_ = {"null","nine","null"};

因为这么做，data_ 的类型会被推导为 initializer_list<const char*>，然而 assign() 需要的是一个 initializer_list<string> 类型的实参，这样就无法通过编译。
当然，我们可以在 assign() 的实参中直接定义初始化列表

deque<string> data {"one","two","three","four","five"};
data.assign({"null","nine","null"});

这样，data 的内容

{"one","two","three","four","five"}

将会被初始化成 data_ 的内容

{"null","nine","null"}

由迭代器指定的一段元素

deque<string> data {"one","two","three","four","five"};
deque<string> data_ {"never","hardly ever","sometimes","often","usually","always"};
deque<string>::iterator begin_iter = begin(data_);
auto end_iter = end(data_);
begin_iter++;
end_iter--;
data.assign(begin_iter,end_iter);

此时，data 的内容为:

{"hardly ever","sometimes","often","usually"}

一个特定对象的多个副本

assign() 中第一个参数指定了替换当前容器内容的第二个参数的个数

deque<string> data {"one","two","three","four","five"};
data.assign(5,"null");

此时，data 的内容为:

{"null","null","null","null","null"}

最后，我们来看看容器的赋值操作，只要赋值运算的右操作数必须和左操作数是相同类型，就可以完成赋值操作。
示例如下:

#include <bits/stdc++.h>
using namespace std;

int main(){
    deque<string> data {"one","two","three","four","five"};
    deque<string> data_;
    data_ = data;
    cout<<"data: "<<data.size()<<endl;
    for(auto d : data){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_: "<<data_.size()<<endl;
    for(auto d : data_){
        cout<<d<<" ";
    }
    cout<<endl;
    //data 的元素发生更改
    data = {"hardly ever","sometimes","often","usually"};
    cout<<"data: "<<data.size()<<endl;
    for(auto d : data){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_: "<<data_.size()<<endl;
    for(auto d : data_){
        cout<<d<<" ";
    }
    cout<<endl;
    return 0;
}

结果如下：

image.png

至此，deque 的内容暂告一段落了，可以看出，deque 的使用和 vector 其实大同小异，它的特点之一是可以在容器的头部和尾部增加元素，当然由于移动元素，时空代价会略有增加。
deque 容器的部分细节和 vector 很相似，例如删除元素后，迭代器的变化，在之前的博客中也有所介绍，这里就不详细展开了。