연관 컨테이너
연관 컨테이너(associate container)
연관 컨테이너(associate container)는 키(key)와 값(value)처럼 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너입니다.
키와 값을 이용한 연관 컨테이너는 요소들에 대한 빠른 접근을 제공해 줍니다.
하지만 연관 컨테이너는 삽입되는 요소의 위치를 지정할 수는 없습니다.
이러한 연관 컨테이너는 보통 균형 잡힌 이진 탐색 트리(balanced binary search tree)나 해시 테이블(hash table)을 이용하여 구현합니다.
연관 컨테이너의 종류
STL에서는 연관 컨테이너로 다음과 같은 클래스 템플릿을 제공합니다.
1. set
2. multiset
3. map
4. multimap
집합(set)과 멀티집합(multiset)
집합(set) 컨테이너는 저장하는 데이터 그 자체를 키로 사용하는 가장 단순한 연관 컨테이너입니다.
이 컨테이너는 벡터와 달리 오름차순으로 정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠릅니다.
집합(set)에서 키는 유일해야 하므로, 키의 중복을 허용하지 않습니다.
하지만 멀티집합(multiset)은 키의 중복을 허용하므로, 같은 값을 여러 번 저장할 수 있습니다.
이 두 컨테이너는 모두 set 헤더 파일에 정의되어 있습니다.
집합 컨테이너는 다음과 같이 선언합니다.
문법
set<템플릿인수> 객체이름;
템플릿 인수로는 집합 컨테이너에 저장될 키의 타입을 전달합니다.
다음 예제는 반복자의 범위를 매개변수로 사용하는 집합 컨테이너의 생성자를 사용하는 예제입니다.
예제
int arr[5] = {10, 20, 30, 40, 50}; // 배열 생성 및 초기화
set<int> st(arr, arr+3); // 배열의 일부 요소를 가지고 셋 컨테이너를 생성함.
cout << "현재 집합의 모든 요소는 다음과 같습니다." << endl;
copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));
cout << endl;
st.insert(60); // 요소의 추가
st.insert(70); // 요소의 추가
st.erase(20); // 요소의 삭제
cout << "현재 집합의 모든 요소는 다음과 같습니다." << endl;
copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));
실행 결과
현재 집합의 모든 요소는 다음과 같습니다.
10 20 30
현재 집합의 모든 요소는 다음과 같습니다.
10 30 60 70
위의 예제에서 사용된 STL 함수는 다음과 같습니다.
1. insert() 함수 : 컨테이너에 해당 데이터를 추가함.
2. erase() 함수 : 전달된 값과 같은 값을 가지는 요소를 컨테이너에서 모두 삭제함.
맵(map)과 멀티맵(multimap)
맵(map) 컨테이너는 키와 값의 쌍으로 데이터를 관리하는 진정한 연관 컨테이너입니다.
이 컨테이너는 집합 컨테이너와 마찬가지로 정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠릅니다.
맵(map)에서 키는 유일해야 하므로, 키의 중복을 허용하지 않습니다.
따라서 하나의 키에 하나의 값만이 연결될 수 있습니다.
하지만 멀티맵(multimap)은 값의 중복을 허용하므로, 하나의 키가 여러 개의 값과 연결될 수 있습니다.
이 두 컨테이너는 모두 map 헤더 파일에 정의되어 있습니다.
맵 컨테이너는 다음과 같이 선언합니다.
문법
map<템플릿인수> 객체이름;
템플릿 인수로는 맵 컨테이너에 저장될 키의 타입과 값의 타입을 전달합니다.
다음 예제는 맵 컨테이너에 요소를 추가하는 방법을 알려주는 예제입니다.
예제
map<string, int> mp;
mp.insert(pair<string, int>("국어", 80)); // 익명의 pair 객체를 생성하여 추가함.
mp["수학"] = 100; // 첨자 연산자를 이용하여 추가함.
cout << "현재 맵의 모든 요소는 다음과 같습니다." << endl;
map<string, int>::iterator it;
for(it = mp.begin(); it != mp.end(); it++)
{
cout << it->first << " : " << it->second << endl;
}
실행 결과
현재 맵의 모든 요소는 다음과 같습니다.
국어 : 80
수학 : 100
맵 컨테이너 요소의 키는 first라는 멤버 변수에, 값은 second라는 멤버 변수에 각각 저장되어 있습니다.
순서가 지정되지 않은 연관 컨테이너
순서가 지정되지 않은(unordered) 연관 컨테이너는 순서가 지정된 기존의 연관 컨테이너와 같은 동작을 합니다.
기존의 연관 컨테이너는 트리(tree) 구조를 기반으로 동작하지만, C++11부터 추가된 이 컨테이너는 해시 테이블(hash table)을 기반으로 동작하게 됩니다.
따라서 요소의 추가, 삭제 속도가 빨라졌으며, 다양한 검색 알고리즘을 사용할 수 있게 되었습니다.
순서가 지정된 연관 컨테이너는 양방향 반복자를 지원하지만, 이 컨테이너는 순방향 반복자만을 지원합니다.
C++11부터 추가된 순서가 지정되지 않은 연관 컨테이너는 다음과 같습니다.
1. unordered_set
2. unordered_multiset
3. unordered_map
4. unordered_multimap
