[STL] 연관 컨테이너 ( set,multiset,map,multimap )

연관 컨테이너

정렬 연관 컨테이너란, 컨테이너 내의 자료들이 규칙에 따라 연관, 정렬 되어있는 컨테이너이다.

일정한 규칙으로 정렬되어있기 때문에 검색속도가 빠른 것이 장점이다.

모든 연관 컨테이너는 균형 2진 트리로 레드 블랙 트리이다.

레드 블랙 트리란, AVL 트리로 삽입, 삭제 검색에서 최악의 경우에도 일정한 실행시간을 보장하는 것이다.

연관 컨테이너는 데이터를 Push한다는 의미보다는 트리에 Insert 한다는 의미로 Push함수 대신 Insert 함수를 가지고 있다. 그리고 AVL 트리 이므로 삽입 후 균형을 맞춘다.

연관 컨테이너는 저장된 데이터를 빠르게 검색할 목적으로 사용되므로 주로 검색을 하는 함수를 가지고 있고, 검색 시간은 log시간이다.

양방향 반복자를 사용한다.

Set

Set과 multiset은 연관컨테이너이자, 노드 기반 컨테이너이다.

Set은 각 노드마다 다른 Key가 있는 것이고, multiset은 중복 Key를 허용하는 컨테이너이다.

Set은 기본 함수자로 less<int>를 사용한다. 이는 트리의 왼쪽자식은 작은 데이터 Key가 오른쪽 자식은 큰 데이터 Key가 위치하게 하는 함수자이다. greater<int>는 반대이다.

void main(void) { 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; }

연관 컨테이너는 주로 find 라는 함수를 사용하며, 자료가 없을 수도 있으므로 else라고 써준다.

검색 함수 이외에도 다른 것이 있다.

우선 pair<>라는 클래스 템플릿이 있는데, 이는 하나의 쌍을 표현하기 위한 클래스이다.

pair<int, string> p2(10,”Hello!”); cout << p2.first << “,”<<p2.second << endl;

equal_range()는 찾은 key의 구간 반복자를 쌍으로 반환하는 함수이다. 

만약 50을 찾는다면 50의 위치를 first로 그 다음위치를 second로 반환한다는 의미이다.

여기서 first는 lower_bound()가 되고, second는 upper_bound()가 된다. lower_bound() 함수로 50을 찾는다면, 찾은 key위치의 반복자를 반환하지만, upper_bound() 함수는 찾은 key위치의 다음 요소를 가리키는 반복자를 반환한다.

multiset에서 equal_range()가 효과를 발휘한다.

multiset은 중복이 가능하므로 만약 중복된 key를 찾는다면 lower_bound()와 upper_bound()를 효과적으로 사용할 수 있게 된다.

key_comp() 함수는 자료형 중에서 연관 컨테이너처럼 비교함수자를 가지는 컨테이너로, 이를 사용하면 2진 트리를 정렬하기 위해 지정했던 함수자(기본함수자less<>)객체를 리턴한다.

key_comp()함수가 less<> 객체를 리턴하므로 함수를 사용하여 지정했던 함수자 객체를 반환받거나 임의의 데이터를 비교할 수 있다.

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; }

map

map은 Key와 Value의 쌍으로 구성된 데이터 셋의 집합이다. 여기서도 Key값은 유일하고, multimap은 key값이 중복될 수 있다.

map<int, int> m; m[5] = 100; cout << m[5] << endl;

이렇게 하면 100이 출력된다.

map은 연관컨테이너에서 유일하게 []연산자 중복을 제공한다. []연산자의 인덱스는 key이며 인덱스가 가리키는 메모리 값은 value이다.

여기서 5라는 key가 없다면 노드가 추가되며, key가 있다면 갱신이 된다.

map은 key와 value를 pair<> 객체로 저장한다.

multimap은 []연산자가 없으며 key값이 중복될 수 있다.

[ 컨테이너 및 STL 정리 PPT ]  

120730_STL 기초.pptx