您的位置:

全面了解STL Deque

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的相关函数和性能表现,能够更加灵活和高效地应用它来解决我们的问题。