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

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

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

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

( AVL 트리 : 자식노드와의 높이차이가 1보다 크지 않은 것으로 그 균형을 맞추기 위해 회전한다. )

연관 컨테이너는 데이터를 push한다는 의미보단  트리에 insert한다는 의미로 push함수 대신 insert함수를 가지고 있다. 

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

그리고 양방향 반복자를 사용한다. 검색시간은 log시간이다.

1. set

각 노드마다 다른 key가 있는 컨테이너이다.

2. multiset

노드에 중복된 key가 있을 수 있다.

3. map

각 노드마다 다른 key와 value가 있다.

( value는 중복 될 수 있다. )

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

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

map은 연관컨테이너에서 유일하게 []연산자 중복을 제공한다.

[]연산자의 인덱스는 key이며 인덱스가 가리키는 메모리 값은 value이다.

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

4. multimap

노드에 중복된 key가 있을 수 있고, 각각의 key값에 짝에 value가 있다.