Unity3D

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

• 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)
• About STL : C++ STL 프로그래밍(5-1)
• About STL : C++ STL 프로그래밍(5-2)

About STL을 보시는 분은 대부분 아직 STL을 잘 모르는 분들이라고 생각합니다. 제가 일하고 있는 게임업계는 주력 언어가 C++입니다. 그래서 취업 사이트에 올라온 프로그래머 채용 공고를 보면 필수 조건에 거의 대부분이 C++와 STL 사용 가능이 들어가 있습니다. 게임 업계뿐 아니라 C++을 사용하여 프로그래밍하는 곳이라면 대부분 C++과 STL을 사용하여 프로그램을 만들 수 있는 실력을 필요로 합니다.
C++ 언어를 배우고 사용하는 프로그래머라면 STL을 배우면 좋고, 특히 게임 프로그래머가 되실 분들은 STL을 꼭 사용할 줄 알아야 됩니다.
작년 여름부터 About STL을 쓰기 시작하여 지금은 2009년이 되었습니다. About STL 집필 계획으로는 이제 반 정도 도달한 것 같습니다. 앞으로 남은 반도 STL을 습득하는데 도움이 되도록 저도 최대한 노력할 테니 2009년에는 STL을 꼭 마스터하기를 바랍니다. 

6.1 시퀸스 컨테이너와 연관 컨테이너 

이전 회까지는 STL의 컨테이너에 대해서 설명했었습니다. STL 컨테이너는 크게 시퀸스 컨테이너와 연관 컨테이너로 나눕니다.
시퀸스 컨테이너는 vector, list, deque와 같이 순서 있게 자료를 보관합니다.
연관 컨테이너는 어떠한 Key와 짝을 이루어 자료를 보관합니다. 그래서 자료를 넣고, 빼고, 찾을 때는 Key가 필요합니다. 


[그림 1] 시퀸스 컨테이너와 연관 컨테이너 

시퀸스 컨테이너는 많지 않은 자료를 보관하고 검색 속도가 중요한 경우에 사용하고, 연관 컨테이너는 대량의 자료를 보관하고 검색을 빠르게 하고 싶을 때 사용합니다. 제가 만드는 온라인 게임 서버에서는 보통 접속한 유저들의 정보를 보관할 때 가장 많이 사용합니다. 

6.2 연관 컨테이너로는 무엇이 있을까요? 

연관 컨테이너로 map, set, hash_map, hash_set이 있습니다. 이것들은 Key로 사용하는 값이 중복되지 않은 때 사용합니다. 만약 중복되는 key를 사용할 때는 컨테이너의 앞에 'multi'를 붙인 multi_map, multi_set, hash_multimap, hash_multiset을 사용합니다. Key의 중복 허용 여부만 다를 뿐 사용방법은 같습니다. 

6.2.1 map, set 과 hash_map, hash_set의 차이는? 

가장 쉽게 알 수 있는 큰 차이는 이름 앞에 'hash'라는 단어가 있냐 없냐의 차이겠죠.^^
네, 'hash'라는 단어가 정말 큰 차이입니다. 
map과 set 컨테이너는 자료를 정렬하여 저장합니다. 그래서 반복자로 저장된 데이터를 순회할 때 넣은 순서로 순회하지 않고 정렬된 순서대로 순회합니다. hash_map, hash_set은 정렬 하지 않으며 자료를 저장합니다. 또 hash라는 자료구조를 사용함으로 검색 속도가 map, set에 비해 빠릅니다. 

map, set과 hash_map, hash_set 중 어느 것을 사용할지 생각할 때는
map, set의 사용하는 경우 : 정렬된 상태로 자료 저장을 하고 싶을 때.
hash_map, hash_set : 정렬이 필요 없으며 빠른 검색을 원할 때. 

를 가장 큰 조건으로 보면 좋습니다. 

6.2.2 hash_map, hash_set은 표준은 아닙니다. 

위에 열거한 연관 컨테이너 중 map과 set은 STL 표준 컨테이너지만 hash_map, hash_set은 표준이 아닙니다. 그래서 보통 STL 관련 책을 보시면 hash_map과 hash_set에 대한 설명은 없습니다. hash_map, hash_set을 쓰려면 라이브러리를 설치해야 할까요? 그럴 필요는 없습니다. STL 표준은 아니지만 오래되지 않은 C++ 컴파일러에서는 대부분 지원합니다. 윈도우에서는 Visual Studio.NET의 모든 버전에서 지원합니다.
STL 표준도 아닌 hash_map을 설명하려는 이유는 대부분 C++ 컴파일러에서 지원하고, 새로운 C++ 표준에서는 정식으로 STL에 들어갈 예정이며 현업에서 프로그래밍할 때 아주 유용하게 사용하는 컨테이너이기 때문입니다. 

[참고]
2010년 이내에 새로운 C++ 표준이 만들어질 예정인데 표준이 공표되기 전에 TR1으로 일부 공개하고 있습니다. TR1에서는 hash_map, hash_set과 거의 같은 컨테이너인 unordered_map, unordered_set이 준비되어 있습니다. hash_map, hash_set과 이름만 다를 뿐 컨테이너의 자료구조나 사용방법이 거의 같습니다.
그래서 hash_map, hash_set 사용법을 익히며 자동으로 unordered_map, unordered_set도 익히게 됩니다. 

6.3 hash_map의 자료구조 

hash_map의 자료구조는 '해시 테이블'입니다. 
아래의 [그림 2]에 나와 있듯이 해시 테이블에 자료를 저장할 때는 Key 값을 해시함수에 대입하여 버킷 번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장합니다.
Key 값을 해시 함수에 입력하여 나오는 버킷 번호에 자료를 넣으므로 많은 자료를 저장해도 삽입, 삭제, 검색 속도가 거의 일정합니다. 


[그림 2] 해시 테이블에 자료 넣기 

해시 테이블에 대한 설명은 간단하지 않고 이 글에서는 hash_map 사용법을 간단하게 설명하고 마치려 합니다. 좀 더 자세하게 알고 싶은 분들은 아래의 참고 항목을 꼭 봐 주세요. 

[참고] 해시 테이블 설명
1. http://internet512.chonbuk.ac.kr/datastructure/hash/hash3.htm
2. 좋은 프로그램을 만드는 핵심 원리 25가지(한빛미디어) 

6.4 hash_map을 사용할 때와 사용하지 않을 때 

이전 연재에서 설명한 STL 컨테이너의 장단점은 컨테이너의 자료구조를 보면 알 수 있습니다. hash_map은 해시 테이블을 자료구조로 사용하므로 해시 테이블에 대해 알면 장단점을 파악할 수 있습니다. 해시 테이블은 많은 자료를 저장하고 있어도 검색이 빠릅니다. 그러나 저장한 자료가 적을 때는 메모리 낭비와 검색 시 오버헤드가 생깁니다.
Key 값을 해시 함수에 넣어 알맞은 버킷 번호를 알아 내는 것은 마법 같은 것이 아닙니다. 그러니 hash_map은 해시 테이블을 사용하므로 검색이 빠르다라는 것만 생각하고 무분별하게 hash_map을 사용하면 안됩니다. 컨테이너에 추가나 삭제를 하는 것은 list나 vector, deque가 hash_map보다 빠릅니다. 또 적은 요소를 저장하고 검색할 때는 vector나 list가 훨씬 빠를 수 있습니다. 수천의 자료를 저장하여 검색을 하는 경우에 hash_map을 사용하는 것이 좋습니다. 

hash_map을 사용하는 경우
1. 많은 자료를 저장하고, 검색 속도가 빨라야 한다.
2. 너무 빈번하게 자료를 삽입, 삭제 하지 않는다. 

6.5 Hash_map 사용방법 

STL의 다른 컨테이너와 같이 사용하려면 먼저 헤더 파일과 namespace를 선언해야 합니다. 그러나 여기서 주의할 점은 앞서 이야기 했듯이 hash_map은 표준이 아니므로 표준 STL의 namespace와 다른 이름을 사용하므로 namespace 선언할 때 실수하지 않게 조심하세요.
hash_map 헤더파일을 포함합니다.

#include <hash_map>

hash_map이 속한 namespace는 표준 STL과 다른 'stdext'입니다.

using namespace stdext;

hash_map 선언은 아래와 같습니다.

hash_map< Key 자료 type, Value 자료 type > 변수 이름

위에서는 Value는 저장할 데이터이고, Key는 Value와 가리키는 데이터입니다. 

Key는 int, Value는 float를 사용한다면 아래와 같습니다.

hash_map< int, float > hash1;

다른 컨테이너와 같이 동적 할당을 할 수 있습니다.

hash_map< key 자료 type, Value 자료 type >* 변수 이름 = new hash_map< key 자료 type, Value 자료 type >;
hash_map< int, float >* hash1 = new hash_map< int, float >;

hash_map은 Key와 Value가 짝을 이뤄야 하므로 hash_map을 처음 보는 분들은 이전의 시퀸스 컨테이너와 다르게 좀 복잡하게 보일 것입니다. 그러나 사용이 어려운 것은 아니니 잘 따라와 주세요. 

6.5.1 hash_map의 주요 멤버들 

hash_map 컨테이너를 사용할 때는 거의 대부분 추가, 삭제, 검색 이렇게 3가지를 사용합니다. 핵심 기능인 만큼 아래에 좀 더 자세하게 설명하고, 다른 컨테이너는 앞서 설명한 것과 사용방법이 같으므로 예제 코드로 보여 드리겠습니다. 

6.5.2 추가 

insert 

hash_map 에서는 자료를 추가 할 때 insert를 사용합니다.

원형 : 
pair <iterator, bool> insert( const value_type& _Val );
iterator insert( iterator _Where, const value_type& _Val );
template<class InputIterator> void insert( InputIterator _First, InputIterator _Last );

insert를 사용하는 세 가지 방법 중 첫 번째 방식으로 Key 타입은 int, Value 타입은 float를 추가한다면

hash_map<int, float> hashmap1, hashmap2;

// Key는 10, Value는 45.6f를 추가.
hashmap1.insert(hash_map<int, float>::value_type(10, 45.6f));

두 번째 방식으로는 특정 위치에 추가할 수 있습니다.

// 첫 번째 위치에 key 11, Value 50.2f를 추가
hashmap1.insert(hashmap1.begin(), hash_map<int, float>::value_type(11, 50.2f));

세 번째 방식으로는 지정한 반복자 구간에 있는 것들을 추가합니다.

// hashmap1의 모든 요소를 hashmap2에 추가.
hashmap2.insert( hashmap1.begin(), hashmap1.end() );

6.5.3 삭제 

erase

원형 : 
iterator erase( iterator _Where );
iterator erase( iterator _First, iterator _Last );
size_type erase( const key_type& _Key );

첫 번째 방식은 특정 위치에 있는 요소를 삭제합니다.

// 첫 번째 위치의 요소 삭제.
hashmap1.erase( hashmap1.begin() );

두 번째 방식은 지정한 구역에 있는 요소들을 삭제합니다.

// hashmap1의 처음과 마지막에 있는 모든 요소 삭제
hashmap1.erase( hashmap1.begin(), hashmap1.end() );

세 번째 방식은 지정한 키와 같은 요소를 삭제합니다.

// Key가 11인 요소 삭제.
hashmap1.erase( 11 );

첫 번째와 두 번째 방식의 반환 값으로는 삭제된 요소의 다음의 것을 가리키는 반복자이며 세 번째 방식은 삭제된 개수를 반환합니다. 

6.5.4 검색 

hahs_map에서 검색은 Key를 사용하여 같은 Key를 가지고 있는 요소를 찾습니다.
Key와 같은 요소를 찾으면 그 요소의 반복자를 반환하고, 찾지 못한 경우에는 end()를 가리키는 반복자를 반환합니다.

원형 : 
iterator find( const Key& _Key );
const_iterator find( const Key& _Key ) const;

방식은 두 가지지만 사용법은 같습니다. 차이는 반환된 반복자가 const냐 아니냐의 차이입니다. 참고로 첫 번째 방식은 const가 아니므로 찾은 요소의 Value를 변경할 수 있습니다(참고로 Key는 변경 불가입니다). 두 번째 방식은 Value도 변경할 수 없습니다.

// Key가 10인 요소 찾기.
hash_map<int, float>::Iterator FindIter = hashmap1.find( 10 );

// 찾았다면 Value를 290.44로 변경
If( FindIter != hashmap1.end() )
{
   FindIter->second = 290.44f;
}

begin, clear, count, empty, end, rbegin, rend, size는 앞서 말 했듯이 다른 컨테이너와 사용방법이 비슷하므로 아래 예제 코드를 통해서 사용법을 보여 드리겠습니다. 

[리스트 1] hash_map을 사용한 유저 관리

#include <iostream>
#include <hash_map>
using namespace std;
using namespace stdext;

// 게임 캐릭터
struct GameCharacter
{
  // 아래의 인자를 가지는 생성자를 정의한 경우는
  // 꼭 기본 생성자를 정의해야 컨테이너에서 사용할 수 있다.
  GameCharacter() { }

  GameCharacter( int CharCd, int Level, int Money )
  {
    _CharCd = CharCd;
    _Level = Level;
    _Money = Money;
  }
  int _CharCd;    //  캐릭터 코드
  int _Level;    // 레벨
  int _Money;    // 돈
};

void main()
{
  hash_map<int, GameCharacter> Characters;

  GameCharacter Character1(12, 7, 1000 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(12, Character1));

  GameCharacter Character2(15, 20, 111000 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(15, Character2));

  GameCharacter Character3(200, 34, 3345000 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(200, Character3));
  
  // iterator와 begin, end 사용
  // 저장한 요소를 정방향으로 순회
  hash_map<int, GameCharacter>::iterator Iter1;
  for( Iter1 = Characters.begin(); Iter1 != Characters.end(); ++Iter1 )
  {
    cout << "캐릭터 코드 : " << Iter1->second._CharCd << " |   레벨 : " << Iter1->second._Level 
      << "|  가진 돈 : " <<  Iter1->second._Money << endl; 
  }
  cout << endl; 

  // rbegin, rend 사용
  // 저장한 요소의 역방향으로순회
  hash_map<int, GameCharacter>::reverse_iterator RIter;
  for( RIter = Characters.rbegin(); RIter != Characters.rend(); ++RIter )
  {
    cout << "캐릭터 코드 : " << RIter->second._CharCd << " |   레벨 : " << RIter->second._Level 
      << "|  가진 돈 : " <<  RIter->second._Money << endl; 
  }
  cout << endl << endl;
 
  // Characters에 저장한 요소 수
  int CharacterCount = Characters.size();

  // 검색. 
  // 캐릭터 코드 15인 캐릭터를 찾는다.
  hash_map<int, GameCharacter>::iterator FindIter = Characters.find(15);
  // 찾지 못했다면 FindIter은 end 위치의 반복자가 반환된다.
  if( Characters.end() == FindIter )
  {
    cout << "캐릭터 코드가 20인 캐릭터가 없습니다" << endl;
  }
  else
  {
    cout << "캐릭터 코드가 15인 캐릭터를 찾았습니다." << endl;
    cout << "캐릭터 코드 : " << FindIter->second._CharCd << " |   레벨 : " << FindIter->second._Level 
      << "|  가진 돈 : " <<  FindIter->second._Money << endl;
  }
  cout << endl;

  for( Iter1 = Characters.begin(); Iter1 != Characters.end(); ++Iter1 )
  {
    cout << "캐릭터 코드 : " << Iter1->second._CharCd << " |   레벨 : " << Iter1->second._Level 
      << "|  가진 돈 : " <<  Iter1->second._Money << endl; 
  }
  cout << endl << endl;
  
  // 삭제
  // 캐릭터 코드가 15인 캐릭터를 삭제한다.
  Characters.erase( 15 );
  for( Iter1 = Characters.begin(); Iter1 != Characters.end(); ++Iter1 )
  {
    cout << "캐릭터 코드 : " << Iter1->second._CharCd << " |   레벨 : " << Iter1->second._Level 
      << "|  가진 돈 : " <<  Iter1->second._Money << endl; 
  }
  cout << endl << endl;

  // 모든 캐릭터를 삭제한다.
  Characters.erase( Characters.begin(), Characters.end() );

  // Characters 공백 조사
  if( Characters.empty() )
  {
    cout << "Characters는 비어 있습니다." << endl;
  }
}

결과 

 

6.5.5 lower_bound와 upper_bound 

hash_map에 저장한 요소 중에서 Key 값으로 해당 요소의 시작 위치를 얻을 때 사용하는 멤버들입니다. Key 값의 비교는 크기가 아닌 저장 되어 있는 요소의 순서입니다. 23, 4, 5, 18, 14, 30 이라는 순서로 Key 값을 가진 요소가 저장되어 있으며 Key 값 18과 같거나 큰 것을 찾으면 18, 14, 30이 됩니다. 

lower_bound 

Key가 있다면 해당 위치의 반복자를 반환합니다.

원형 : 
iterator lower_bound( const Key& _Key );
const_iterator lower_bound( const Key& _Key ) const;

upper_bound 

Key가 있다면 그 요소 다음 위치의 반복자를 반환합니다.

원형 : 
iterator lower_bound( const Key& _Key );
const_iterator lower_bound( const Key& _Key ) const;

lower_bound와 upper_bound는 hahs_map에 저장된 요소를 일부분씩 나누어 처리를 할 때 유용합니다. 예를 들면 hash_map에 3,000개의 게임 캐릭터 정보를 저장되어 있으며 이것을 100개씩 나누어서 처리하고 싶을 때 사용하면 좋습니다. 

[리스트 2] lower_bound와 upper_bound 사용 예

#include <iostream>
#include <hash_map>
using namespace std;
using namespace stdext;

// 게임 캐릭터
struct GameCharacter
{
  GameCharacter() { }

  GameCharacter( int CharCd, int Level, int Money )
  {
    _CharCd = CharCd;
    _Level = Level;
    _Money = Money;
  }
  int _CharCd;    //  캐릭터코드
  int _Level;    // 레벨
  int _Money;    // 돈
};

void main()
{
  hash_map<int, GameCharacter> Characters;

  GameCharacter Character1(12, 7, 1000 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(12, Character1));

  GameCharacter Character2(15, 20, 111000 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(15, Character2));

  GameCharacter Character3(7, 34, 3345000 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(7, Character3));

  GameCharacter Character4(14, 12, 112200 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(14, Character4));

  GameCharacter Character5(25, 3, 5000 );
  Characters.insert(hash_map<int, GameCharacter>::value_type(25, Character5));

  hash_map<int, GameCharacter>::iterator Iter1;
  cout << "저장한 캐릭터 리스트" << endl;
  for( Iter1 = Characters.begin(); Iter1 != Characters.end(); ++Iter1 )
  {
    cout << "캐릭터 코드 : " << Iter1->second._CharCd << " |   레벨 : " << Iter1->second._Level 
      << "|  가진 돈 : " <<  Iter1->second._Money << endl; 
  }
  cout << endl;

  cout << "lower_bound(14)" <<endl;
  hash_map<int, GameCharacter>::iterator Iter = Characters.lower_bound(14);
  while( Iter != Characters.end() )
  {
    cout << "캐릭터 코드 : " << Iter->second._CharCd << " |   레벨 : " << Iter->second._Level 
      << "|  가진 돈 : " <<  Iter->second._Money << endl;

    ++Iter;
  }
  cout << endl;

  cout << "upper_bound(7)" <<endl;
  Iter = Characters.upper_bound(7);
  while( Iter != Characters.end() )
  {
    cout << "캐릭터 코드 : " << Iter->second._CharCd << " |   레벨 : " << Iter->second._Level 
      << "|  가진 돈 : " <<  Iter->second._Money << endl;

    ++Iter;
  }
}

결과 

 

이것으로 hash_map의 주요 사용법에 대한 설명이 끝났습니다.
위에 설명한 것들만 알고 있으면 hash_map을 사용하는데 문제가 없을 것입니다.
위에 설명한 것들 이외의 hash_map의 멤버들에 대해서 알고 싶으며 마이크로소프트의 MSDN 사이트에 있는 것을 참고하세요
http://msdn.microsoft.com/en-us/library/h80zf4bx(VS.80).aspx 

[참고]
Visual C++의 hash_map의 성능에 대해서 Visual C++에 있는 hash_map은 다른 컴파일에서 구현한 것보다 꽤 느리다라는 말이 있습니다.
(관련 글은 여기서 참고하세요. http://minjang.egloos.com/1983788 http://junyoung.tistory.com/1) 

얼마나 느린지 테스트했습니다.
http://blog.naver.com/jacking75/140062720030
제가 조사한 것은 Windows 플랫폼에서 VC++에서 제공한 라이브러리로 테스트한 것입니다.
결과를 보면 hash_map이 map보다 빠르지도 않고 특히 hash_map과 같은 자료구조를 사용하는 컨테이너로 마이크로소프트사에서 만든 CAtlMap에 비해 속도가 아주 느립니다.
성능이 중요한 곳에 hash_map을 사용한다면 VC++에 있는 것을 사용하지 말고 자체적으로 잘 만들어진 hash 함수를 사용하거나 C++ 오픈 소스 라이브러리인 boost에 있는 unordered_map을 사용하는 것이 좋을 것 같습니다. Windows 플랫폼에서만 사용한다면 CAtlMap을 사용하는 것도 좋습니다.

출처 : http://www.hanb.co.kr/

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

• 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)
• About STL : C++ STL 프로그래밍(5-1)

5.5.3. deque 실습 예제

다음은 deque에서 가장 자주 사용하는 멤버들을 사용하는 전체 코드입니다. 

[리스트 1]

#include 
#include 

using namespace std;


// 서버/ 클라이언트간에 주고 받는 패킷
struct Packet
{
	unsigned short Index; // 패킷 인덱스
	unsigned short BodySize; // 패킷 보디(실제 데이터)의 크기
	char	       acBodyData[100]; // 패킷의 데이터
};


int main() 
{
	Packet Pkt1;
	Pkt1.Index = 1;		Pkt1.BodySize = 10;

	Packet Pkt2;
	Pkt2.Index = 2;		Pkt2.BodySize = 12;

	Packet Pkt3;
	Pkt3.Index = 3;		Pkt3.BodySize = 14;


	deque< Packet > ReceivePackets;


	// 뒤에 추가
	ReceivePackets.push_back( Pkt2 );
	ReceivePackets.push_back( Pkt3 );

	// 앞에 추가
	ReceivePackets.push_front( Pkt1 );

	
	// 저장된 패킷 정보 출력
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index << endl;
		cout << "패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	cout << endl << "역방향으로 출력" << endl;
	for( deque< Packet >::reverse_iterator iterPos = ReceivePackets.rbegin();
		iterPos != ReceivePackets.rend();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index << endl;
		cout << "패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	cout << endl << "배열 방식으로 접근" << endl;
	// 저장된 총 패킷 수
	int ReceivePacketCount = ReceivePackets.size();
	cout << "총 패킷 수: " << ReceivePacketCount << endl;
	for( int i = 0; i < ReceivePacketCount; ++i )
	{
		cout << "패킷 인덱스: " << ReceivePackets[i].Index << endl;
		cout << "패킷 바디 크기: " << ReceivePackets[i].BodySize << endl;
	}


	// 첫 번째, 마지막 위치에 있는 패킷
	Packet& FirstPacket = ReceivePackets.front();
	cout << "첫 번째 패킷의 인덱스: " << FirstPacket.Index << endl;

	Packet& LastPacket = ReceivePackets.back();
	cout << "마지막 패킷의 인덱스: " << LastPacket.Index << endl;

	// at을 사용하여 두 번째 패킷
	Packet& PacketAt = ReceivePackets.at(1);
	cout << "두 번째 패킷의 인덱스: " << PacketAt.Index << endl;


	// 첫 번째 패킷 삭제
	ReceivePackets.pop_front();
	cout << "첫 번째 패킷의 인덱스: " << ReceivePackets[0].Index << endl;

	// 마지막패킷삭제
	ReceivePackets.pop_back();
	LastPacket = ReceivePackets.back();
	cout << "마지막 패킷의 인덱스: " << LastPacket.Index << endl;

	// 모든 패킷을 삭제
	if( false == ReceivePackets.empty() )
	{
		cout << "모든 패킷을 삭제합니다." << endl;
		ReceivePackets.clear();
	}
}

결과 

5.5.3.1. insert 멤버

deque의 insert는 vector의 insert와 사용 방법이 같습니다. 지정된 위치에 삽입, 지정된 위치에 지정된 개수만큼 삽입, 지정된 위치에 반복자 구간 안에 있는 것들을 삽입이 있습니다. vector와 같이 insert는 삽입 되는 위치 이후에는 있는 모든 원소들이 뒤로 이동을 합니다. 그리고 insert의 성능은 vector 보다도 더 좋지 않습니다.

원형 : iterator insert( iterator _Where, const Type& _Val );
      void insert( iterator _Where, size_type _Count, const Type& _Val );
      template void insert( iterator _Where, InputIterator _First, 
                                            InputIterator _Last );

 
[그림 6] deque의 insert 처리 과정 

지정한 위치에 데이터 삽입. 아래는 300을 첫 번째 위치에 삽입합니다.

deque< int >::iterator iterInsertPos = deque1.begin();
deque1.insert( iterInsertPos, 300 );

지정한 위치에 데이터를 횟수만큼 삽입. 아래는 두 번째 위치에 10을 3번 추가합니다.

iterInsertPos = deque1.begin();
++iterInsertPos;
deque1.insert( iterInsertPos, 3, 10 );

지정한 위치에 반복자의 시작과 끝 안에 있는 원소를 삽입. 아래는 두 번째 위치에 deque2의 처음과 끝에 있는 원소를 삽입합니다.

deque< int > deque2;
deuqe2.push_back( 20 );
deuqe2.push_back( 30 );
deuqe2.push_back( 40 );

iterInsertPos = deque1.begin();
deque1.insert( ++iterInsertPos, deque2.begin(),deque2.end() );

5.5.3.2. erase 멤버

지정한 위치에 있는 원소를 삭제, 지정한 범위 안에 있는 원소를 삭제합니다. vector와 사용법이 같고 또 erase를 하는 위치 이후의 모든 원소들이 앞으로 이동하는 것도 같습니다.

원형 : iterator erase( iterator _Where );
      iterator erase( iterator _First, iterator _Last );

 
[그림 7] deque의 erase 처리 과정 

지정한 위치의 요소를 삭제. 아래는 첫 번째 요소를 삭제하는 코드입니다.

deque1.erase( deque1.begin() );

지정한 반복자 구간 안의 원소를 삭제합니다. 아래는 deque1의 첫 번째 요소에서 마지막까지 모두 삭제합니다.

deque1.erase( deque1.begin(), deque1.end() );

아래는 insert와 erase 사용 예입니다. 

[리스트 2] Insert와 erase

#include 
#include 

using namespace std;


int main()
{
	Packet Pkt1;
	Pkt1.Index = 1;		Pkt1.BodySize = 10;

	Packet Pkt2;
	Pkt2.Index = 2;		Pkt2.BodySize = 12;

	Packet Pkt3;
	Pkt3.Index = 3;		Pkt3.BodySize = 14;

	Packet Pkt4;
	Pkt4.Index = 4;		Pkt4.BodySize = 16;

	deque< Packet > ReceivePackets;
	ReceivePackets.push_back( Pkt1 );
	ReceivePackets.push_back( Pkt2 );
	ReceivePackets.push_back( Pkt3 );

	cout << "< insert >" << endl;

	// 첫 번째 위치에 Pkt3을 삽입
	cout << "insert 1" << endl;
	ReceivePackets.insert( ReceivePackets.begin(), Pkt3 );

	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	// 두 번째 위치에 Pkt4를 2개 삽입
	cout << endl << "insert 2" << endl;
	ReceivePackets.insert( ++ReceivePackets.begin(), 2, Pkt4 );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}


	deque< Packet > ReceivePackets2;
	ReceivePackets2.push_back( Pkt3 );
	ReceivePackets2.push_back( Pkt4 );
	ReceivePackets2.push_back( Pkt1 );

	// ReceivePackets2의 모든 것을 ReceivePackets의 첫 번째 위치에 삽입
	cout << endl << "insert 3" << endl;
	ReceivePackets.insert( ReceivePackets.begin(), ReceivePackets2.begin(), 
                                  ReceivePackets2.end() );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}


	cout << endl << "< erase >" << endl;	
	// 두 번째 원소를 삭제한다.
	cout << "erase 1" << endl;
	ReceivePackets.erase( ++ReceivePackets.begin() );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	// 두 번째 이후부터 모두 삭제한다.
	cout << endl << "erase 2" << endl;
	ReceivePackets.erase( ++ReceivePackets.begin(), ReceivePackets.end() );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}
}

결과 

5.5.1.4 assign

vector의 assign과 같이 deque의 assign도 컨테이너를 특정 데이터로 채울 때 사용합니다. 특정 값이나 다른 deque의 특정 영역(반복자로 가리키는)에 있는 데이터로 채울 수 있습니다. assign을 사용하는 deque에 데이터가 있다면 이를 덮어쓰면서 채웁니다.

원형 : void assign( size_type _Count, const Type& _Val );
template void assign( InputIterator _First, InputIterator _Last );

 
[그림 8] deque의 assign 

지정 데이터를 지정 개수만큼 채웁니다. 숫자 7를 7개 채웁니다.

deque1.assign( 7, 7 );

다른 deque의 반복자로 지정한 영역으로 채웁니다.

deque1.erase( deque1.begin(), deque1.end() );

5.5.1.5 swap

deque1과 deque2가 있을 때 두 deque에 저장한 데이터를 서로 맞바꿀 때 사용합니다. swap 원형은 아래와 같습니다.

원형 : void swap( deque& _Right );
friend void swap( deque& _Left, deque& _Right )
template void swap(
       deque< Type, Allocator>& _Left, deque< Type, Allocator>& _Right );

deque A와 B를 swap하는 모습을 그림으로 나타내면 아래와 같습니다. 

 
[그림 9] deque의 swap 

아래는 deque1과 deque2를 swap하는 방법을 두 가지로 나타낸 코드입니다.

deque1.swap( deque2 );
swap(deque1, deque2 );

[리스트 3] assign, swap

#include 
#include 

using namespace std;

int main()
{
	deque< int > deque1;

	cout << "assign 1" << endl;
	deque1.assign( 7, 7 );
	for( deque< int >::iterator iterPos = deque1.begin();
		iterPos != deque1.end();
		++iterPos )
	{
		cout << "deque 1 : " << *iterPos << endl;
	}

	cout << endl << "assign 2" << endl;
	deque< int > deque2;
	deque2.assign( deque1.begin(), deque1.end() );
	for( deque< int >::iterator iterPos = deque2.begin();
		iterPos != deque2.end();
		++iterPos )
	{
		cout << "deque 2 : " << *iterPos << endl;
	}

	// swap
	deque< int > deque3;
	deque3.push_back(10);
	deque3.push_back(20);
	deque3.push_back(30);

	cout << endl << "swap" << endl;
	deque3.swap( deque1 );
	for( deque< int >::iterator iterPos = deque3.begin();
		iterPos != deque3.end();
		++iterPos )
	{
		cout << "deque 3 : " << *iterPos << endl;
	}

	for( deque< int >::iterator iterPos = deque1.begin();
		iterPos != deque1.end();
		++iterPos )
	{
		cout << "deque 1 : " << *iterPos << endl;
	}
}

결과 

 

deque에서 자주 사용하는 deque의 멤버를 중심으로 설명하였습니다. 여기에서 설명하지 않은 나머지 deque 멤버의 사용법은 여기(http://msdn.microsoft.com/en-us/library/8tk0b6f0.aspx)에서 참고해 주세요. 앞에서 여러 번 언급했듯이 deque 사용법이 이전 회의 vector와 거의 같습니다. 위 예제에서 deque를 vector로 바꾸어도 push_front를 제외하고는 문제없이 컴파일할 수 있습니다. deque와 vector는 사용법은 비슷하나 자료구조는 완전히 다릅니다. 앞과 끝에 데이터를 추가, 삭제하는 일이 대부분이라면 deque가 vector보다 좋지만, 그렇지 않다면 vector를 사용하는 쪽이 훨씬 더 좋습니다. STL 컨테이너는 사용이 어렵다기보다는 언제 어떤 STL 컨테이너를 사용해야 알맞은지 선택하기가 어렵습니다. STL 컨테이너를 올바른 장소에 사용하려면 컨테이너의 자료구조가 무엇인지 확실하게 알고 있어야 합니다. 만약 자료구조를 잘 모른다면 꼭 자료구조 공부를 STL 공부보다 먼저 해야 합니다.

5.6. 과제

1. deque를 사용하여 FIFO, LIFO 방식의 스택을 만들어 보세요. 

2. deque를 사용하여 Undo, Redo 구현해 보세요. 
간단한 예제로 deque의 원리만 익혀보는 과제입니다. Deque에 숫자를 저장하고 Undo를 하면 가장 마지막에 넣은 데이터를 빼고 Redo를 하면 뺀 데이터를 다시 넣습니다. deque를 2개 사용하면 횟수 제한이 없는 Undo, Redo를 구현할 수 있습니다.

출처 : http://www.hanb.co.kr/

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

• 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보다 성능이 좋지 않습니다. 

[표 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의 기능과 같습니다. 

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

5.5.2. 기본 사용 멤버

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

[표 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에서 설명한 것과 같으니 편안하게 잘 따라와 주세요.

출처 : http://www.hanb.co.kr/