C++容器使用详解---deque容器_deque c++ 使用

1.deque容器

在C++中，std::deque（发音为 “deck”）是双端队列（double-ended queue）的缩写，是STL中的一个容器。它允许在两端高效地进行插入和删除操作，因此得名双端队列。下面是关于std::deque的一些基本概念和特性：

特点：

1. 动态数组：deque内部通常实现为一个分段的动态数组，这意味着它在内存中不是连续的一块，而是由多个连续的区块组成，这使得在两端插入和删除元素都非常高效。

2. 随机访问：尽管在内存中不是连续一块，deque仍然支持随机访问，即通过索引直接访问元素，时间复杂度为O(1)。

3. 双向开口：可以在deque的前端（front）和后端（back）进行插入和删除操作，时间复杂度通常为O(1)。

4. 内存分配：当deque需要更多空间时，它会在两端分别分配新的区块，而不是移动所有元素来腾出空间或扩大现有的连续内存块，这使得在两端的插入操作相对高效。

5. 容量与尺寸：同vector一样，deque也有容量（capacity）和大小（size）的概念。容量表示当前分配的内存可以存放多少元素，而大小则是当前实际存放的元素数量。

6. 迭代器：deque提供了随机访问迭代器，可以从前向后或从后向前遍历元素。

常用操作：

• push_back() 和 pop_back()：在deque的后端添加或移除元素。
• push_front() 和 pop_front()：在deque的前端添加或移除元素。
• insert() 和 erase()：在deque的任意位置插入或删除元素。
• size() 和 capacity()：获取deque中的元素数量和当前容量。
• 使用下标或迭代器访问元素。

应用场景：

deque适合于那些需要在序列的开始和结束位置高效插入和删除元素的场景，比如实现一个循环缓冲区、模拟队列（尤其是需要两端操作的队列）等。

总之，std::deque是一个灵活且高效的容器，特别适合于需要在序列两端进行频繁插入和删除操作的场景。

1.deque容器构造函数

deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身
deque(n, elem);//构造函数将n个elem拷贝给本身
deque(const deque &deq);//拷贝构造函数
1
2
3
4

示例:

#include <iostream>
#include <deque>
using namespace std;

int main(){
    deque<int>deque1;
    for(int i = 0;i < 10;++i){
        deque1.push_back(i);
    }
    for(int &it : deque1){
        cout << it << " ";
    }
    cout << endl;
    deque<int>deque2(deque1.begin(), deque1.end());
    for(int &it : deque2){
        cout << it << " ";
    }
    cout << endl;
    deque<int>deque3(10,100);
    for(int &it : deque3){
        cout << it << " ";
    }
    cout << endl;
    deque<int>deque4(deque3);
    for(int &it : deque4){
        cout << it << " ";
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.deque容器赋值操作

deque& operator=(const deque &deg);//重载等号操作符
assign(beg, end);//将[beg,end)区间中的数据拷贝赋值给本身
assign(n, elem);//将n个elem拷贝赋值给本身。
1
2
3

示例：

//
// Created by 86189 on 2024/6/27.
//
#include <iostream>
#include <deque>
using namespace std;

int main(){
    deque<int>deque1;
    for(int i = 0;i < 10;++i){
        deque1.push_back(i);
    }
    for(int &it : deque1){
        cout << it << " ";
    }
    cout << endl;
    deque<int>deque2;
    deque2 = deque1;
    for(int &it : deque2){
        cout << it << " ";
    }
    cout << endl;
    deque<int>deque3;
    deque3.assign(deque2.begin(), deque2.end());
    for(int &it : deque3){
        cout << it << " ";
    }
    cout << endl;
    deque3.assign(10,520);
    for(int &it : deque3){
        cout << it << " ";
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

3.deque容器大小操作

deque.empty();//判断容器是否为空
deque.size();//返回容器中元素的个数
deque.resize(num);
//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem);
//重新指定容器的长度为num,若容器变长，则以elem值填充新位置,//如果容器变短，则末尾超出容器长度的元素被删除。
1
2
3
4
5
6
7

示例：

//
// Created by 86189 on 2024/6/27.
//
#include <iostream>
#include <deque>
using namespace std;

int main(){
    // 初始化一个双端队列
    deque<int> deque1;
    
    // 向队列中添加10个整数
    for(int i = 0;i < 10;++i){
        deque1.push_back(i);
    }
    
    // 遍历并打印队列中的所有元素
    for(int &it : deque1){
        cout << it << " ";
    }
    cout << endl;
    
    // 检查队列是否为空，并打印相应信息
    if (deque1.empty()){
        cout << "Nothing" << endl;
    }
    
    // 打印队列的大小
    cout << deque1.size() << endl;
    
    // 调整队列大小为15，可能造成元素的添加或删除
    deque1.resize(15);
    
    // 遍历并打印调整后的队列元素
    for(int &it : deque1){
        cout << it << " ";
    }
    cout << endl;
    
    // 将队列大小调整为20，并为新增元素指定默认值1
    deque1.resize(20,1);
    
    // 再次遍历并打印调整后的队列元素
    for(int &it : deque1){
        cout << it << " ";
    }
    cout << endl;
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

4.deque容器插入和删除

两端插入操作:
push back(elem);//在容器尾部添加一个数据
push front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据
指定位置操作:
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//清空容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
1
2
3
4
5
6
7
8
9
10
11
12

示例：

#include <iostream>
#include <deque>
using namespace std;

/* 定义一个打印类，用于输出deque的内容 */
class print{
public:
    /* 使用静态成员函数printFunc，接收一个deque<int>类型的引用参数 */
    /* 参数deque1: 要打印的deque<int>对象 */
    /* 该函数不返回任何值，它通过cout输出deque<int>的内容 */
    static void printFunc(const deque<int>& deque1){
        /* 遍历deque1中的每个元素，并打印 */
        for(int it : deque1){
            cout << it << " ";
        }
        /* 行末换行 */
        cout << endl;
    }
};

int main(){
    /* 创建一个deque<int>对象deque1 */
    deque<int> deque1;
    /* 在deque1的尾部添加元素10 */
    deque1.push_back(10);
    /* 在deque1的头部添加元素20 */
    deque1.push_front(20);
    /* 调用printFunc打印当前deque1的内容 */
    print::printFunc(deque1);
    /* 移除deque1的尾部元素 */
    deque1.pop_back();
    /* 移除deque1的头部元素 */
    deque1.pop_front();
    /* 调用printFunc打印当前deque1的内容 */
    print::printFunc(deque1);
    /* 在deque1的开头插入元素2 */
    deque1.insert(deque1.begin(),2);
    /* 调用printFunc打印当前deque1的内容 */
    print::printFunc(deque1);
    /* 在deque1的开头插入两个值为1的元素 */
    deque1.insert(deque1.begin(),2,1);
    /* 调用printFunc打印当前deque1的内容 */
    print::printFunc(deque1);
    /* 将deque1的自身内容复制并插入到deque1的末尾 */
    deque1.insert(deque1.end(),deque1.begin(), deque1.end());
    /* 调用printFunc打印当前deque1的内容 */
    print::printFunc(deque1);
    /* 清空deque1的所有元素 */
    deque1.clear();
    /* 调用printFunc打印当前deque1的内容（此时为空） */
    print::printFunc(deque1);
    /* 从deque1的开头到结尾删除所有元素（因已清空，此操作无实际效果） */
    deque1.erase(deque1.begin(), deque1.end());
    /* 调用printFunc打印当前deque1的内容（此时为空） */
    print::printFunc(deque1);
    /* 在deque1的头部插入元素1 */
    deque1.push_front(1);
    /* 删除deque1的开头元素 */
    deque1.erase(deque1.begin());
    /* 调用printFunc打印当前deque1的内容 */
    print::printFunc(deque1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

另外：传入的迭代器pos、begin等支持数据偏移。

5.deque容器数据存取

at(int idx);//返回索引idx所指的数据

operator[];//同上

front();//返回容器中的第一个数据元素

back();//返回容器中的最后一个元素

示例：

//
// Created by 86189 on 2024/6/28.
//
#include <iostream>
#include <deque>
using namespace std;

int main(){
    // 创建一个整数类型的双端队列
    deque<int> deque1;
    
    // 向队列中添加10个整数，从0到9
    for(int i = 0;i < 10;++i){
        deque1.push_back(i);
    }
    
    // 输出队列中索引为1的元素
    // 使用.at()方法访问元素时，会进行边界检查，确保索引在有效范围内
    cout << deque1.at(1) << endl;
    
    // 输出队列中索引为2的元素
    // 使用[]操作符访问元素时，不会进行边界检查
    cout << deque1[2] << endl;
    
    // 输出队列的最后一个元素
    // back()方法用于获取队列的最后一个元素
    cout << deque1.back() << endl;
    
    // 输出队列的第一个元素
    // front()方法用于获取队列的第一个元素
    cout << deque1.front() << endl;
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

6.deque容器构排序操作

当使用标准算法时，需要包含算法的头文件#include <algorithm>

示例：

//
// Created by 86189 on 2024/6/28.
//
#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main(){
    // 初始化一个双端队列deque1
    deque<int> deque1;
    
    // 向队列中添加五个整数元素
    deque1.push_back(100);
    deque1.push_back(45);
    deque1.push_back(55);
    deque1.push_back(199);
    deque1.push_back(163);
    
    // 对队列中的元素进行排序
    // 为了展示deque可以支持标准库中的排序操作
    sort(deque1.begin(), deque1.end());
    
    // 遍历并输出排序后的队列元素
    // 体现deque支持迭代器遍历的特点
    for(int &it : deque1){
        cout << it << " ";
    }
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33