STL - 결합 컨테이너

▣ 결합 컨테이너 (Associative Container) 혹은 연관 컨테이너

→ 시퀀스 컨테이너와는 다른 기본 컨테이너의 발전형태
이것은 컨테이너의 값에 키(Key)라는 값을 결합하고 그 키 값을 이용하여 값 데이터를 찾을 수 있다.
결합 컨테이너도 시퀀스와 마찬가지로 원소 삽입이 가능하지만 여기서는 특정 위치에 대한 삽입이 허용되지 않는다. 그 이유는 정보 검색을 빠르게 하기 위해 결합 컨테이너에서 특별한 알고리즘을 사용하기 때문이다.

→ 결합 컨테이너는 set, multiset, map, multimap 이렇게 4개의 컨테이너를 가지고 있다. set과 multiset은 <set>헤더에 정의되어 있고, map과 multimap은 <map>헤더에 정의되어 있다.


★ set 컨테이너

→ set은 결합 컨테이너 중에서 가장 단순한 형태로 여기서의 값의 데이터 타입은 키의 데이터타입과 같다.
set의 경우 키는 고유하다. 즉, 키가 한개만 있어야 한다는 뜻이기도 하다.
set은 마치 이전 수학 시간때의 집합을 떠올리게 하는 컨테이너다. 그렇다 보니 다수의 집합 관련 연산들을 가지고 있다.

→ 선언은 이와 같다.

set<string> A;

→ 템플릿 전달인자는 보통 1개이며, 상황에 따라서는 2개를 쓸 수도 있다.

set< string, less<string> > A;

→ 인수1 : 값의 데이터 타입이자 키의 데이터 타입이 된다.
인수2 : 키를 배치하는 데 쓰이는 비교 함수 객체. 디폴트는 less<>이며 이것은 작은 것이 컨테이너의 앞쪽에 배치된다는 것이다.

→ 생성자도 여러개가 있지만 그중 하나는 이렇다.

string s1[6] = { "buffon, "thinkers", "for", "heavy", "can", "for" };
set<string> A( s1, s1 + 6 );

→ 이렇게 이터레이터 혹은 포인터로 [인수1, 인수2) 의 범위로 컨테이너를 초기화 시킬 수 있다.
위의 경우 "for"라는 문자열이 두 개가 컨테이너로 들어갔는데 set에서는 동일한 데이터가 두 개 이상 들어가는 것을 허용하지 않으므로(키는 고유하다.) 두개의 "for"중 하나가 없어진다.
위의 A를 출력하면 "for"가 한개만 출력된다는 것을 알 수 있다.

ostream_iterator<string, char> out_iter( cout, " " );
copy( A.begin(), A.end(), out_iter );
// buffon can for heavy thinkers 이렇게 출력됨. for가 하나만 출력된다.

→ set에서도 물론 삽입 메서드가 들어가야 하는데 그것이 바로 insert() 이다. 시퀀스 컨테이너의 push_back() 등과 비슷한 인수 형태를 가지는데 인수는 키 타입의 원소가 들어가야 한다. 단, set에서는 알고리즘에 따라서 넣게 된 인수값이 자동 정렬되어진다는 것을 잊어서는 안된다. 또한 set에서는 컨테이너 내의 같은 키 값이 있으면 삽입이 이루어 지지 않고 실패 값을 리턴한다.

A.insert( "FromPt" );

→ STL에서는 set등의 결합 컨테이너에 대한 다수의 알고리즘들을 제공한다.

set_union() 함수는 두 컨테이너에 대해서 합집합을 산출해 낼 수 있다.
인수는 총 5개가 들어간다.

인수 1, 2 : 제 1집합의 범위. [인수1, 인수2) 의 범위이다.
인수 3, 4 : 제 2집합의 범위. [인수3, 인수4) 의 범위이다.
인수 5 : 두 집합의 합집합된 결과가 인수 5의 이터레이터 지점으로 복사된다.

이 인수 5의 형태는 copy()의 인수3의 형태와 비슷하다. 즉, insert_iterator를 쓰지 않는다면 기존 데이터를 덮어 씌울수도 있으며 공간을 따로 할당받지 않았다면 메모리 할당구역을 침범할 수도 있다.

→ set_intersection() 함수는 set_union() 과 인수의 형태가 똑같으며, 이 함수는 집합 2개의 교집합을 산출해 낸다.

→ set_difference() 함수 또한 위의 함수들과 동일하게 인수가 5개이며, 이 함수는 제 1집합(인수1~2) 에서 제 2집합(인수3~4)을 뺀 차집합을 인수 5에 복사한다.

→ 그리고 set에서는 멤버함수로 lower_bound()와 upper_bound() 메서드를 제공한다.
두 함수는 인수가 한개씩 들어가는데 그것은 컨테이너 원소 데이터 타입의 값이 된다.

lower_bound()는 인수의 값을 컨테이너와 비교하여 인수보다 큰 데이터들 중 가장 작은 원소의 이터레이터를 리턴한다. 결국 lower라는 말이 인수가 더 작다는 뜻이 되버린다.
upper_bound()는 반대로 인수보다 작은 데이터들 중 가장 큰 원소의 이터레이터를 리턴한다. 즉 찾고자 하는 이터레이터 원소보다 인수의 값이 한 수 더 큰 값이 된다.

→ multiset과 set의 차이점을 설명하자면, 키가 하나만 존재해야 하는 set과는 달리 multiset은 키들이 동일한 값으로 중복되어 들어갈 수가 있다. 그렇기 때문에 insert()에서 인수 타입이 완전히 틀린게 아니라면 삽입이 실패할 일이 없다.
이점을 제외하면 두 컨테이너는 서로 비슷하다.


★ multimap, map

→ map, multimap의 특징은 키 데이터형과 값 데이터 형이 따로 분리되져 있다는 것이다.

→ map과 multimap의 대략적인 이해를 위해서는 pair 라는 템플릿 클래스에 대해서 알아야 한다.
pair 는 두 종류의 값을 하나의 객체에 저장하기 위한 클래스로 이것을 통해 두 타입의 값을 한꺼번에 사용할 수 있다. 사실상 넣을 수 있는 템플릿 전달인수는 프로그래머 마음이다.

pair< int, float > intnfloat( 4, 4.0f );
// 이와 같이 선언하여 쓸 수 있다.

→ pair에서 멤버 변수 first는 첫번째 요소를 나타내고 있고 (위에서는 정수 4 ), second는 두번째 요소를 가리키고 있다.(위에서는 실수 4.0f )

→ map이나 multimap에서는 템플릿 데이터 타입 전달인자가 두개가 딱 맞는 pair 템플릿 객체를 insert 메서드의 인수로 넣게 된다.
map, multimap 의 선언은 이와 같다.

multimap< int, string > codes;

→ 일반적으로 위와 같이 두개의 템플릿 전달인자가 들어가는데 템플릿 전달인수 3이 추가로 들어갈 수가 있다. 인수3은 set에서의 템플릿 전달인수2와 비슷하게 키 데이터형에 대한 비교함수 객체를 넣는다. 디폴트는 less<>다.

인수1 : 키 데이터 타입. map에서는 이것을 넣을때 값들이 유일해야 하지만, multimap에서는 키 데이터가 중복이 가능하다.
인수2 : 값 데이터 타입. 키 데이터와 매치되는 값 데이터가 들어갈 수 있다.

→ map, multimap에서의 삽입도 insert() 메서드를 통해 이루어지는데 넣는 인수가 컨테이너와 데이터형 매개변수가 일치하는 pair 객체이어야 한다.

pair< int, string > item( 0, "FromPt" );
// 위의 컨테이너 codes와 템플릿 전달인수가 같다.
codes.insert( item );

→ set도 그렇지만 map의 경우 인수의 키 데이터가 컨테이너에 같은 것이 있으면 그것이 설사 값 데이터 부분이 다르다고 하더라도 삽입이 이루어 지지 않고 실패했다는 내용을 pair< iterator, bool > 타입으로 리턴한다. 여기서 iterator란 성공시에 들어가는 위치를 뜻한다. 만약 multimap에서의 삽입이라면 키 중복이 허용되므로 iterator만 리턴한다.

→ map과 multimap에서는 set과 동일한 기능을 하는 lower_bound()와 upper_bound() 메서드가 있고 cound()라는 메서드도 있다. 이것은 multimap에서 사용되는 메서드로 키 값을 인수로 넣어서 그것과 매치되는 원소의 갯수를 리턴한다. ( map에서도 쓸수는 있지만 키를 유일하게 하나만 사용하므로 1만 리턴하게 될테니 그닥 쓸 일이 없을 것 같다. )

→ 또한 map과 multimap에서는 equal_range() 라는 메서드가 있다.
이것은 키 값을 인수로 받아서 이 키와 동일한 원소들의 이터레이터로 이루어진 pair 객체를 리턴값으로 받는다.
예를 들어 위의 codes에서 (codes 컨테이너가 어느정도 채워져 있다고 가정하고..) 키 값이 718인 원소들의 데이터들에 접근하고자 할때,

pair< multimap<int, string>::iterator, multimap<int, string>::iterator > range = codes.equal_range( 718 );
// 다소 복잡해 보이지만 이렇게 할 수 밖에 없다. typedef 를 통해 코드를 보다 깔끔하게 보일 수도 있다.

→ 이와 같이 multimap<int, string> 타입에 대한 이터레이터 두개를 템플릿 전달인자로 쓰는 pair 객체 range를 선언하여 리턴값을 받는다.
여기서 얻는 리턴값 pair 의 첫번째 요소는 컨테이너에서 키 값이 동일한 요소중 첫번째 것의 이터레이터이고, 두번째 요소는 컨테이너에서 키 값이 동일한 요소 중 마지막 것의 다음요소(past-the-end)의 이터레이터가 된다.
→ 키값이 동일한 원소들이라면 그것들은 순서가 붙어있다는 것을 알아두어야 한다.
map 같은 경우 어차피 키 값이 일치하는 요소가 하나라 리턴값은 1개 요소에 대한 것 뿐이다. 그러므로 range의 첫번째 요소만 확인하면 될 것이다.
그러나 multimap의 경우 키 값이 일치하는 원소들이 두개 이상이 될 수도 있다. range는 이 요소들 중에서 처음부터 past-the-end 지점까지의 이터레이터를 리턴함으로써 전부 확인해 볼 수 있게 한 것이다.

multimap<int, string>::iterator it;
for( it = range.first; it != range.second; ++it )
cout << (*it).second << endl;

→ 위의 코드와 같이 키 값이 718인 원소들에 모든 값 데이터를 출력할 수가 있는 것이다.
→ 여기서 설명 하지 않은 부분이 있는데, 바로 map, multimap의 이터레이터의 *연산자이다.
insert()로 컨테이너에 삽입할 때에 함수의 인수로 map, multimap의 데이터형 인수와 동일한 pair 객체를 넣었듯이 이터레이터의 * 연산자는 이터레이터가 가리키는 원소를 pair 객체로 보여주게 된다.