정렬 연관 컨테이너

시퀀스 컨테이너에서는 데이터 아이템의 상대적인 순서를 유지하기 위해서 데이터 아이템들을 선형으로 저장하지만, 정렬 연관 컨테이너에서는 이러한 상대적 순서가 없어지고, 대신에 아이템에 담긴 키(key) 값으로(아이템 자체가 키인 경우도 있다) 원하는 아이템을 빠른 시간 내에 찾아낼 수 있도록 되어 있다.

 

연관 검색을 구현하는 방법 중에서 가장 일반적인 방법은 키 값을 저장할 때는 전순서(total order)로 정렬해서 저장하고(예를 들어, 아이템이 숫자인 경우에는 숫자 크기 순으로, 아이템이 문자열인 경우에는 사전식 순으로), 검색할 때는 이항 검색 알고리즘을 사용하는 것이다. 또 한 가지 방법은 해쉬(hash)를 사용하는 것인데, 키 공간(key space)을 몇 개의 부분 집합으로 나눈 뒤에 각각의 키를 이들 부분 집합 중 한 곳에 삽입해 두고, 나중에 검색을 할 때는 "해쉬" 함수를 이용해서 주어진 키가 어느 부분 집합에 속해 있는지를 찾아내어 해당 부분 집합만을 검색하는 방법이다. 첫 번째 방식은 정렬 연관 컨테이너(sorted associative container)라 불리는 것으로, 균형 이진 검색트리(balanced binary search tree)를 이용하여 구현할 수 있으며, 두 번째 방식은 해쉬 연관 컨테이너(hashed associative container)라 불리는 것으로 해쉬 테이블을 이용하여 구현된다.

 

해쉬를 이용한 방법의 가장 큰 장점은 저장과 검색시의 평균 소요 시간이 상수라는 점이다. 반면에 정렬을 이용한 방법은 항상 일정한 성능을 보여준다(다시 말해, 최악의 경우에서 해쉬 테이블 연산은 최악 소요 시간이 테이블의 사이즈, N에 비례하는 선형 소요 시간이 될 수 있지만, 균형 이진 트리(balanced binary tree)에서는 소요 시간이 항상 O(log N)이다).

 

기본적으로는 정렬 연고나 컨테이너와 해쉬 연고나 컨테이너가 모두 C++ 표준 라이브러리에 포함되는 것이 좋겠으나, 실제로는 정렬 연관 컨테이너만 포함되어 있다.

 

STL 정렬 연관 컨테이너 클래스에는 set, multiset, map, multimap 이렇게 네 가지가 있다. 셋과 멜티셋에서는 데이터 아이템 자체가 키로 사용되는데, 셋은 중복키를 허용하지 않는 반면에, 멀티셋은 중복키를 허용한다. 맵과 멀티맵의 데이터 아이템은 키 값과 데이터가 하나의 쌍으로 구성되어 있으며, 맵은 중복키를 허용하지 않는 반면에, 멀티맵은 중복키를 허용한다.

 

비록 기본적인 특징은 서로 다르지만, 정렬 연관 컨테이너와 시퀀스 컨테이너는 많은 부분에서 서로 공통점을 가지고 있다. 그 이유는 정렬 연관 컨테이너에서도, 선형 시퀀스처럼 데이터 아이템들을 차례로 순회해야 할 경우가 발생하는데, 이를 위해서는 시퀀스 컨테이너에서  정의된 것과 동일한 컨테이너 접근자들이 필요하기 때문이다. 순회할 때 정렬 연관 컨테이너에서 제공하는 양방향 반복자를 이용하여 순회하면, 정렬된 순서에 따라 차례대로 아이템들을 접근할 수 있다. 실제로, 아이템의 시퀀스를 정렬하고자 할 때 어떤 상황에서는(예를 들어, 데이터 아이템의 사이즈가 매우 큰 경우) 일단 먼저 멀티셋에 아이템들을 삽입하고, 그 다음에 양방향 반복자를 이용하여 멀티셋을 순회하는 것이 제네릭 sort 알고리즘이나 리스트의 sort 멤버 함수를 사용하는 것보다 훨씬 더 효율적인 경우가 있다.

 

 

1. 셋과 멀티셋

 

1.1 타입

set과 multiset 클래스의 템플린 인자는 모두 다음과 같다.

template <typename Key, typename Compare=less<Key>, class Allocator = allocator<Key>>

첫 번째 인자는 컨테이너에 저장될 키의 타입이고, 두 번째 인자는 아이템의 순서를 결정하는 비교 함수의 타입이며, 세 번째 인자는 컨테이너에서 사용할 메모리 할당기의 타입이다.

 

set과 multiset 클래스가 제공하는 타입 정의들은 시퀀스 컨테이너가 제공하는 것들과 동일하다. 즉, value_type(Key로 정의되어 있음), size_type, difference_type, reference, pointer, iterator, reverse_iterator, const_reference, const_pointer, const_iterator, const_reverse_iterator 등의 타입이 제공되며, 이와 더불어 다음 타입들이 추가로 제공된다.

- key_type : Key 타입으로 정의된다. - key_compare: Compare 타입으로 정의된다. - value_compare : Compare 타입으로 정의된다.

두 클래스 모두 key_compare와 value_compare를 정의해 두고 있는데, 이는 map, multimap과의 호환성을위한 것이다. map, multimap에서는 key_compare와 value_compare가 서로 다른 타입으로 정의되어 있다.

 

비교 함수는 키들 간의 순서 관계(order relation)를 정의할 수 있어야 한다. 특히, 컨테이너의 반복자 타입을 이용하여 선형으로 순회할 때는 이 비교 함수를 통해 순회 순서가 결정된다. 두 키의 동등(equivalence) 여부를 판단할 때 순서 관계를 사용하게 되는데, 두 키 k1과 k2가 다음 조건을 만족했을 때 이들을 서로 동등하다고 한다.

key_compare(k1, k2) == false && key_compare(k2, k1) == false

간단한 경우에는 키 동등의 정의와 == 연산자의 정의가 서로 일치할 때가 있다. 예를 들어, 키 값이 내장 수치 타입(built-in numeric type)이고 key_compare가 key_compare(k1, k2) == (k1<k2) 조건을 만족한다면, 키 동등에 관한 정의는 다음과 같이 표현할 수 있다. 

!(k1 < k2) && !(k2 <k1)

이렇게 되면, 이는 k1 == k2와 동일한 것이다. 그러나 동등의 정의와 == 연산자의 정의가 서로 일치하지 않는 경우도 있다. 간단한 예로 키가 vector<int> 컨테이너이고, 벡터 컨테이너를 비교할 때는 벡터의 첫 번째 원소만을 비교하는 key_compare가 정의되어 있다고 하자. 그렇다면 첫 번째 원소가 동일한 두 벡터는 key_compare로 비교했을 때는 서로 동등한 것이 되지만, == 연산자로 비교하면 첫 번째 원소가 동일하다 해도 나머지 원소들이 일치하지 않기 때문에 서로 동등한 것이라 할 수 없다.

 

키 동등의 개념은 모든 정렬 연관 컨테이너에서 다양하게 활용되기 때문에 위에서 설명한 차이점들을 잘 숙지하고 있어야 한다. 키 동등의 개념은 원소를 삽일할 때 이와 중복되는 (동등한) 값이 컨테이너에 존재하는지를 검사하여 삽입 여부를 결정할 때 라든지, 멀티셋에서 주어진 키와 동등한 모든 키를 찾아낼 때 사용된다. 어떤 경우든지 간에, 키 동등에 관한 언급이 있을 때는 == 연산자의 정의를 의미하는 것이 아니라 위에서 설명한 정의를 의미한다는 것을 꼭 명심하기 바란다.

 

셋과 멀티셋에서 사용하는 반복자 타입은 임의 접근 반복자가 아니라 양방향 반복자랄는 점을 명심해야 한다. 따라서, 정렬 알고리즘을 포함한 일부 알고리즘들은 셋, 멀티셋에서 사용할 수 없다. 그러나 셋과 멀티셋은 항상 정렬된 상태를 유지하고 있기 때문에 정렬 알고리즘이 그다지 중요하지 않다.

 

1.2 생성자

셋에서 제공되는 생성자에는 크게 다음 세 가지가 있다.

set(const Compare& comp = Compare()); tempate <typename InputIterator> set(InputIterator first, InputIterator last, constCompare& comp = Compare()); set(const set<Key, Compare, Allocator>& otherSet);

첫 번째 생성자는 원소가 없는 빈 셋을 만들어내는 생성자이고, 두 번째 생성자는 주어진 구간[first, last)에 속하는 원소들을 복사하여 집합을 만들어 내는 생성자이다(이 때, 중복되는 값은 제거된다). 그리고 세 번째 생성자(복사 생성자)는 otherSet과 동일한 셋을 만들어 낸다. 첫 번째와 두 번째 생성자는 Compare 타입의 인자를 옵션으로 가질 수 있는데, 디폴트 값은 Compare()이다. 멀티셋 생성자자들도 원소의 중복을 허용한다는 점만 제외하면 그 형태와 의미는 셋 생성자들과 동일하다.

 

1.3 삽입

set과 multiset에서 가장 간단한 형태를 가진 insert 멤버 함수는 value_type 타입(Key 타입에 해당함)의 인자를 한 개 가지고 있다. 이 멤버 함수는 인자로 주어진 원소의 복사본을 만들어 컨테이너에 삽입한다.

 

insert 멤버 함수의 리턴 값은 set의 경우와 multiset의 경우가 각각 다르다는 점에 유의하자. 우선, set의 클래스의 insert는 다음과 같은 인터페이스를 가지고 있으며,

pair<iterator, bool> insert(const value_type& x);

그리고 multiset 클래스의 insert는 다음과 같은 인터페이스를 가지고 있다.

iterator insert(const value_type& x);

set의 insert 멤버 함수는 x가 셋에 포함되어 있는지 여부와 관계없이, x 값과 동일한 값을 가지는 원소를 가리키는 반복자와 bool 값을 함께 리턴한다. 여기서 bool 값은 x가 셋에 포함되어 있지 않아서 삽입이 성공적으로 수행된 경우에는 ture가 되고, 해당 원소가 이미 셋에 포함되어 있어 삽입이 수행되지 않은 경우에는 false가 된다. multiset의 insert 멤버 함수는 주어진 원소를 무조건 삽입하므로, bool 값을 리턴할 필요가 없다.

 

insert 함수의 소요 시간은 O(log N)에 해당한다. 여기서 N은 셋이나 멀티셋에 저장된 원소의 개수를 나타낸다.

 

지금 설명하는 insert 멤버 함수는 다른 시퀀스의 insert 멤버 함수와 달리, 삽입 위치를 나타내는 반복자가 필요하지 않다. 정렬 연관 컨테이너 내의 원소들은 항상 정렬되어 있어야 하기 때문에, 삽입 위치는 내부적으로 비교 함수를 통해서 자동으로 정해진다. 하지만 셋과 멀티셋의 insert 멤버 함수 중에는 반복자를 인자로 가지는 것도 있는데, 인터페이스는 다음과 같이 시퀀스 컨테이너의 insert 멤버 함수와 동일하다.

iterator insert(iterator position, const value_type& x);

이 함수에서 x는 원소들의 정렬 상태가 그대로 유지될 수 있는 위치에 삽입되는데, 여기서 position은 삽입 위치를 찾기 위해서 어디서부터 검색을 시작할 것인지에 대한 "힌트"로서의 역할만 담당한다. x가 성공적으로 삽입된 경우나 position이 가리키는 곳에 x가 이미 존재하는 경우에는 함수의 소요 시간이 O(log N)이 아닌 아모타이즈드 상수 시간이 된다. 이러한 성능 상의 특성을 유용하게 활용할 수 있는 경우를 예로 들자면, 이미 정렬되어 있는 컨테이너를 셋이나 멀티셋으로 복사할 때를 들 수 있다. 다음을 보자. 

vector<int>::iterator i; for(i = vector1.begin(); i != vector1.end(); ++i)     set1.insert(set1.end(), *i);

이 코드는 vector1의 원소들의 정렬 여부와는 관계없이 제대로 동작한다. 정렬되어 있지 않은 벡터를 셋으로 복사하는 경우에는

 

O(N log N) 시간이 소요되며(N은 vector1.size()), 정렬되어 있는 경우에는 O(N) 시간만이 소요된다.

 

inserter로 만든 삽입 반복자는 insert 함수로 표현될 수 있으므로, 앞의 코드는 다음과 같이 작성할 수도 있다.

copy(vector1.begin(), vector1.end(), inserter(set1, set1.end()));

좀 더 일반적으로 말해 셋, 멀티셋의 insert 멤버 함수 중에서 반복자를 인자로 가지는 insert 함수는 정렬 데이터 구조에 셋 관련 연산을 적용하는 제네릭 알고리즘에 해당하는 includes, set_union, set_intersection, set_difference, set_symmetric_difference 등의 알고리즘과 같이 사용하면 매우 유용하게 쓸 수 있다.

 

셋과 멀티셋에는 또 다른 insert 멤버 함수가 있는데, 이 함수는 지정된 구간에 속하는 원소들을 삽입할 때 사용된다.

template <typename InputIterator> void insert(InputIterator first, InputIterator last);

이 함수의 소요 시간은 O(M log(N + M))이다. 여기서 M은 구간의 사이즈이고, N은 셋 또는 멀티셋의 사이즈이다.

 

1.4 삭제

셋이나 멀티셋에서 원소를 삭제할 때는 키 또는 반복자를 이용하여 삭제할 원소를 지정한다. set1이 셋 또는 멀티셋인 경우에 키 값이 k인 원소를 모두 삭제하려면 다음과 같이 작성하면 된다.

set1.erase(k);

set1이 멀티셋이고 *i와 동일한 원소가 여러 개 중복되어 있다면, 위 코드는 i가 가리키는 원소만 삭제하며 다른 중복 원소들은 삭제하지 않는다.

우선 문자들이 담긴 STL 컨테이너를 문자열로 변환하는 make_string이라는 함수를 새로 정의해 보자.

#include <functional> template<typename Container> string make_string(const Container& c) {     string s;     copy(c.begin(), e.end(), inserter(s, s.end()));     return s; }

 

1.5 접근자

셋과 멀티셋은 정렬된 선형 시퀀스로 취급할 수 있기 때문에, 일반 시퀀스 컨테이너에서 공통적으로 사용하는 접근자를 셋과 멀티셋에서도 동일하게 제공함으로써 컨테이너에 담긴 원소와 관련된 정보들을 얻어낼 수 있다. 이러한 접근자들로는 begin, end, rbegin, rend, empty, size, max_size 등이 있다. 다른 경우와 마찬가지로, 셋과 멀티셋에서도 일반 반복자를 리턴하는 접근자 외에, 상수 셋 또는 상수 멀티셋에 적용했을 때 상수 반복자를 리턴하는 접근자를 제공한다. 그리고 키를 사용하여 정보를 얻어내는 find, lower_bound, upper_bound, equal_range 등의 멤버 함수도 제공하고 있다.

 

멀티셋에서는 find 멤버 함수가 리턴하는 반복자와 제네릭 find 알고리즘이 리턴하는 반복자가 반드시 일치하는 것은 아니다. 제네릭 find 알고리즘은 주어진 키 값을 가지는 원소들 중에서 가장 첫 번째 원소를 가리키는 반복자를 리턴하지만, find 멤버 함수가 리턴하는 반복자는 그 중 어떤 원소를 가리키게 될 지 알 수 없다. lower_bound 멤버 함수는 바로 이 첫 번째 원소를 가리키는 반복자를 리턴하며, upper_bound는 주어진 키 값을 가지는 원소들로 구성된 구간의 끝경과 반복자를 리턴한다.

 

lower_bound는 정렬 순서를 흩트리지 않고 주어진 키를 삽입할 수 있는 첫 번째 위치를 리턴하고, upper_bound는 그러한 위치 중 가장 마지막 위치를 리턴한다. 이는 주어진 키가 컨테이너에 포함되어 있는 경우에도 마찬가지이다(이는 정렬 시퀀스에 적용된 제네릭 lower_bound, upper_bound 알고리즘과 의미가 동일하다).

 

lower_bound와 upper_bound의 결과 값을 동시에 얻고 싶은 경우에는, equal_range를 호출하면 된다. equal_range는 lower_bound와 upper_bound의 두 결과 값을 한 쌍의 반복자로 리턴한다. 이름에서도 짐작할 수 있듯이, equal_range는 주어진 키와 동등한 키를 지닌 원소들의 구간을 나타내는 반복자 한 쌍을 리턴한다. 만약에 주어진 키와 동등한 키를 지닌 원소들이 없다면, 빈 구간(동일한 반복자 한 쌍으로 지정한다)을 리턴한다.

 

마지막으로, count는 lower_bound가 리턴하는 반복자와 upper_bound가 리턴하는 반복자 사이의 거리를 리턴하는데, 이 값은 주어진 키 값과 동등한 키를 가지는 원소의 개수에 해당하는 것이다.

 

count를 제외한 모든 검색 관련 함수는 상수 컨테이너에 적용하면 상수 반복자를 리턴하는(equal_range의 경우에는 상수 반복자 쌍을 리턴) 버전을 하나씩 가지고 있다. 검색 관련 함수를 설명할 때는 멀티셋만을 예로 들었지만, 셋에서도 동일하게 적용된다. 셋에서 count 함수는 항상 0 또는 1을 리턴한다.

 

검색 관련 함수에 관해서 한 가지 꼭 명심해 두어야 할 것은, 검색 함수들의 의미는 키 동등의 개념으로 결정된다는 것이며, 이키 동등의 개념은 == 연산자로 정의한 것이 아닌, key_compare를 이용하여 정의된 것이다.

 

검색에 관련된 모든 멤버 함수는 O(log N) 시간이 소요되며, 여기서 N은 셋 또는 멀티셋의 사이즈이다. 반면에 count는 O(log N+E) 시간이 소요되며, 여기서 E는 주어진 키를 가지고 있는 원소의 개수이다.

 

1.6 상등과 대소관계

모든 STL 컨테이너에서 공통적으로 사용되는 컨테이너 상등(equality)의 정의를 다시 한번 살펴보자. 

- 컨테이너에 담긴 시퀀스의 길이가 서로 같아야 한다. - 대응되는 위치에 놓인 두 원소가 각각 상등이어야 한다.   두 원소의 상등 관계는 원소 타입에 정의되어 있는 == 연산자로 결정한다.

STL의 셋과 멀티셋 컨테이너에 담긴 원소들은 항상 정렬되어 있기 때문에, 위 정의를 셋과 멀티셋에 적용하면 수학에서 사용하는 "셋", "멀티셋"의 개념과 정확히 일치하게 된다. 즉, 셋에 담긴 모든 원소들이 서로 동일하면(원소의 순서는 상등 여부와 관련 없다) 두 셋은 서로 상등이고, 멀티셋에 담긴 각 원소의 중복 개수가 서로 일치하면(원소의 순서는 상등 여부와 관련 없다) 두 멀티셋은 서로 상등이다. 이러한 성질들을 정렬 데이터 구조 상에서 수행되는 셋 관련 STL 제네릭 알고리즘들(includes, set_union, set_intersection, set_difference, set_symmetric_difference)과 함께 사용하면, 가장 기본적인 셋과 멀티셋 연산들을 수행할 수 있다.

 

그러나 실제로는 이것이 그렇게 간단하지만은 않은데, 왜냐하면 여기서의 "같다(sameness)"라는 개념은 key_compare 함수로 정의되는 키 동등(key equivalence) 관계에 해당하는 것이기 때문이다. 키 동등 개념에서는 두 개의 키 k1과 k2가 다음 조건을 만족할 때 서로 동등하다고 말한다.

key_compare(k1, k2) == false && key_compare(k2, k1) == false

그런데, 키 동등의 개념이 원소 타입에 정의되어 있는 == 연산자의 상등 개념과 반드시 일치하는 것은 아니다. 이 두 개념이 서로 일치하지 않는 상황에서는, 셋과 멀티셋의 상등 여부를 검사할 때 예기치 못한 결과를 얻을 수도 있다.

 

이와 비슷한 상황이 셋과 멀티셋의 operator<에도 존재하는데, 그 이유는 모든 컨테이너에서 이 연산자를 정의할 때 제네릭 lexicographical_compare 알고리즘을 사용하지 않고, 이 알고리즘은 원소 타입의 < 연산자를 사용하기 때문이다. 따라서, key_compare의 키 비교 방식과 원소 타입에 정의된 < 연산자의 키 비교 방식이 동일하지 않다면, 셋이나 멀티셋간의 비교 결과가 예상치 못한 것이 될 수 있다.

 

1.7 대입

모든 STL 컨테이너에 정의되어 있는 operator=를 이용하여 x=y를 수행한 뒤에는 반드시 x==y 조건이 true가 되어야 한다. 이 연산을 수행하는데는 선형 시간이 소요된다. 정렬 연관 컨테이너에는 assign 멤버 함수가 없다. 하지만 x.swap(y)을 통해서 상수 시간 내에 x와 y의 값을 서로 바꿀 수 있는 컨테이너에서는 swap 멤버 함수를 제공한다. 부분 스페셜라이제이션과 swap 멤버 함수를 이용하여 구현한 제네릭 swap 알고리즘도 있다.

 

 

2. 맵과 멀티맵

맵 컨테이너는 0, 1, 2, ...와 같은 일반 정수를 인덱스로 사용하지 않고, 키(타입은 Key)를 인덱스로 사용하는 배열이라고 보면 된다. 맵 컨테이너는 Key 타입의 키 값을 이용하여 T 타입의 데이터를 신속하게 찾아내는 정렬 연관 컨테이너이다. 멀티맵도 이와 마찬가지이며, 대신에 중복키를 허용한다. 맵과 멀티맵의 관계는 셋, 멀티셋의 관계와 동일하다.

 

맵과 멀티맵은 셋, 멀티셋이 담고 있는 각각의 키에 T 타입의 데이터를 추가로 덧붙인 것이라고 보면 된다. 이렇게 덧붙여진 추가 데이터는 컨테이너의 검색 방식이나 순회 방식에는 영향을 주지 않으며, 다만 이 데이터를 저장하거나 읽어낼 때 사용하는 일부 연산에서만 의미가 있다.

 

기능면에서, 배열(그리고 벡터와 덱)은 정수 0, 1, 2, ..., N-1(N은 음이 아닌 정수)을 키로 사용하는 맵과 비슷한 기능을 제공한다. 배열에서는 키와 데이터의 연관 관계가 매우 효율적으로 되어 있지만, 효율성을 제외한 다른 부분은 맵에 비해 상당히 제약적인 측면이 있다. 첫 째, 키는 정수만 사용할 수 있으며, 둘 째, N에 비례하는 저장 공간을 필요로 하기 때문에, 키 값 0, 1, 2, ..., N-1 중에서 일부 키만 의미 있는 데이터와 연결되는 경우에는 비효율적이다. 이와 달리, 맵과 멀티맵은 어떠한 타입의 키도 사용할 수 있으며, 필요한 저장 공간은 실제로 저장된 키의 개수에 비례한다.

 

키가 정수키인 경우에는 맵과 멀티맵에서 사용할 수 있는 "sparse 표현 방식"을 이용함으로써, 저장 공간과 계산 소요 시간을 상당히 절약할 수 있다.

 

2.1 타입

map과 multimap 클래스는 모두 다음과 같은 템플릿 인자를 가지고 있다.

template<typename Key, typename T, typename Compare = less<Key>, class Allocator = allocator<par<const Key, T>>

첫 번째 인자는 저장되는 키의 타입이고, 두 번째 인자는 키와 연관되는 데이터 타입이다. 그리고 세 번째 인자는 순서를 결정할 때 사용하는 비교 함수이며, 네 번째 인자는 메모리 할당기를 나타낸다. 맵과 멀티맵의 템플릿 인자는 두 번째 인자에 T가 추가되었다는 점만 제외하면 셋, 멀티셋의 경우와 동일하다.

 

map과 multimap 클래스는 시퀀스 컨테이너가 제공하는 것과 동일한 타입 정의들을 제공한다. 즉, value_type(map과 multimap에서는 pair<const Key, T>로 정의되어 있다), pointer, reference, iterator, reverse_iterator, idfference_type, size_type, const_iterator, const_reverse_iterator, const_pointer, const_reference가 제공되며, 다음 타입들도 추가로 제공된다.

- key_type : 타입 Key로 정의되어 있다. - key_compare : 타입 Compare로 정의되어 있다. - value_compare : 키 값을 기준으로 두 value_type 객체를 비교하는 함수 타입

 

셋, 멀티셋의 경우와 마찬가지로, 맵과 멀티맵의 반복자 타입은 임의 접근 반복자가 아니라 양방향 반복자이다.

 

2.2 생성자

맵과 멀티맵의 생성자는 셋, 멀티셋의 생성자와 형태나 의미상의 차이점이 동일하다. 즉, 맵에서는 지정된 구간으로부터 맵을 구축할 때, 중복된 키를 가지는 보사본은 제거되지만, 멀티맵에서는 중복키가 제거되지 않는다. 생성자의 소요 시간은 셋, 멀티셋과 동일하다.

 

2.3 삽입

맵, 멀티맵에 원소를 삽입할 때는 insert 멤버 함수를 이용한다. 인터페이스는 셋, 멀티셋과 동일하지만, 맵, 멀티맵에서의 value_type은 그냥 Key가 아니라 pair<const Key, T>이다. 즉, insert로 넘겨주는 value_type 인자에는 Key 타입의 값과 T 타입의 값이 같이 함께 포함되어 있다. 이미 삽입한 원소쌍의 값을 대입 연산을 이용하여 변경하는 것은 가능하지만, 이 때는 T 부분의 값만 변경할 수 있다. Key는 const로 선언되어 있기 때문에 키는 변경이 불가능하다. 이런 식으로 제약을 가하는 것은 맵 내부의 데이터를 일관성 있게 유지하기 위해서 반드시 필요한 것이다.

 

다음과 같이 operator[]를 사용하여 맵에 원소를 삽입할 수도 있다.

map1[k] = t;

map1에 키가 k인 원소쌍이 없는 경우에는 원소쌍 (k, t)을 새로 삽입하지만, 원소쌍 (k, t0)이 이미 map1에 포함되어 있는 경우에는 t0를 t로 수정한다. 원소쌍의 데이터 부분을 다른 값으로 수정하려면 다음과 같이 해도 된다.

i -> second = t;

여기서 i는 map<Key, T>::iterator이고, i->first == k 를 ture가 되게 하는 값이다

(i->first는 value_type 타입의 상수 멤버이기 때문에, i -> first = k1을 사용할수 없다).

 

다소 의아하게 들릴지 모르겠지만, 멀티맵에는 operator[]가 정의되어 있지 않다. 만약에 멀티맵에 operator[]를 정의하게 되면, 더 큰 문제가 발생하게 된다. 왜냐하면 대입 연산 multimap1[k] = v를 수행하고 난 뒤에 multimap[k] == v가 되도록, 키가 k인 모든 원소쌍을 모두 수정해야 하기 때문이다.

맵의 operator[]는 대입문의 왼편에 사용할 때 뿐만 아니라, 표현식 중간에 이 연산자를 사용해도 맵의 삽입 연산을 수행할 수 있다는 점을 주목하기 바란다. 즉, 아래의 표현식을 일반 표현식에 사용하면, 

map1[k]

k와 연관된 T 타입의 값이 맵에 포함되어 있으면 해당 값을 리턴하지만, 맵에 해당 값이 포함되어 있지 않은 경우에는 (k, T()) 원소쌍을 삽입하고 T()를 리턴한다.

 

2.4 삭제

셋과 멀티셋에서와 마찬가지로, 맵이나 멀티매벵서도 키 값이나 반복자를 통해 원하는 원소를 삭제할 수 있다. 삭제 연산을 수행할 때 T 타입의 데이터 부분은 아무런 역할도 하지 않는다. 삭제 연산은 셋, 멀티셋에서와 동일한 방식으로 수행되며, 소요 시간도 동일하다(즉, 소요 시간은 O(log N+E), 여기서 N은 맵, 멀티맵의 사이즈이며, E는 삭제된 원소의 개수이다).

 

2.5 접근자

맵, 멀티맵의 접근자도 셋, 멀티셋과 상당히 유사하다. 맵과 멀티맵에서 원소를 정보를 얻기 위해 사용하는 접근자는 셋, 멀티셋의 것과 동일하다. 즉, begin, end, rbegin, rend, empty, size, max_size들을 제공하고 있다. find, lower_bound, upper_bound, equal_range과 count는 키를 이용하여 원소 관련 정보를 얻어내는 함수들이다. 맵의 접근자에는 operator[]도 포함되어 있다. 이 접근자는 멀티맵에서는 사용할 수 없는데, 그 이유는 멀티맵에서는 주어진 키 값과 연관되는 원소가 한 개 이상일 수 있기 때문이다. operator[]를 포함한 모든 검색 연산의 소요 시간은 모두 O(log N)이다. 여기서 N은 맵이나 멀티맵의 사이즈이다. 단, const는 예외다. count 연산의 소요 시간은 O(log N+E)이며, 여기서 E는 주어진 키를 가지고 있는 원소의 개수이다.

 

2.6 상등과 대소 관계

기본적으로 맵과 멀티맵의 상등과 대소 관계는 셋, 멀티셋과 동일한 특성을 가지고 있다. 단 한 가지 차이점은 T라는 타입이 추가되었기 때문에, 키 동등의 의미와 value_type::operator==의 의미가 일치하는 경우가 드물어졌다는 것이다. 왜냐하면 value_type::operator==는 멤버 T를 대상으로 하는 반면에, key_compare는 멤버 T를 대상으로 하지 않기 때문이다. key_compare와 value_type::operator< 간의 차이점도 이와 비슷한 맥락에서 이해하면 된다.

 

2.7 대입

 

 

 

 

 

 

 

- STL 튜토리얼·레퍼런스 가이드 제2판 中 -