시퀀스 컨테이너와 달리 모든 연관 컨테이너(set, multiset, map, multimap)는 같은 인터페이스(생성자, 멤버 함수, 연산자)를 제공하므로 이 절에서만 표로 정리하며 다른 컨테이너 설명에서는 템플릿 형식만을 정리합니다.
set의 기본 구조 입니다. set 은 컨테이너에 원소를 저장하는 유일한 멤버 함수 insert() 를 제공합니다. 연관 컨테이너는 정렬 기준이 있으므로 insert()에 의해 삽입된 원소는 자동 정렬됩니다. set에서 원소 (10, 30, 40, 50, 70, 80, 90) 를 key라 하며 이 키를 비교하여 내부 원소를 정렬합니다. set은 그림처럼 모든 원소가 유일합니다. 원소의 중복을 허용해야 한다면 multiset을 사용해야 합니다.
연관 컨테이너는 특정 정렬 기준(조건자)에 따라 원소를 자동 정렬하는 컨테이너입니다. 이때 정렬 기준은 템플릿 매개변수에 지정할 수 있으며, 기본 정렬 기준은 less 조건자 입니다. 그렇다 보니 시퀀스 컨테이너가 제공하는 순서와 관련된 함수류인 push_back(), push_front() 등등의 함수들을 제공하지 않습니다.
연관 컨테이너는 균형 이진 트리를 사용하므로 찾기 연산 (find(), lower_bound() upper_bound(), equal_range(), count())에 뛰어난 성능을 보이며 insert() 멤버 함수를 이용한 삽입도 로그 시간 복잡도를 보입니다.
s.insert(50);
s.insert(50); // 실패
set<int>:::iterator iter;
for(...)
//inorder 이진 트리 탐색 순서로 출력
pr = s.insert(50): 50을 s에 삽입하고 결과를 pr에 저장합니다. pr.first는 50우너소를 가리키는 반복자이며 pr.second는 삽입 성공, 삽입 실패 결과입니다.
pr.second가 성공이면 pr.first는 삽입한 원소(50)를 가리키는 반복자이며, pr.second가 false 이면 pr.first는 이미 삽입된 원소를 가리키는 반복자 입니다.
연관 컨테이너는 시퀀스 컨테이너처럼 삽입할 위치를 지정하는 버전과 삽입할 구간을 지정하는 버전의 insert() 도 제공합니다. 단, 원소의 삽입 위치를 지정하는 버전은 삽입 탐색을 시작할 위치로 삽입 위치가 정렬 순서와 맞는다면 바로 삽입되지만 아니면 로그 시간이 걸립니다.
pr = s.insert(90);
s.insert(pr.first, 85);
//pr.first가 가리키는 위치부터 탐색을 시작하여 85를 삽입합니다.
set<int, greater<int>>::iterator iter;
// greater<int> 조건자를 사용하는 반복자 생성
set은 사용중인 정렬 기준 조건자를 반환하는 멤버 함수 key_comp()와 value_comp()를 제공합니다. 이때 정렬 기준 형식은 typedef 내장 멤버 형식 key_compare와 value_compare로 제공합니다. set은 저장 원소인 값(value)이 곧 비교로 사용되는 키(key)가 되며 그래서 set은 value와 key 타입이 같습니다.
set<int, less<int>>::key_compare l_cmp = s_less.key_comp();
set<int, greater<int>>::key_compare g_cmp = s_greater.key_comp();
typeid(s_less.value_comp()).name() << endl;
set은 원소가 key이므로 key_compare와 value_compare 두 타입이 같습니다. 필요하다면 사용자가 직접 조건자를 만들어 set의 정렬 기준으로 사용할 수 있습니다.
연관 컨테이너는 모두 같은 인터페이스의 멤버 함수를 제공합니다. 이 연관 컨테이너의 핵심 인터페이스는 찾기 관련 멤버 함수입니다. 찾기 관련 멤버 함수는 정렬 기준으로 트리의 루트 노드부터 자식 노드로 검색을 진행하므로 로그 시간 복잡도에 실행되며 count(), fidn(), lower_bound(), upper_bound(), equal_range() 멤버 함수입니다.