기초 : C++ STL 프로그래밍(8)-셋(Set)

http://www.hanb.co.kr/network/view.html?bi_id=1624

제공 : 한빛 네트워크
저자 : 최흥배

앞서 설명했던 map과 비슷하면서도 다른 set을 이번에 이야기 하려고 합니다. map 이전에는 hash_map을 설명했는데 이번에 이야기할 set과 여러 부분에서 중복되는 부분이 있고, 저는 현업에서 set을 사용하는 경우가 거의 없어서 이번에는 내용이 길지 않을 것 같습니다. 

8.1 set 이란 

set은 원하는 key를 신속하게 찾고, 또 이 key가 정렬되기를 원할 때 사용합니다.(여기서 말하는 key라는 것은 저장할 자료를 말합니다). map과 비슷하지만 다른 점은 map은 key와 값이 한 쌍으로 저장하지만 set은 key만 저장합니다. set도 map과 같이 key를 중복으로 저장할 수 없습니다. 만약 key를 중복으로 사용하고 싶다면 multiset을 사용해야 합니다. 사용방법은 set과 거의 같습니다. set은 map과 같이 이진 탐색 트리 자료구조를 사용합니다. 

8.2 set을 사용할 때 

앞서 이야기 했듯이 set은 자료를 저장할 때 내부에서 자동으로 정렬하고, map과 다르게 key만 저장합니다. 

set은 아래 조건일 때 사용하면 좋습니다.

1. 정렬해야 한다.
2. key가 있는지 없는지 알아야 할 때
3. 많은 자료를 저장하고, 검색 속도가 빨라야 할 때

다른 컨테이너를 설명 할 때 꽤 많은 이야기를 했는데 그동안 했던 이야기와 중복되는 것이 많고 특히 앞의 map과 비슷한 부분이 많아서 이번에는 바로 사용 방법으로 들어가겠습니다. 

8.3 set 사용 방법 

set 컨테이너를 쓰려면 먼저 헤더 파일을 포함해야 합니다.

#include <set>

보통 set을 사용하는 방법은 아래와 같습니다.

set< key 자료 type > 변수 이름

set< int > set1;

map과 사용 방법이 비슷하죠? 다만, set은 위와 같이 key만 저장합니다. 위에서는 key로 int 타입을 사용했습니다. 

set은 map과 같이 기본적으로 오름차순으로 정렬을 합니다. 만약 이것을 내림 차순으로 바꾸고 싶거나 key 자료형이 기본형이 아니란 유저 정의형이라면 함수 객체로 정렬 방법을 제공해야 합니다. 

set의 key가 기본형이고 내림 차순으로 정렬하고 싶다면 STL의 greater 알고리즘을 사용하면 됩니다.

set< key 자료 type, 비교 함수 > 변수 이름

set< int, greater<int> > set1;

만약 key가 기본형이 아니고 Player 이라는 클래스를 사용하고 Player의 멤버 중 HP를 비교하여 정렬하고 싶다면 아래와 같이 하면 됩니다.

class Player
{
public:
   Player() {}
   ~Player() {}

   int m_HP;
};

template< typename T >
struct HP_COMPARE : public binary_function< T, T, bool >
{
   bool operator() (T& player1, T& player2) const 
   { 
      return player1.m_HP > player2.m_HP;
   }
};

int main()
{
   set< Player, HP_COMPARE<Player> > set1;
   return 0;
}

8.3.1 set의 주요 멤버들 

멤버	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환
clear	저장하고 있는 모든 원소를 삭제
empty	저장 하고 있는 요소가 없으면 true 반환
end	마지막 원소 다음의(미 사용 영역) 반복자를 반환
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제
find	key와 연관된 원소의 반복자 반환
insert	원소 추가
lower_bound	지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환
operator[]	지정한 key 값으로 원소 추가 및 접근
rbegin	역방향으로 첫 번째 원소의 반복자를 반환
rend	역방향으로 마지막 원소 다음의 반복자를 반환
size	원소의 개수를 반환
upper_bound	지정한 key 요소를 가지고 있다면 해당 위치 다음 위치의 반복자 반환

[표 1]. map의 주요 멤버들 

8.3.2. 추가 

set 에서는 자료를 추가 할 때 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 );

첫 번째가 자주 사용하는 방식입니다.

set< int > set1;

// key 1을 추가.
set1.insert( 1 );

// 추가했는지 조사 하고 싶을 때는
pair< set<int>::iterator, bool > Result;
Result = set1.insert( 1 );
if( Result.second )
{
   // 추가 성공
}
else
{
  // 추가 실패
}

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

// 첫 번째 위치에 key 1, value 35를 추가
set1.insert( set1.begin(), 10 );

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

set< int > set2;
// set1의 모든 요소를 set2에 추가.
set2.insert( set1.begin(), set1.end() );

set은 이미 있는 key 값을 추가할 수 없습니다(복수의 key 값을 사용하기 위해서는 multiset을 사용해야 합니다). 

참고로 특정 위치를 지정하여 추가를 하여도 정렬되어 저장합니다. 

<리스트 1. 특정 위치에 추가했을 때의 정렬 여부>

#include <iostream>
#include <functional>
#include <set>

using namespace std;

int main()
{
   set< int > set1;
   set1.insert( 10 );
   set1.insert( 15 );
   set1.insert( 12 );
   set1.insert( 2 );
   set1.insert( 100 );

   for( set<int>::iterator IterPos = set1.begin();
      IterPos != set1.end(); ++IterPos )
   {
      cout << *IterPos << endl;
   }

   set<int>::iterator IterPos = set1.begin();
   ++IterPos;
   set1.insert( IterPos, 90 );
   
   cout << endl;
   cout << "90을추가후set1의모든요소출력" << endl;
   for( set<int>::iterator IterPos = set1.begin();
      IterPos != set1.end(); ++IterPos )
   {
      cout << *IterPos << endl;
   }
   
   return 0;
}

<결과> 

 

8.3.3. 반복자 사용 

다른 컨테이너와 같이 정 방향 반복자 begin(), end()와 역 방향 반복자 rbegin(), rend()를 지원합니다. 사용 방법은 다음과 같습니다.

// 정 방향으로 set1의 모든 Key 출력
set< int >::iterator Iter_Pos;
for( Iter_Pos = set1.begin(); Iter_Pos != set1.end(); ++Iter_Pos)
{
   cout << *Iter_Pos << endl;
}

// 역 방향으로 set1의 모든 요소 Key 출력
set< int >::reverse_iterator Iter_rPos;
for( Iter_rPos = set1.rbegin(); Iter_rPos != set1.rend(); ++Iter_rPos)
{
   cout << *Iter_rPos << endl;
}

8.3.4. 검색 

set에서 검색은 key를 대상으로 합니다.
key와 같은 요소를 찾으면 그 요소의 반복자를 반환하고, 찾지 못한 경우에는 end()를 가리키는 반복자를 반환합니다.

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

두 방식의 차이는 반환된 반복자가 const 여부입니다. 첫 번째 방식은 const가 아니므로 찾은 요소의 Key를 변경할 수 있습니다. 그러나 두 번째 방식은 Key를 변경할 수 없습니다.

// key가 10인 요소 찾기.
set< int >::Iterator FindIter = set1.find( 10 );

// 찾았다면 value를 1000으로 변경
if( FindIter != set1.end() )
{
   // Key를 찾았다!!!
}

set은 map과 다르게 Key만 저장하기에 Key의 변경이 가능하지만 find로 찾은 Key를 변경하면 정렬되지 않습니다. 

<리스트 2. find로 찾은 Key 변경>

int main()
{
   set< int > set1;
   set1.insert( 10 );
   set1.insert( 15 );
   set1.insert( 12 );

   for( set<int>::iterator IterPos = set1.begin();
      IterPos != set1.end(); ++IterPos )
   {
      cout << *IterPos << endl;
   }

   set<int>::iterator FindIter = set1.find( 15 );
   if( FindIter != set1.end() )
   {
      *FindIter = 11;
   }

   cout << endl;
   cout << "15를 검색 후11로 변경한 후 set1의 모든 요소 출력" << endl;
   for( set<int>::iterator IterPos = set1.begin();
      IterPos != set1.end(); ++IterPos )
   {
      cout << *IterPos << endl;
   }

   return 0;
}

<결과> 

 

8.3.5. 삭제 

저장하고 있는 요소를 삭제할 때는 erase와 clear를 사용합니다.
erase는 특정 요소를 삭제할 때 사용하고, clear는 모든 요소를 삭제할 때 사용합니다. 

erase

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

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

// 두 번째 위치의 요소 삭제.
set1.erase( ++set1.begin() );

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

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

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

// key가 10인 요소 삭제.
set1.erase( 10 );

첫 번째와 두 번째 방식으로 삭제를 하면 삭제되는 요소의 다음을 가리키는 반복자를 반환합니다.
세 번째 방식은 삭제된 개수를 반환하는데 정말 삭제가 되었다면 1이 반환됩니다. 그러나 multiset에서는 1이 아닌 삭제된 개수를 반환합니다. 

clear 

set의 모든 요소를 삭제할 때는 clear를 사용합니다.

set1.clear();

이것으로 set에서 자주 사용하는 멤버들에 대한 설명은 끝났습니다. 
아래의 <리스트 3>은 set을 전반적으로 사용하는 예를 나타내고 있습니다. 

<리스트 3. set 사용 예>

#include <iostream>
#include <functional>
#include <set>

using namespace std;

class Player
{
public:
   Player() {}
   ~Player() {}

   int m_Level;
};

// 레벨이 높은 순으로 정렬
template< typename T > 
struct LEVEL_COMPARE : public binary_function< T, T, bool >
{
   bool operator() (const T& player1, const T& player2) const 
   { 
      return player1->m_Level > player2->m_Level;
   }
};

int main()
{
   set< Player*, LEVEL_COMPARE<Player*> > PlayerList;

   Player* pPlayer1 = new Player; pPlayer1->m_Level = 10;
   PlayerList.insert( pPlayer1 );
   Player* pPlayer2 = new Player; pPlayer2->m_Level = 45;
   PlayerList.insert( pPlayer2 );
   Player* pPlayer3 = new Player; pPlayer3->m_Level = 5;
   PlayerList.insert( pPlayer3 );
   Player* pPlayer4 = new Player; pPlayer4->m_Level = 15;
   PlayerList.insert( pPlayer4 );

   // 정 방향으로 출력( 레벨이 높은 순으로)
   for( set< Player*, LEVEL_COMPARE<Player*> >::iterator IterPos = PlayerList.begin();
      IterPos != PlayerList.end(); ++IterPos )
   {
      cout << (*IterPos)->m_Level << endl;
   }

   cout << endl;

   // 역 방향으로 출력( 레벨이 낮은 순으로)
   for( set< Player*, LEVEL_COMPARE<Player*> >::reverse_iterator IterPos = PlayerList.rbegin();
      IterPos != PlayerList.rend(); ++IterPos )
   {
      cout << (*IterPos)->m_Level << endl;
   }

   cout << endl;

   // pPlayer4를검색
   set< Player*, LEVEL_COMPARE<Player*> >::iterator FindPlayer = PlayerList.find( pPlayer4 );
   if( FindPlayer != PlayerList.end() )
   {
      cout << "pPlayer4를 찾았습니다" << endl;

      cout << "pPlayer4 삭제" << endl;
      PlayerList.erase( FindPlayer );
   }
   else
   {
      cout << "pPlayer4를 못찾았습니다" << endl;
   }

   cout << endl;
   cout << "Total Player Count : " << PlayerList.size() << endl;

   cout << endl;
   PlayerList.clear();
   if( PlayerList.empty() )
   {
      cout << "Player가 없습니다." << endl;
   }
   
   delete pPlayer1;
   delete pPlayer2;
   delete pPlayer3;
   delete pPlayer4;
   return 0;
}

<결과> 

 

이전 회의 map과 거의 대부분 비슷하기 때문에 map을 아시는 분들은 아주 쉬웠을 것이라고 생각합니다. 

이전과 같이 set의 멤버 중 설명하지 않은 것들은 MSDN에 있는 set 설명을 참조하시기를 바랍니다. 

과제 

Sset은 Key를 중복으로 저장할 수 없습니다. 중복 Key를 저장하기 위해서는 multiset을 사용해야 합니다. multiset을 공부해 보세요 

참고 url : http://msdn.microsoft.com/ko-kr/library/w5txk7zc.aspx