STL序列型容器之deque

deque容器

deque是double-ended queue的缩写，又称双端队列容器。

deque和vector容器很多地方类似，比如：

• 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双端队列的特点，该容器包含一些array、vector容器没有的成员函数。

和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数组外，还需要维护start和finish这两个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指针指向的是连续空间最后狗一个元素的下一个位置。

借助start和finish,以及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;
}