[C++] deque container 정리 및 사용법

<목차>

1) deque container

2) deque의 사용 

3) deque의 생성자와 연산자

4) deque의 멤버 함수

5) 다양한 예제

1) deque container

• deque는 vector의 단점을 보완하기 위해서 만들어진 container 입니다.
  
  

• deque도 vector와 마찬가지로 배열기반의 구조입니다.
  
  

• vector는 새로운 원소가 추가 될때 메모리 재할당 후 이전 원소를 복사하는 방식으로 인하여,  삽입시에 성능이 저하 하는 단점이 있습니다.
  
  deque는 이러한 vector의 단점을 보완하기 위해서 여러개의 메모리 블록을 할당하고하나의 블록처럼 여기는 기능을 제공합니다.
  
  

• deque는 메모리가 부족할때 마다 일정한 크기의 새로운 메모리 블록을 할당합니다. 그럼으로써, 이전 원소를 복사하지 않습니다.
  
  

• 그림으로 확인해 보겠습니다.
  

  

  
  

• 그림에서 보면, 일정한 크기의 블록이 3개로 이루어져있고, 데이터의 삽입과 삭제가 front 와 back에서 이루어 질 수 있음을 알 수 있습니다.
  
  

• 또한 deque 중간에 원소를 삽입하거나 삭제 할 수 있습니다. (vector의 멤버 변수와 90% 같습니다.)
  

2) deque의 사용.

• <deque> 헤더파일을 추가해야합니다.
  
  
• using namespace std; 를 추가하면 편리하게 사용할 수 있습니다.
  
  
• deque의 선언은 deque<[Data Type]> [변수이름] 입니다.
  ex) deque<string> dq;
  

3) deque의 생성자와 연산자

• deque dq;
  - 비어있는 deque dq 를 생성합니다.
  
  
• deque dq(10);
  - default(0) 값 으로 초기화 된 10개의 원소를 가진 dq를 생성합니다
  
  
• deque dq(10, 4);
  - 4의 값으로 초기화 된 10 개의 원소를 가진 dq를 생성합니다.
  
  
• deque dq1;
  deque dq2(dq1);
  - dq1을 복사한 dq2를 생성합니다.
  
  
• 연산자
  "==", "!=", "<", ">", "<=", ">=" 사용 가능합니다. (return 은 bool 타입입니다.)
  ex) dq1 == dq2
  

4) deque의 멤버 함수

-> deque에는 capacity 멤버 함수가 없습니다.

-> deque<int> dq; 라고 가정.
-> 참조 한다는 것은 해당 데이터를 리턴 한다는 뜻입니다.

• dq.assign(4, 3);
  - 3의 값으로 4개의 원소 할당.
  
  
• dq.at(idx);
  - idx번째 원소를 참조합니다. 
  - 유효범위를 점검하므로 dq[idx]보다 "상대적"으로 속도가 느립니다.
  - dq[idx] 로도 참조가 가능합니다 (dq[idx]가 at보다 속도가 빠릅니다)
  
  
• dq[idx];
  - idx 번째 원소를 참조합니다.
  - 유효 범위를 점검하지 않으므로 상대적으로 속도가 dq.at(idx)보다 빠릅니다.
  
  
• dq.front();
  - 첫 번째 원소를 참조 합니다.
  
  
• dq.back();
  - 맨 마지막 원소를 참조 합니다.
  
  
• dq.clear();
  - 모든 원소를 제거합니다.
  
  
  
• dq.push_front(3);
  - dq의 첫 번째 원소 앞에 원소 3을 삽입합니다.
  
  

• dq.pop_front();
  - dq의 첫 번째 원소를 제거합니다.
  
  
  
• dq.push_back(5);
  - dq의 마지막 원소 뒤에 원소 5를 삽입합니다.
  

• dq.pop_back();
  - 마지막 원소를 제거합니다.
  
  
  
• dq.begin();
  - 첫번째 원소를 가리킵니다. (iterator와 사용)
  - ex) deque<int>::iterator iter = dq.begin();
  
  
• dq.end();
  - 마지막의 "다음"을 가리킵니다. (iterator와 사용)
  - ex) deque<int>::iterator iter = dq.end();
  
  

• dq.rbegin();
  - reverse begin을 가리킵니다.
  - 맨 마지막원소를 마치 첫 번째 원소처럼 가리킵니다. (역으로)
  - iterator와 사용.
  - ex) deque<int>::iterator iter = dq.rbegin();
  
  

• dq.rend();
  - reverse end 을 가리킵니다.
  - 맨 첫번째 원소의 "앞"을 마지막 원소의 "다음" 처럼 가리칩니다.
  - iterator와 사용.
  - ex) deque<int>::iterator iter = dq.rend();
  
  
  
• dq.resize(n);
  - 크기를 n 으로 변경합니다.
  - 만약 크기가 더 커졌을 경우 비어있는 원소를 default값인 0으로 초기화 합니다.

• dq.resize(n,2);
  - 크기를 n 으로 변경합니다.
  - 만약 크기가 더 커졌을 경우 빈 원소를 2로 초기화합니다.
  
  
• dq.size();
  - 원소의 개수를 리턴합니다.
  
  

• dq2.swap(dq1);
  - dq1과 dq2를 바꾸어 줍니다. (swap)
  
  
  
• dq.insert(1, 2, 3);
  - 1번째 위치에 2개의 3값을 삽입합니다.
  - 삽입 시에 앞뒤 원소의 개수를 판단하여 적은 쪽으로 미루어서 삽입합니다.
  - 만약 앞의 원소의 개수가 적을 경우, 앞쪽으로 블록을 만들어서 원소를 옮기고 삽입합니다.
  - 만약 뒤의 원소의 개수가 적을 경우, 뒤쪽으로 블록을 만들어서 원소를 옮기고 삽입합니다.
  
  
• dq.insert(3, 4);
  - 3번째 위치에 4의 값을 삽입합니다.
  - 삽입한 곳의 iterator를 반환합니다.
  
  
• dq.erase(iter);
  - iter가 가리키는 원소를 제거합니다.
  - 제거 한 후 앞 뒤의 원소의 개수를 판단하여 적은쪽의 원소를 당겨서 채웁니다.
  - 제거한 곳의 iterator 를 반환합니다.
  

• dq.empty()
  - dq가 비었으면 true를 반환합니다.

5) 다양한 예제

예제 1, 2) 앞뒤 삽입, 역으로 출력.

#include <iostream>
#include <deque>
 
using namespace std;
 
int main() {
    deque<int> dq;
 
    for(int i=0; i<5; i++){
        dq.push_back((i+1) *10);
    }
 
    //iterator 선언
    deque<int>::iterator iter;
 
    //[default 출력]
    cout << "[Default] : " ;
    for(iter = dq.begin(); iter != dq.end() ; iter++){
        cout << *iter << " ";
    }
    cout << endl << endl;
 
    //[test1] : 앞 뒤 삽입
    cout << "[Test1] push_front & end : " ;
 
    dq.push_front(1);
    dq.push_front(2);
    dq.push_back(100);
    dq.push_back(200);
    
    for(iter = dq.begin(); iter != dq.end() ; iter++){
        cout << *iter << " ";
    }
    cout << endl ;
    
    
    //[test2] : 역으로 출력
    cout << "[Test2] reverse_iterator : ";
    
    deque<int>::reverse_iterator rIter;
    
    for(rIter = dq.rbegin(); rIter != dq.rend() ; rIter++) {
        cout << *rIter << " ";
    }
    cout << endl ;
    
    
    return 0;
}

> 예제 1,2 결과

예제 3, 4) 중간삽입, 삭제, 출력의 2가지 방법.

#include <iostream>
#include <deque>
#include<string>
using namespace std;
 
int main() {
    deque<string> dq;
 
    dq.push_front("Dok2");
    dq.push_back("ZICO");
    dq.push_front("Tiger_JK");
 
 
    cout << "[Default]" << endl;
    deque<string>::iterator iter;
    for(iter = dq.begin(); iter!= dq.end() ; iter++){
        cout << *iter << " " ;
    }
    cout << endl << endl;
 
    cout << "[Test3] insert(conIter ++ 두번, 2, INSERT)"<<endl;
    deque<string>::const_iterator conIter = dq.begin();
    conIter+=2;
    dq.insert(conIter, 2, "INSERT");
    for(iter = dq.begin(); iter!= dq.end() ; iter++){
        cout << *iter << " " ;
    }
 
    cout << endl << endl;
 
 
 
    cout << "[Test4] dq.end() 의 전전 erase, erase" << endl;
    conIter = dq.end();
    //end 가 맨 마지막의 "다음"을 가리키므로 맨 마지막을 가리키도록 한번 -- 해줍니다.
    conIter--;
 
    //한번더 -- ;
    conIter--;
 
    dq.erase(conIter);
    for(iter = dq.begin(); iter!= dq.end() ; iter++){
        cout << *iter << " " ;
    }
    cout << endl;
 
    dq.erase(conIter);
    for(iter = dq.begin(); iter!= dq.end() ; iter++){
        cout << *iter << " " ;
    }
    cout << endl << endl;
 
 
    cout << "[Test5-1] dq.at(i) : " ;
 
    deque<string>::size_type i;
    for(i=0 ; i<dq.size() ; i++){
        cout << dq.at(i) << " " ;
    }
    cout << endl;
 
 
    cout << "[Test5-2]  dq[i]  : " ;
 
    for(i=0 ; i<dq.size() ; i++){
        cout << dq[i] << " " ;
    }
    cout << endl;
 
 
    return 0;
}