[C++ STL] std::deque (시퀀스 컨테이너)

std::deque

deque 컨테이너는 시퀀스 컨테이너이며 배열 기반(연속적인 메모리) 기반의 컨테이너.

 -> deque(double ended queue)는 앞과 뒤에서 삽입과 삭제가 가능한 자료구조.

출처 - https://blog.daum.net/coolprogramming/81

deque 컨테이너는 위 그림과 같이 앞과 뒤에 데이터들이 추가될 수 있는 형태. 또한 데이터 요소를 저장하는 여러개의 메모리 단위를 갖는다.

std::vector 컨테이너와 비슷하면서도 가장 큰 차이점이 존재하는데, vector의 경우에는 배열이 가득차면 새로운 메모리 블럭을 만들고 기존의 데이터를 복사한 다음 기존의 메모리 블럭을 부숴버린다.

deque의 경우에는 메모리가 가득차도 복사 후 파괴(이사)가 아닌 새로운 메모리 블럭을 하나 더 만들뿐이다.

 

출처 - https://blog.daum.net/coolprogramming/81

위 그림처럼 하나의 메모리 블럭에서 요소가 가득찼지만 메모리를 새로 할당하고 복사한 다음 기존의 메모리 블럭을 해제하는 vector와는 달리 새로운 메모리 블럭을 하나 더 할당한다.

deque는 위와 같은 구조를 가지고 있기에 vector와 달리 push_front, pop_front가 존재하며 중간에서 원소를 삽입/삭제를 하는경우에도 vector에 비해 효율이 좀 더 낫다.

 

먼저 std::deque를 사용하기 위해서 deque 헤더파일을 추가해야 한다.

기본적인 생성방법

// 비어있는 deque 컨테이너 객체를 만든다.
std::deque<int> dq;
// 0으로 초기화된 요소를 10개 가진 상태로 deque 컨테이너 객체를 만든다.
std::deque<int> dq2(10);
// 4로 초기화된 요소를 10개 가진 상태로 deque 컨테이너 객체를 만든다.
std::deque<int> dq3(10,4);
// dq3의 컨테이너를 dq4로 복사하여 생성한다.
std::deque<int> dq4(dq3);

 

이제 멤버함수를 하나씩 살펴보자 (자주 사용하는것 위주로)

 

1. at함수, operator [] 연산자

std::deque<int> dq(10,4);
std::cout << &dq.at(4) << " " << &dq[4] << std::endl;

at함수의 인자로 넘긴 값과 operator []연산자에 넘긴 인자값은 넘긴 인자번째의 원소에 접근다.

deque컨테이너도 기본적으로 배열의 형태로 데이터를 저장한다. (여러개의 배열)

물론 메모리 블럭이 여러개 존재하는 구조이지만, 기본적으로 배열의 형태이기에 operator []연산자도 지원한다.

at함수는 유효범위를 체크하므로 operator []연산으로 접근하는것보다 상대적으로 속도가 느리다.

 

2. push_back, pop_back

std::deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40); //가득찬 상태라고 가정
dq.push_back(50); //하나의 메모리 블럭을 더 생성 후 저장.

push_back 함수는 제일 마지막 요소의 뒤에 데이터를 저장한다.

만약 하나의 메모리 블럭의 최대 크기가 4라고 할 때 위의 경우에서 40을 저장한 후 50을 저장할 때 하나의 메모리 블럭을 더 생성한다.

출처 - https://blog.daum.net/coolprogramming/81

std::deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40); //가득찬 상태라고 가정
dq.push_back(50); //하나의 메모리 블럭을 더 생성 후 저장.
    
dq.pop_back(); // 맨 뒤의 요소를 제거한다.

pop_back함수. 단순히 맨 뒤의 요소를 제거한다.

 

3. push_front, pop_front

std::deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40); //가득찬 상태라고 가정    
 
dq.push_front(100);
dq.push_front(200);
dq.push_front(300);

push_front 함수는 제일 처음의 요소 앞에 데이터를 추가한다.

처음 소개때 말했듯이 deque는 여러개의 메모리 단위를 갖는 형태. 제일 앞에 데이터를 추가한다 해서 vector처럼

메모리를 새로 만들고 복사한 후 기존의 메모리를 부술필요 없이 밑의 그림과 같은 형태로 데이터를 추가해간다.

출처 - https://blog.daum.net/coolprogramming/81

std::deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40); //가득찬 상태라고 가정    
 
dq.push_front(100);
dq.push_front(200);
dq.push_front(300);
 
dq.pop_front();

pop_front는 제일 처음의 요소를 제거한다. 위 코드에서 제일 앞의 요소는 300. 300이 제거된다.

 

4. insert, erase 함수

std::deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40);
auto iter = (dq.begin() + 1); // 반복자는 20을 가리킨다.
dq.insert(iter,500);

insert함수는 해당하는 반복자 위치(첫번쨰 인자)에 데이터(두번째 인자)를 저장한다.

 -> 삽입은 항상 반복자가 가리키는 위치 앞에 삽입된다. (시퀀스 컨테이너)

위 그림에서부터 하나의 메모리 블럭 크기가 최대 4라고 가정했는데, 위의 경우 500을 추가하면 20의 앞에 데이터가 삽입이 된다. 그럼 10은 밀려나게 되는 것.

위 그림과 같이 중간에 데이터를 삽입할 때에도 데이터가 밀려나가면 새로운 메모리 블럭을 하나 더 생성하여 밀려난 데이터를 저장한다.

삽입시에 체크과정이 하나 존재하는데, 삽입 시 앞뒤의 요소의 개수를 판단하여 적은 쪽으로 밀고난 후 삽입한다.

즉 위의 그림의 경우에는 삽입할 20의 자리를 기준으로 앞쪽 요소의 개수가 더 작으므로 앞쪽으로 밀어낸다.

 -> 반대의 경우에는 뒤로 밀어낸다.

 

erase함수도 비슷하다.

std::deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40);
auto iter = (dq.begin() + 1); // 반복자는 20을 가리킨다.
dq.insert(iter, 500);
iter = (dq.begin() + 1); // 반복자는 500을 가리킨다.
 
dq.erase(iter);

현재 메모리 블럭은 밑 그림과 같은 상태

현재 inert 500을 하고난 후 다시 begin() + 1을 하여 반복자를 반환받았는데 이 반복자는 500을 가리키고 있다.

500을 가리키는 반복자를 erase의 인자로 넘겨주면 해당 위치의 데이터를 제거한 후 앞과 뒤의 요소의 수를 판단하여 더 적은쪽을 뒤로 당긴다.

 

나머지 멤버함수인 begin,end,rbegin,rend,swap,size,resize,empty등의 함수는 앞에서 배운 컨테이너 함수와 다른게 없다.

 

deque 컨테이너의 장점

 - vector처럼 데이터를 담을 수 있는 크기가 가변적이지만, 비용은 vector에 비해 가볍다.

 - 맨 앞과 맨 뒤의 삽입과 삭제가 좋다. (맨 앞의 원소를 삭제한다고 한칸 앞으로 당기지 않는다)

 - 임의 접근 연산자가 가능하다.

 

deque 컨테이너의 단점

 - deque 컨테이너의 메모리 정책상 처음부터 끝까지 연속적인 메모리 공간이 아니므로 임의 접근 연산이 가능한것과는 별개로 포인터 연산을 통해 데크의 원소들을 안전하게 접근할 수 없다.  (본문의 deque의 메모리 할당 정책 그림을 확인)

 - vector 컨테이너 보다는 중간 삽입/삭제가 좀 더 좋은 효율성을 보이지만 list 컨테이너에 비해서는 좋지못한 성능.

 - deque는 앞의 삽입/삭제 (뒤는 제외. vector의 뒤의 삽입이 재 할당이 안 일어난다는 조건), 중간 삽입/삭제를 제외한 나머지 기능은 vector보다 성능이 별로 좋지 못하다.

 

처음과 끝에 데이터가 자주 삽입/삭제가 된다면 deque를. 그 외의 경우에는 vector,list를 사용하는게 좋다.

 

 

 

 

 

 

참고한 사이트 https://blog.daum.net/coolprogramming/81