【STL五】序列容器——deque容器

一、简介

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

前面章节中，我们已经系统学习了 vector 容器，值得一提的是，deque 容器和 vecotr 容器有很多相似之处，比如：

• deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
• deque 容器也可以根据需要修改自身的容量和大小。

和 vector 不同的是，deque 还擅长在序列头部添加或删除元素，所耗费的时间复杂度也为常数阶O(1)。

并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

二、头文件

#include<deque>

三、模板类

template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

四、成员函数

1、迭代器

2、元素访问

3、容量

4、修改操作

五、demo

1、修改操作insert

list 容器在进行插入（insert()）、接合（splice()）等操作时，都不会造成原有的 list 迭代器失效，甚至进行删除操作，而只有指向被删除元素的迭代器失效，其他迭代器不受任何影响。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int>d{ 1,2,3,4,5 };
    auto first = d.begin();  
    while (first < d.end()) {
        cout << *first << " ";
        ++first;
    }
    cout << endl;

    d.pop_front();
    d.push_front(6);

    auto first2 = d.begin();
    while (first2 < d.end()) {
        cout << *first2 << " ";
        ++first2;
    }

    return 0;
}

输出

1 2 3 4 5
6 2 3 4 5

2、修改操作emplace_front

• emplace_front和push_front的区别就不说了，因为我们在同vector容器讲过emplace_back和push_back的区别，其区别是一样的。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int>d{ 1,2,3,4,5 };
    auto first = d.begin();  
    while (first < d.end()) {
        cout << *first << " ";
        ++first;
    }
    cout << endl;

    d.emplace_front(6);

    auto first2 = d.begin();
    while (first2 < d.end()) {
        cout << *first2 << " ";
        ++first2;
    }

    return 0;
}

输出

1 2 3 4 5
6 1 2 3 4 5

3、 size()使用注意事项

• 以下deque讲的一切同样适用于我们之前讲过的vector和array

由于deque和我们讲过的array和vector的大部分成员函数都一直，只有上面三个不同，所以我们扩展下部分成员函数的使用注意事项。这里我们讲的就是size

3.1、size()-1导致的死循环

• 因为size() 返回是无符号整型，当vector是空的时候，size()返回0，无符号的0 减去1，得到的是一个极大的正数。因而在vector是空的时候，以下写法会陷入死循环！

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int> d;
    for (int i = 0; i <= d.size() - 1; i++)//正确写法为for (int i = 0; i < d.size() ; i++)
    {
        cout << "ok\n";
    }
    cout << endl;

    return 0;
}

3.2、操作系统运算规则

• 规则1：所有的立即数按照有符号数处理。
• 规则2：一个无符号数与一个有符号数一块参与运算时，需要将有符号数转为无符号数再进行运算。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int> d;
    int i = 1;
    cout <<"d.size()=" << d.size() << endl;
    cout << "d.size() - i="<<d.size() - i << endl;

    return 0;
}

输出

d.size()=0
d.size() - i=18446744073709551615
size()是无符号类型，有符号类型i在和它比较的时候被自动转型成了无符号的整型，所以取值为-1的i，变成了一个极大的整数.

在i会自动转型成无符号整型，然后你本以为的i（负数）小于v.size() (大于等于0），却判断成了大于！

参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container