[C++ STL] 시퀀스 컨테이너 - 덱(deque)

vector와 동일하며, 아래는 추가된 멤버 함수 입니다. ( capacity(), reserve() 함수는 vector만 가지므로, deque, list는 없음 )

 

멤버 함수
dq.pop_front()	dq의 첫 원소를 제거한다.
dq.push_front(x)	dq의 앞쪽에 x를 추가한다.

 

deque 컨테이너는 vector 컨테이너와 기능과 동작이 가장 비슷한 컨테이너로 vector의 단점을 보완하는 몇 가지 특징을 갖습니다. deque도 vector 컨테이너와 같이 시퀀스 컨테이너이며 배열 기반 컨테이너 입니다.

 

※ 중요

deque이 vector와 다른 점은 메모리 블록 할당 정책입니다.

deque은 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용합니다.

원소의 추가 시 메모리가 부족할때마다 일정한 크기의 새로운 메모리 블록을 할당하여 이전 메모리를 제거하거나 이전 원소를 복사하는 등의 연산을 수행하지 않습니다.

 

즉! vector 처럼 메모리가 부족하여, 새로운 메모리 블록을 만들고, 다시 원소를 복사하는 일은 없습니다.

 

[ deque 기본 생성 ]

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <iostream> #include <deque> using namespace std;   int main(){       deque<int> dq;     dq.push_back(10);     dq.push_back(20);     dq.push_back(30);     dq.push_back(40);     dq.push_back(50);       deque<int>::iterator Iter = dq.begin();     for( ; Iter != dq.end(); ++Iter ){         cout<< *Iter <<endl;     }       system("pause");     return 0; }

 

 

[ deque의 push_front() ]

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12

deque<int> dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); dq.push_back(40); dq.push_back(50);   dq.push_front(100);// 앞쪽에 추가합니다. dq.push_front(200);     for(deque<int>::size_type i = 0; i< dq.size(); ++i ){     cout<< dq[i] <<endl; }

 

deque은 원소를 앞쪽에 추가하면 새로운 메모리 블록을 할당하고 원소를 저장해 갑니다.

deque의 반복자는 vector의 반복자와 동일하게 동작합니다.

 

deque의 insert() 멤버함수는 vector보다 효율적으로 동작합니다.

 

Colored By Color Scripter™

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

#include <iostream> #include <deque> using namespace std;   int main(){       deque<int> dq;     dq.push_back(10);     dq.push_back(20);     dq.push_back(30);     dq.push_back(40);     dq.push_back(50);       // 30을 가르킴     deque<int>::iterator Iter = dq.begin()+2;     deque<int>::iterator Iter_Insert = dq.insert(Iter, 100);       for( Iter = dq.begin(); Iter != dq.end(); ++Iter ){         cout<< *Iter <<" ";     }     cout<<endl;     cout<< *Iter_Insert <<endl;       system("pause");     return 0; }

 

위의 예제에서 Iter는 30을 가르키는데, Iter가 가리키는 위치보다 삽입할 원소(100)이 앞쪽에 삽입 됩니다.

블럭 -> 10, 20, 100, 30, 40 ( Iter를 기준으로 앞쪽 원소 2개, Iter를 포함한 뒤쪽원소는 3개 )

블럭 -> 50

 

이렇게 삽입되면 Iter가 가리키는 원소(100)의 앞쪽 원소 개수가 적기 때문에 앞쪽으로 밀어내며 삽입이 됩니다.

블럭 ->                 10 <- 메모리 할당

블럭 -> 20, 100, 30, 40

블럭 -> 50

 

deque의 erase() 멤버함수도 vector처럼 제거될 위치부터 모든 원소를 밀어내지만,

vector보다는 조금 더 효율적으로 동작합니다.

 

vector는 모든 원소를 뒤쪽으로만 밀어 내지만 deque은 뒤쪽이나 앞쪽으로 밀어낼 수 있기 때문입니다.