이번 장은 트리 자료구조를 이해하시면 조금 빠르게 공부할 수 있습니다.
set과 multiset은 '연관 컨테이너'입니다. 모든 연관 컨테이너는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는 균형 2진 트리로 구현됩니다. 균형 2진 트리는 보통 레드-블랙 트리를 사용합니다. set의 특징은 유니크(unique)한 데이터(key) 셋의 균형 2진 트리로 저장합니다. multiset은 같은 데이터(key) 값을 가질 수 있는 set입니다. 그래서 set과 multiset은 데이터(key) 값을 빠르게 검색하고자 할 때 사용하면 좋은 컨테이너입니다.
set의 주요 개념을 그림으로 표현하면
set과 map은 컨테이너의 저장 데이터가 유니크합니다.
multiset의 주요 개념을 그림으로 표현하면
multiset과 multimap은 같은 값의 데이터를 컨테이너에 저장할 수 있습니다.
1, set과 multiset의 주요 특징과 함수
set은 데이터를 추가하는 push_? 류의 함수를 가지고 있지 않습니다. set뿐만 아니라 모든 연관 컨테이너는 데이터를 트리에 삽입(insert)한다는 의미에서 insert() 함수를 가지고 있습니다. 모든 연관 컨테이너에 데이터를 삽입하면 균형 2진 트리 형태로(비교 함수자를 사용하여) 크기 비교를 하여 2진 트리를 유지합니다.
또 모든 연관 컨테이너는 저장된 데이터를 빠르게 검색할 목적으로 사용되므로 검색류의 함수들을 가지고 있습니다.
데이터(key)의 저장과 출력( 랜덤으로 데이터를 저장합니다.)
#include <iostream>
#include <set>
using namespace std;
void main( )
{
set<int> s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
set<int>::iterator iter;
for( iter = s.begin(); iter != s.end() ; iter++)
cout << *iter << ' ';
cout << endl;
}
- 10 30 50 60 70 80
set은 같은 값의 데이터(key)를 저장할 수 없는 컨테이너입니다. 모든 연관 컨테이너는 '양방향 반복자'를 제공합니다. 출력 결과를 보면 inorder 방법으로 모든 컨테이너 요소를 탐색하는 것을 알 수 있습니다.
사실 연관 컨테이너에서 모든 요소를 출력하는 것은 별 의미가 없습니다. 연관 컨테이너라는 것이 데이터(key)를 저장하고 저장된 데이터(key)를 빠르게 검색할 목적으로 사용되기 때문입니다. 연관 컨테이너의 검색시간은 '로그 시간'입니다.
set은 기본 '비교 함수자'로 less<>를 사용합니다.
아래 예제는 위 예제와 같습니다.
#include <iostream>
#include <set>
using namespace std;
void main( )
{
set<int , less<int> > s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
set<int , less<int> >::iterator iter;
for( iter = s.begin(); iter != s.end() ; iter++)
cout << *iter << ' ';
cout << endl;
}
- 10 30 50 60 70 80
set의 두번째 템플릿 인자가 '비교 함수자'입니다. less<>는 operator < 연산자를 중복한 멤버 함수를 갖는 클래스 템플릿입니다. 그래서 트리의 왼쪽 자식으로 작은 데이터(key)값이 오른쪽 자식으로 큰 데이터(key) 값이 위치합니다. 함수자 less<>은 '함수자와 함수 포인터5'에 자세히 설명되어 있습니다.
함수자를 greater<> 로 바꾸면 트리의 왼쪽 자식으로 큰 데이터(key)값이 오른쪽 자식으로 작은 데이터(key) 값이 위치합니다.
greater<> 사용 예제
#include <iostream>
#include <set>
using namespace std;
void main( )
{
set<int , greater<int> > s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
set<int, greater<int> >::iterator iter;
for( iter = s.begin(); iter != s.end() ; iter++)
cout << *iter << ' ';
cout << endl;
}
- 80 70 60 50 30 10
결과는 less<>와 반대로 출력됩니다.
이제 연관 컨테이너의 주요 함수인 검색함수를 공부합니다.
find() 함수 사용 예제
#include <iostream>
#include <set>
using namespace std;
void main( )
{
set<int> s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
set<int>::iterator iter;
iter = s.find( 80 );
if( iter != s.end() )
cout << *iter << endl;
else
cout << "없음!" << endl;
iter = s.find( 100 );
if( iter != s.end() )
cout << *iter << endl;
else
cout << "없음!" << endl;
}
- 80
없음!
검색한 데이터(key)의 반복자를 반환합니다. 검색한 데이터가 없다면 끝을 표시하는 반복자를 반환합니다.
검색하는 내용에는 이 외에도 equal_range()와 lower_bound(), upper_bound()가 있습니다.
이 내용을 공부하기 위해서는 템플릿 클래스 pair<>를 알아야 합니다.
잠시 pair<> 클래스를 공부하고 가겠습니다. 아주 간단합니다.
pair<>는 하나의 쌍을 표현하기 위한 클래스입니다. STL의 쌍을 표현하는 모든 곳에서 pair<> 클래스를 사용합니다.
사용 예제입니다.
#include <iostream>
#include <string>
using namespace std;
void main( )
{
pair<int , int> p1(10,20);
cout << p1.first << ',' << p1.second << endl;
pair<int , string> p2(10, "Hello!" );
cout << p2.first << ',' << p2.second << endl;
pair<string, string> p3( "Hello!", "Hi");
cout << p3.first << ',' << p3.second << endl;
cout << p3.first.c_str() << endl;
cout << p3.first.size() << endl;
cout << p3.second.c_str() << endl;
cout << p3.second.size() << endl;
}
- 10,20
10,Hello!
Hello!,Hi
Hello!
6
Hi
2
pair<>는 공용 멤버 first와 second를 가지고 있습니다. first는 첫 번째 값을 second는 두 번째 값을 저장하는 변수입니다.
그림으로 간단하게...
다시 set 컨테이너의 검색 함수를 돌아옵니다.
equal_range() 함수는 찾은 데이터(key)의 구간 반복자를 쌍으로 반환합니다.
사실 set은 저장한 데이터(key)가 유니크하므로(예외?를 제외하고) 반복자 쌍을 사용할 필요는 없지만 multiset이나 multimap에서는 유용하게 사용됩니다. 또 모든 연관 컨테이너는 같은 종류의 멤버 함수들을 제공합니다.
equal_range()의 예제입니다.
#include <iostream>
#include <set>
using namespace std;
void main( )
{
set<int> s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
pair< set<int>::iterator, set<int>::iterator> iter_pair;
iter_pair = s.equal_range(50);
if( (iter_pair.first) == s.end() && (iter_pair.second == s.end()) )
cout << "없음!" << endl;
else
cout << *iter_pair.first << ',' << *iter_pair.second << endl; //주의
iter_pair = s.equal_range(100);
if( (iter_pair.first) == s.end() && (iter_pair.second == s.end()) )
cout << "없음!" << endl;
else
cout << *iter_pair.first << ',' << *iter_pair.second << endl; //주의
}
- 50,60
없음!
equal_range()는 찾음 데이터의 시작을 가리키는 반복자와 끝은 가리키는 반복자를 반환합니다.
여기서 주의할 점이 있습니다. set의 경우 찾은 데이터는 first 멤버가 되고 찾은 데이터 다음이 second가 됩니다. 이것은 lower_bound와 upper_bound에 해당합니다.
그림으로 보면...
그래서 만약 마지막 데이터인 80을 검색하면 그림은 아래와 같습니다.
lower_bound와 upper_bound 예제입니다.
#include <iostream>
#include <set>
using namespace std;
void main( )
{
set<int> s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
set<int>::iterator iter_lower;
iter_lower = s.lower_bound(50);
if( iter_lower == s.end() )
cout << "없음!" << endl;
else
cout <<"lower: " << *iter_lower<< endl;
set<int>::iterator iter_upper;
iter_upper = s.upper_bound(50);
if( iter_upper == s.end() )
cout << "없음!" << endl;
else
cout <<"upper: " << *iter_upper<< endl; //주의
}
- lower: 50
upper: 60
lower_bound()와 upper_bound() 함수 모두 찾은 데이터(key) 위치의 반복자를 반환합니다.
여기서 주의할 점은 lower_bound()은 찾은 데이터 위치의 반복자지만 upper_bound()은 찾은 데이터 위치의 다음 요소를 가리키는 반복자입니다.
그림으로 보면...
지금까지 배운 내용은 모두 multiset에도 적용됩니다.
multiset이 set과 다른 점은 같은 값의 데이터(key)를 저장할 수 있다는 것입니다.
간단한 multiset의 출력입니다.
#include <iostream>
#include <set>
using namespace std;
void main( )
{
multiset<int> s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 80 );
s.insert( 80 );
s.insert( 30 );
s.insert( 50 );
s.insert( 70 );
s.insert( 60 );
multiset<int>::iterator iter;
for( iter = s.begin(); iter != s.end() ; iter++)
cout << *iter << ' ';
cout << endl;
}
- 10 30 50 50 60 70 80 80 80
50과 80 데이터가 중복으로 저장됩니다.
여기서 주요 함수가 equal_range()입니다.
#include <iostream>
#include <set>
using namespace std;
void main( )
{
multiset<int> s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 80 );
s.insert( 80 );
s.insert( 30 );
s.insert( 50 );
s.insert( 70 );
s.insert( 60 );
multiset<int>::iterator iter;
for( iter = s.begin(); iter != s.end() ; iter++)
cout << *iter << ' ';
cout << endl;
pair<multiset<int>::iterator, multiset<int>::iterator > iter_pair;
iter_pair = s.equal_range( 80 );
for( iter = iter_pair.first ; iter != iter_pair.second ; iter++)
cout << *iter << ' ';
cout << endl;
}
- 10 30 50 50 60 70 80 80 80
80 80 80
equal_range() 함수를 사용하면 찾은 데이터의 구간 반복자 쌍을 얻을 수 있습니다.
설명은 그림으로...
2, typedef 내장 자료형
모든 컨테이너 클래스에는 typedef되어 있는 자료형들을 제공합니다. 이 자료형중 연관 컨테이너처럼 '비교 함수자'를 가지는 컨테이너는 key_comp()라는 함수를 제공합니다.
key_comp()함수를 사용하면 우리가 2진 트리를 정렬하기 위해 지정했던 함수자(기본 함수자 less<>) 객체를 리턴합니다.
key_comp()함수 예제
#include <iostream>
#include <set>
using namespace std;
void main( )
{
multiset<int> s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
less<int> key_less = s.key_comp();
if( key_less( 10, 20 ) )
cout << "true" << endl;
else
cout << "false" << endl;
if( s.key_comp()( 10, 20) )
cout << "true" << endl;
else
cout << "false" << endl;
}
- true
true
key_comp()함수가 less<> 객체를 리턴하므로 함수를 사용하여 지정했던 함수자 객체를 반환받거나 임의의 데이터를 비교할 수 있습니다.
greater<>를지정한 key_comp()함수 예제
#include <iostream>
#include <set>
using namespace std;
void main( )
{
multiset<int, greater<int> > s;
s.insert( 50 );
s.insert( 10 );
s.insert( 80 );
s.insert( 30 );
s.insert( 70 );
s.insert( 60 );
greater<int> key_greater = s.key_comp();
if( key_greater( 10, 20 ) )
cout << "true" << endl;
else
cout << "false" << endl;
if( s.key_comp()( 10, 20) )
cout << "true" << endl;
else
cout << "false" << endl;
}
- false
false
greater<>를 사용하므로 결과는 false 입니다.
출처 : http://blog.daum.net/coolprogramming/76
