C   STL/ (4) deque

deque是常見的雙端陣列。用處很廣,本節就介紹相關概念並實現一個簡單的評委打分系統。

  • deque的基本概念
    • 什麼是deque?
    • deque的功能
    • deque的實現方法
  • deque常用API

    • deque建構函式
    • deque賦值
    • deque元素存取
    • deque大小
    • deque插入與刪除
  • deque應用:評委打分系統


  • deque基本概念
    • 什麼是deque?
      我們知道vector是一個單口容器,相當於一個動態陣列。而deque則是一個雙口容器,是一個雙端陣列。也就是說,deque提供方法能夠在首尾以O(1)的時間複雜度插入刪除元素。
    • deque的基本功能
      我們還是以一張圖來說明:
      deque
    • deque實現方法
      deque利用分塊的連續儲存空間來實現首尾元素的插入和刪除。
      deque利用中控器管理分塊的連續儲存空間。中控器中存放的是各塊記憶體空間的首地址(即指標)。
      deque_theory

  • deque常用API

    • deque的初始化

          deque<int> d;
      deque<int> d1(10,1);
      deque<int> d2(d1);
      deque<int> d3(d2.begin(),d2.end());
      deque<int> d4=d3;
      for(int i=0;i<d1.size();i  ){
      cout<<d1[i]<<d2[i]<<d3[i]<<d4[i]<<endl;
      }
      
    • deque賦值

      deque<int> d, d2, d3, d4;
      deque<int> d5(10, 1);
      d = d5;
      d2.assign(d5.begin(), d5.end());
      d3.assign(10,2);
      //d4.assign(d3); 沒有這種寫法
      for (int i = 0; i<d.size(); i  ){
      cout << d[i] << d2[i] << d3[i] << d5[i] << endl;
      }
    • deque元素存取

          deque<int> d,d1;
      deque<int> d2(10,1);
      cout<<d2.front()<<" "<<d2.back()<<endl;
      for(int i=0;i<d2.size();i  ){
      cout<<d2.at(i)<<" ";
      }
      cout<<endl;
      
    • deque大小
      deque沒有capacity和reserve

          deque<int> d(10,1);
      if(d.empty()){
      cout<<"d is empty!!!"<<endl;
      }
      else{
      cout<<"d is not empty!!"<<endl;
      }
      cout<<"d.size: "<<d.size()<<endl;
      for(int i=0;i<d.size();i  ){
      cout<<"ele "<<i <<" :"<<d.at(i)<<" ";
      }
      cout<<endl;
      d.resize(5);
      cout<<"d.size: "<<d.size()<<endl;
      for(int i=0;i<d.size();i  ){
      cout<<"ele "<<i <<" :"<<d.at(i)<<" ";
      }
      cout<<endl;
    • deque插入和刪除

      • 插入
        • insert(iterator,num,ele);
        • push_back(ele) ;
        • push_front(ele);
      • 刪除
        • erase(iterator start,iterator end);
        • erase(iterator pos);
        • clear();
        • pop_back();
        • pop_front();

      這裡的插入刪除用法跟vector中的用法一樣,就不重複了。


  • deque應用:評委打分系統