본문 바로가기
<개인공부>/[C++]

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

by 사용자 BlockDMask 2017. 7. 23.
반응형

<목차>

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) 앞뒤 삽입, 역으로 출력.
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
#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;
}
cs

> 예제 1,2 결과


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

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
64
65
66
67
68
69
70
71
72
#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;
}
cs


> 예제 3,4,5 결과


반응형

댓글2

  • 나그네 2018.01.07 05:58

    예제 3,4)의 47번 라인에서 offset out of range 런타임에러가 납니다.
    dq.erase(conIter)를 실행한면 conIter의 인덱스에 변화가 오는듯 합니다.
    왜 그럴까요?


    답글

  • dcdnf 2019.12.30 15:59

    저런충격적인구조가있을수가있습니까?
    어떻게 연산자[] 가 작동하는거죠? 각 메모리 블록은 항상 4로 일정한건가요? 중간에 데이터를 삽입하면 앞으로 밀려나는건가요 뒤로 밀려나는건가요? 연산자= 나 복사생성자 이동생성자가 작동하면ㅡ 만약 첫번째 메모리 블록이 2개 비워져있다면 그 2개의 비워진 데이터도 복사해오나요 아님 뒤의 데이터를 전부 당겨서 가져오나요?
    많은 의문점을 다 합쳐서 말하자면. 어이가없네요 . . .
    답글