한빛출판네트워크

제공 : 한빛 네트워크
저자 : 최흥배
이전기사 :

• About STL : C++ STL 프로그래밍(1)
• About STL : C++ STL 프로그래밍(2-1)
• About STL : C++ STL 프로그래밍(2-2)
• About STL : C++ STL 프로그래밍(3)
• About STL : C++ STL 프로그래밍(4)

이번 회는 STL 컨테이너 라이브러리 중 하나인 deque를 설명합니다. 앞 회의 list, vector 글을 보신 분들은 아시겠지만 STL 컨테이너 라이브러리는 사용하는 방법이 서로 비슷하므로 하나만 잘 알면 다른 컨테이너도 쉽게 배울 수 있습니다. 이전에 연재했던 list나 vector에 대한 글을 보지 않은 분은 꼭 보신 후 이 글을 보기를 권합니다. 또 이미 list나 vector를 알고 있는 분들은 deque의 자료구조 및 특징을 잘 파악하기를 바랍니다.

5.1 deque의 자료구조

deque의 자료구조는 이름과 같이 Deque(Double Ended Queue) 자료구조입니다. Deque 자료구조는 Queue 자료구조와 비슷하므로 먼저 Queue 자료구조를 설명하겠습니다. Queue는 선형 리스트로 선입선출(FIFO) 방식을 사용합니다. 아래 그림처럼 시작과 끝을 가리키는 포인터로 삽입과 삭제를 합니다.


[그림 1] 큐(Queue) 자료구조

[그림 1]에서 F(Front)는 가장 앞에 있는 것을 가리키며 삭제 작업을 할 때 사용합니다. 위 그림에서 삭제를 한다며 ‘a’는 없어지고 F는 ‘b’를 가리킵니다. R(Rear)은 가장 마지막에 있는 것을 가리키며 삽입 작업을 할 때 사용합니다. 위 그림에서 ‘g’를 추가하면 ‘f’ 다음에 위치하며 R은 ‘f’를 가리킵니다.

Queue는 앞으로는 삭제, 뒤로는 삽입을 할 때 사용합니다.

OS의 작업 스케줄링처럼 입력 순서대로 처리를 할 때 Queue를 사용하면 좋습니다. Deque과 Queue와 다른 점은 삽입과 삭제를 한쪽이 아닌 앞, 뒤 양쪽에서 할 수 있다는 것만 다르며 Queue와 같습니다.


[그림 2] 덱(Deque) 자료구조

[그림 1]과 다르게 [그림 2]를 보면 앞과 뒤에서 삽입과 삭제를 할 수 있습니다. Deque는 Stack과 Queue의 장점을 모은 것으로 FIFO 방식과 LIFO 방식 둘 다 사용할 수 있습니다.

5.2 Deque의 특징

Deque의 장점을 정리하면 아래와 같습니다.

1. 크기가 가변적이다.
리스트와 같이 데이터를 담을 수 있는 크기가 가변적입니다.

2. 앞과 뒤에서 삽입과 삭제가 좋다.
Deque가 다른 자료구조와 가장 다른 점으로 앞과 뒤에서 삽입, 삭제가 좋습니다.

3. 중간에 데이터 삽입, 삭제가 용이하지 않다.
데이터를 중간에 삽입하거나 삭제하는 것은 피해야 합니다. 삽입과 삭제를 중간에 한다면 삽입하거나 삭제한 위치 앞뒤 데이터를 모두 이동해야 합니다.


[그림 3] 데이터 g를 중간에 삽입하는 과정


[그림 4] 데이터 c를 삭제하는 과정

4. 구현이 쉽지 않다.
Deque은 Stack과 Queue가 결합된 자료구조로 연결 리스트보다 구현하기가 더 어렵습니다.

5. 랜덤 접근이 가능하다.

연결 리스트처럼 리스트를 탐색하지 않고 원하는 요소에 바로 접근할 수 있습니다.

5.3 deque를 사용하는 경우

Deque의 특징을 고려할 때 다음과 같은 경우에 사용하면 좋습니다.

1. 앞과 뒤에서 삽입, 삭제를 한다.
이것이 deque를 사용하는 가장 큰 이유입니다. 대부분 작업이 데이터를 앞이나 뒤에 삽입, 삭제를 한다면 STL 컨테이너 라이브러리 중에서 deque를 사용할 때 성능이 가장 좋습니다.

2. 저장할 데이터 개수가 가변적이다.
저장할 데이터 개수를 미리 알 수 없어도 deque는 크기가 동적으로 변하므로 유연하게 사용할 수 있습니다.

3. 검색을 거의 하지 않는다.
많은 데이터를 저장한다면 앞 회에서 여러 번 언급했듯이 map, set, hash_map 중 하나를 선택해서 사용하는 편이 좋습니다.

4. 데이터 접근을 랜덤하게 하고 싶다.
vector와 같이 랜덤 접근이 가능합니다. 사용하는 방법도 같습니다.

5.4 deque VS vector

deque는 전체적으로 멤버 함수의 기능이나 사용 방법이 vector와 거의 같습니다. vector는 삽입과 삭제를 뒤(back)에서만 해야 성능이 좋지만, deque는 삽입과 삭제를 앞과 뒤에서 해도 좋으며 앞뒤 삽입, 삭제 성능도 vector보다 좋습니다. 하지만, deque는 앞뒤에서 삽입, 삭제하는 것을 제외한 다른 위치에서의 삽입과 삭제는 vector보다 성능이 좋지 않습니다.

	deque	vector
크기 변경 가능	O	O
앞에 삽입, 삭제 용이	O	X
뒤에 삽입, 삭제 용이	O	O
중간 삽입, 삭제 용이	X	X
순차 접근 가능	O	O
랜덤 접근 가능	O	X

[표 1] deque와 vector의 차이

deque와 vector를 비교할 때 고려해야 되는 점은
deque는 앞과 뒤에서 삽입과 삭제 성능이 vector보다 더 좋다.
deque는 앞과 뒤 삽입, 삭제를 제외한 기능은 vector보다 성능이 좋지 못하다.

---

게임 서버에서 deque를 사용하는 경우

게임 서버는 클라이언트에서 보낸 패킷을 차례대로 처리합니다. 서버에서 네트워크 데이터를 받는 함수에서 데이터를 받으면 패킷으로 만든 후 받은 순서대로 순차적으로 처리합니다. 이렇게 순차적으로 저장한 패킷을 처리할 때는 deque가 가장 적합한 자료구조입니다. 다만, 실제 현업에서는 이 부분에 STL의 deque를 사용하지 않는 경우가 종종 있습니다. 이유는 네트워크에서 데이터를 받아 패킷으로 만들어 저장하고, 그 패킷을 처리하는 부분은 게임 서버의 성능 면에서 가장 중요한 부분이므로 deque보다 더 빠르게 처리하기를 원하므로 독자적인 자료구조를 만들어 사용합니다(즉, 범용성보다는 성능을 우선시합니다).

---

5.5 deque 사용 방법

deque를 사용하려면 deque 헤더 파일을 포함합니다.

#include 

deque 형식은 아래와 같습니다.

deque< 자료 type > 변수 이름

int를 사용하는 deque 선언은 아래와 같습니다.

deque< int > deque1;

deque도 동적 할당을 할 수 있습니다.

deque< 자료 type >* 변수 이름 = new deque< 자료 type >;
deque< int >* deque1 = new deque< int >;

5.5.1 deque의 주요 멤버들

deque 멤버 중 일반적으로 자주 사용하는 멤버들입니다. vector에 없는 pop_front와 push_front가 있다는 것 빼고는 vector의 기능과 같습니다.

멤버	설명
assign	특정 원소로 채운다
at	특정 위치의 원소의 참조를 반환
back	마지막 원소의 참조를 반환
begin	첫 번째 원소의 랜던 접근 반복자를 반환
clear	모든 원소를 삭제
empty	아무것도 없으면 true 반환
End	마지막 원소 다음의(미 사용 영역) 반복자를 반환
erase	특정 위치의 원소나 지정 범위의 원소를 삭제
front	첫 번째 원소의 참조를 반환
insert	특정 위치에 원소 삽입
pop_back	마지막 원소를 삭제
pop_front	첫 번째 원소를 삭제
push_back	마지막에 원소를 추가
push_front	제일 앞에 원소 추가
rbegin	역방향으로 첫 번째 원소의 반복자를 반환
rend	역방향으로 마지막 원소 다음의 반복자를 반환
reserve	지정된 크기의 저장 공간을 확보
size	원소의 개소를 반환
swap	두 개의 vector의 원소를 서로 맞바꾼다

[표 2] 자주 사용하는 deque 멤버

5.5.2. 기본 사용 멤버

deque의 가장 기본적인(추가, 삭제, 접근 등) 사용법을 설명합니다.

멤버	원형	설명
at	reference at( size_type _Pos ); const_reference at( size_type _Pos ) const;	특정 위치의 원소의 참조를 반환
back	reference back( ); const_reference back( ) const;	마지막 원소의 참조를 반환
begin	const_iterator begin() const; iterator begin();	첫 번째 원소의 랜던 접근 반복자를 반환
clear	void clear();	모든 원소를 삭제
empty	bool empty() const;	아무것도 없으면 true 반환
end	iterator end( ); const_iterator end( ) const;	마지막 원소 다음의(미 사용 영역) 반복자를 반환
front	reference front( ); const_reference front( ) const;	첫 번째 원소의 참조를 반환
pop_back	void pop_back();	마지막 원소를 삭제
pop_front	void pop_front( );	첫 번째 원소를 삭제
push_back	void push_back( const Type& _Val );	마지막에 원소를 추가
push_front	void push_front( const Type& _Val );	제일 앞에 원소 추가
rbegin	reverse_iterator rbegin( ); const_reverse_iterator rbegin( ) const;	역방향으로 첫 번째 원소의 반복자를 반환
rend	const_reverse_iterator rend( ) const; reverse_iterator rend( );	역방향으로 마지막 원소 다음의 반복자를 반환
size	size_type size() const;	원소의 개수를 반환

[표 3] 추가, 삭제, 접근 등에 사용하는 멤버들


[그림 5] deque의 추가, 삭제, 접근 멤버들

추가

앞과 뒤에 추가를 할 수 있습니다. 보통 deque를 사용할 때는 뒤에 추가를 하고 앞에서는 삭제를 합니다. 앞쪽 추가는 push_front()를 사용합니다.

deque< int > deque1;
deque1.push_front( 100 );

뒤에 추가할 때는 push_back()을 사용합니다.

deque< int > deque1;
deque1.push_back( 200 );

삭제

앞과 뒤에서 삭제 할 수 있습니다. 앞에서 삭제를 할 때는 pop_front()를 사용합니다.

deque1.pop_front();

뒤에서 삭제를 할 때는 pop_back()를 사용합니다.

deque1.pop_back();

접근

첫 번째 위치의 반복자를 얻을 때는 begin()을 사용합니다.

deque< int >::iterator IterBegin = deque1.begin();
cout << *IterBegin << endl;

반복자로 다른 원소에 접근을 할 때는 반복자에 ‘++’ 이나 ‘–-‘을 사용합니다.

deque< int >::iterator IterPos = deque1.begin();

// 두 번째 위치로 이동
++IterPos;
// 첫 번째 위치로 이동
--IterPos;

end()는 deque에 저장된 원소 중 마지막 다음 위치, 즉 사용하지 못하는 영역을 가리킵니다. 보통 반복문에서 컨테이너에 남은 원소가 있는지 조사할 때 주로 사용합니다.

deque< int >::iterator IterEnd = deque1.end();
for(deque< int >::iterator IterPos = deque1.begin; IterPos != IterEnd;
     ++IterPos )
{
   ……
}

첫 번째 위치에 있는 데이터를 얻을 때는 front(), 마지막 위치에 있는 데이터를 얻을 때는 back()을 사용합니다.

int& FirstValue = deque1.front();
int& LastValue = deque1.back();

begin()과 end()는 순방향으로 앞과 뒤를 가리키고, 역방향으로는 rbegin()과 rend()를 사용합니다. 특정 위치에 있는 데이터를 얻을 때는 at()이나 배열 식 접근([])을 사용합니다.

int& Value2 = deque1.at(1); // 두 번째 위치
int Value3 = deque1[2];      // 세 번째 위치

모두 삭제

clear()를 사용하면 저장한 모든 데이터를 삭제합니다.

deque1.clear();

데이터 저장 여부

deque에 저장한 데이터가 있는지 없는지는 empty()로 조사합니다. 데이터가 있으면 false, 없다면 true를 반환합니다.

bool bEmpty = deque1.empty();

저장된 원소 개수 조사

size()로 deque에 저장된 데이터 개수를 조사합니다.

deque< int >::size_type TotalCount = deque1.size();

지금까지 설명한 deque 멤버들의 사용법을 보면 전 회에 설명한 vector와 같다는 것을 충분히 알 수 있을 것입니다. vector를 공부하신 분들은 아주 쉽죠? ^^ 이후에 소개하는 내용도 vector에서 설명한 것과 같으니 편안하게 잘 따라와 주세요.