全面了解STL Deque

NCFPP • 2025-04-12 13:00 • 编程

STL（Standard Template Library）是C++语言的标准库，其中的deque（双端队列）是一个非常重要的容器。

一、deque基础

deque可以视作一个序列的集合，每个序列头尾相接而形成一个圆形缓冲区。它支持O(1)常数时间下以下操作：

在序列前后插入元素
在序列前后删除元素
随机访问序列中的元素
获取序列中元素的数量

deque使用动态数组存储元素，默认情况下在序列的前后各预留一定数量的空间，从而保证在插入或删除元素时在O(1)时间内完成。

#include 
#include 
using namespace std;
int main(){
    deque dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.pop_front();
    dq.pop_back();
    dq.clear();
    dq.empty();
    dq.size();
}

二、insert和erase操作

deque提供了insert和erase操作，用于在序列中插入和删除元素，这两个操作非常强大。

（一）insert操作

insert操作有以下几种形式：

在指定位置插入单个元素
在指定位置插入n个相同的元素
在指定位置插入区间[first, last)内的元素

#include 
#include 
using namespace std;
int main(){
    deque dq {1,2,3,4};
    auto it = dq.begin() + 2;
    dq.insert(it, 5);    // 1 2 5 3 4
    
    dq.insert(it, 2, 6); // 1 2 6 6 5 3 4
    
    vector v {7,8};
    dq.insert(it, v.begin(), v.end());    // 1 2 7 8 6 6 5 3 4
}

（二）erase操作

erase操作有以下几种形式：

删除指定位置的单个元素
删除区间[first, last)内的元素
删除所有元素

#include 
#include 
using namespace std;
int main(){
    deque dq {1,2,3,4};
    auto it = dq.begin() + 2;
    dq.erase(it);   // 1 2 4
    
    dq.erase(it, dq.end()); // 1 2
    
    dq.clear(); // 空序列
}

三、deque和vector的比较

deque和vector都是STL提供的序列容器，它们的最大区别在于存储结构不同，因而导致不同的性能表现。

vector使用连续的动态数组存储元素，支持在序列末尾追加元素，但是在序列头部或中间插入或删除元素的代价较大。

deque使用的是一种双层结构，底层是一个数组的指针序列，每个指针指向一个动态数组，上层提供了更为方便的接口。由于deque采用了类似于虚拟内存的方式，因此其无论在序列首尾或中间插入或删除元素的代价都是O(1)的，除此之外，deque还支持高效地在序列两端执行插入和删除操作。

#include 
#include 
#include 
#include 
using namespace std;
int main(){
    deque dq;
    vector v;
    auto t1 = chrono::high_resolution_clock::now();
    for(int i=0;i<100000;i++)
        dq.push_back(i);
    auto t2 = chrono::high_resolution_clock::now();
    for(int i=0;i<100000;i++)
        v.push_back(i);
    auto t3 = chrono::high_resolution_clock::now();
    cout << "deque push_back: " << chrono::duration_cast(t2-t1).count() << "ms" << endl;
    cout << "vector push_back: " << chrono::duration_cast(t3-t2).count() << "ms" << endl;
}

四、总结

deque在实际运用中表现出的优异性能和灵活性使其成为STL中重要的序列容器之一，我们可以根据需要灵活地选择存储结构相对固定的vector或者支持高效操作的deque作为容器。通过深入了解deque的相关函数和性能表现，能够更加灵活和高效地应用它来解决我们的问题。

原创文章，作者：NCFPP，如若转载，请注明出处：https://www.506064.com/n/368882.html