STL 정렬연관 컨테이너

• wiki 스타일로 변경 : 2009/12/23

Contents

앞서 sequence container에서 STL Sequences 컨테이너에 대한 내용을 다루었다. 여기에서는 정렬 연관 컨테이너 (Association Container)에 대해서 알아볼 것이다. 우선은 Association 컨테이너가 Sequences 컨테이너와의 다른 점을 알아보도록 하자.

Association 컨테이너는 Sorted Associative Container 과 Hash Associative Container 2개의 컨테이너를 포함한다. 원문은 정렬 연관 컨테이너만 설명했으나 이번 wiki 스타일로 문서를 변경하면서 Hash Associative 컨테이너에 대한 설명도 포함하기로 했다.

Assocative 컨테이너라고 부르는 이유는 입력되는 원소들이 키=>값형태로 키로 서로 연관 되어있기 때문이다. Sequence 컨테이너와 마찬가지로 컨테이너의 크기는 자유롭게 확장되며, 키를 기준으로 원소를 검색할 수 있다.

Association 컨테이너는 정렬 연관 컨테이너와 Hash 연관 컨테이너의 두가지 종류가 있다. 여기에서는 정렬 연관 컨테이너만 다룬다. Hash 연관 컨테이너는 Hash Association Container를 참고한다. Associative Container은 키=>값의 형태를 가진다. 정렬 연관 컨테이너는 원소가 입력되면 키를 기준으로 정렬이 된다.

아래의 예는 Association 컨테이너중 가장 대표적인 map 에 대한 간단한 예제이다.

예제 : name_map.cc 위의 예제를 컴파일 해서 실행시키면, 다음과 같은 결과를 볼 수 있다. 키값인 yundream, zood, goodday를 기준으로 정렬되어 있는걸 볼 수 있다. 정렬 연관 컨테이너도 다른 STL 컨테이너와 마찬가지로 컨테이너의 크기가 자동으로 조절된다. 원소의 삭제/삽입을 지원하지만, Sequence 컨테이너와 같이 특정한 위치에 원소를 삽입할수 있는 기능은 제공하지 않는다. 원소의 입력시 정렬이 되므로 특정 위치에 원소를 삽입하는게 의미가 없다.

정열연관 컨테이너에는 map, multimap, set, multiset 등이 있다. 다음장에서는 이러한 각각의 컨테이너에 대해서 알아보도록 하겠다. map 은 Sorted 정렬 연관 컨테이너 이며, Key 와 Value 의 쌍으로 이루어진 자료구조이다. php나 perl, python 과 같은 언어에서 map 은 매우 기본적인 자료구조다. 이들언어를 사용해 봤다면 ("mon" => "월요일", "Tue => "화요일") 과 같은 문법에 익숙할것이다. 다른 컨테이너와 마찬가지로 key와 value 에 사용되는 자료형태에 제한은 없다. int, string, 포인터, object, struct, 또다른 컨테이너 들까지 사용할 수 있다.

map 를 사용할때 key 는 중복되면 안된다. 만약 key 가 중복되면 되면, 이전의 value 의 값을 덮어써 버린다. key 는 유일해야 한다.

map 은 다음과 같이 선언할수 있다.

표 1. 템플릿 Parameters

Parameter	설명	기본값
Key	map 의 key 이다.
Data	Key의 값으로 입력되는 데이터
Compare	Key 가 정렬되기 위해사용되는 크기 비교함수이다. 첫번째 아규먼트가 2번째 아규먼트보다 작으면 true 를 그렇지 않으면 false 를 리턴하도록 만든다.	less<key>
Alloc	map의 할당기 이다. map 은 이 할당기를 통해서 메모리 관리를 한다.	alloc

보통은 기본할당기를 사용하게 됨으로 다음과 같이 map 을 만들어서 사용할수 있다. map 의 parameter 중에 3번째를 보면 Compare 가 있다. 이것은 Key 비교를 위한 함수이다. 위의 예제의 경우는 Compare 함수를 정의해서 사용하지 않고 있다. 이유는 string이 비교가능한 데이터 타입이기 때문이다. 그러나 char * 타입의 경우에는 char * 타입간 비교가 불가능하므로 아래와 같이 Compare 함수를 선언해서 사용해야 한다. 기본적으로 STL 에서 사용되는 대부분의 컨테이너들은 같은이름의 함수를 제공한다. 이는 프로그래머로 하여금 쉽게 사용할수 있도록 하기 위함이며, 간단히 컨테이너 이름만 바꿈으로써 전혀 다른 컨테이너로의 전환이 손쉽게 하기 위함이다.

Associative Container 는 Sequence 컨테이너와 다르게 인덱스 첨자를 이용한 접근이 불가능 하다. 원래가 첨자를 통해서 원소에 접근하는 방식이 아니기 때문이다. map 의 경우 iterator 나 Key 이름을 통해서 접근해야만 한다.

iterator 의 사용은 다른 STL 컨테이너와 같이 컨테이너의 처음위치를 돌려주는 begin() 과 마지막을 돌려주는 end()가 있다.

이들은 다음과 같이 사용할 수 있다. find()를 이용하면 일치하는 key 이름을 가르키는 iterator 를 되돌려준다. 원소를 삽입하거나 변경하기 위한 가장 간단한 방법은 "name[key]=value" 을 이용한 방법이다. 동일한 key 이름이 없다면 새로 삽입될것이고, 이미 동일한 key 이름이 있다면 기존의 key 의 value 값이 변경될 것이다.

또한 insert()라는 함수를 이용해서 원소를 추가할 수도 있다. (이함수는 다른 multimap, set, multiset 등에도 사용된다). insert 를 이용해서 원소를 삽입할경우 x 키가 이미 있다면, 변경되고 그렇지 않다면 삽입된다. iterator 을 줄경우 insert 를 위해서 위치검색을 하게될 위치를 지정해 줄수도 있다. 값을 변경하는 또다른 방법은 iterator->second 를 이용한 방법이다. 원하는 키 값의 위치를 find() 를 통해서 찾아내고 iterator->second = value 의 방식을 이용해서 값을 변경할수 있다.

원하는 key 를 삭제하기 위해서 erase()를 사용하면 된다. key 값을 이용해서 삭제할수도 있고, 위치를 가르키는 iterator 를 알고 있을경우 iterator 를 이용해서 삭제할수도 있다. 다음과 같이 2 개의 iterator 를 이용해서 특정범위의 요소를 모두 삭제할수도 있으며 컨테이너에 포함된 모든 요소를 삭제할수도 있다. erase(begin(), end())로 clear()과 같은 일을 할 수 있다. 현재 컨테이너에 포함된 원소의 크기를 알려주기 위해서 2개의 함수를 제공한다. size() 는 현재 컨테이너에 포함된 원소의 갯수를 알려준다. empty()는 컨테이너에 원소가 있는지 없는지 확인한다. 원소가 없다면 1 그렇지 않을경우 0을 되돌려준다. empty() 조사는 size() == 0 을 통해서도 검사할수 있겠지만, 단지 원소의 유무를 조사하길 원한다면 empty() 를 사용하도록 하자.

swap()을 제공한다. 이것을 이용하면 요소를 덮어쓸수 있다. count()를 사용하면 해당 key 가 몇개의 값를 가지고 있는지 확인할수 있다. 그러나 map 에서는 하나의 key 에 하나의 값만을 가지게 되므로, key 의 존재유무를 파악하는정도로만 사용 할 수 있다. 이 함수는 하나의 키가 여러개의 값을 가질수 있는 multimap 에 유용하게 사용할수 있을것이다.

key 를 중복된다는 점을 제외하고 map 과 동일한 특징을 가진다. multimap 는 다음과 같이 선언할수 있다.

표 2. 템플릿 Parameters

Parameter	설명	기본값
Key	map 의 key
Data	Key 가 가리키는 데이타
Compare	Key 가 정렬되기 위해사용되는 크기 비교함수이다. 첫번째 아규먼트가 2번째 아규먼트보다 작으면 true 를 그렇지 않으면 false 를 리턴하도록 만든다.	less<key>
Alloc	multimap의 할당기	map 은 이 할당기를 통해서 메모리 관리를 한다.	alloc

기본적으로 map 과 동일한 함수를 사용한다. 다만 동일한 키를 가지게 됨으로 이를 지원하기 위한 추가적인 함수를 필요로 한다. 또한 map 와 같은 name[key] = value; 와 같은 삽입을 지원하지 않는다. insert 함수를 이용해서 삽입해야 한다. 하나의 key 가 여러개의 값을 가질수 있음으로, key 가 몇개의 값을 가지고 있는지 확인할수 있는 함수가 필요하다. count()함수를 이용해서 몇개의 값을 가지고 있는지 확인할 수 있다. 이함수도 map 에서 사용할수 있겠지만, map 에서의 용도라면 찾기원하는 key 가 있는지 없는지 정도가 될것이다. 키의 값을 가지고 오기 위해서 find()로는 부족할것이다. find 는 단지 처음에 일치된 key 의 iterator 값만을 돌려줄것이기 때문이다. 그래서 lower_bound()와 upper_bound 라는 함수가 중요하게 사용된다. (이들 두 함수는 map 에서도 사용할수 있지만 map 에서는 거의 사용할 일이 없다.) 예를 들어 key "a" 가 가지는 모든 값을 가져오길 원한다면 위의 코드는 count()와 find()를 이용한 코드로 바꿀 수 있다.

map, multimap 과 달리 set 은 "키"가 곧 "값" 이된다. 정렬되는 list 와 매우 비슷하다.

set 은 키는 유일해야 한다. 만약 동일한 key 를 insert 하게 된다면, 덮어쓰게 된다.

set 은 특히 includes, set_union, set_intersection, set_difference 와 같은 집합관련 알고리즘과 자주 사용된다. 왜냐하면 list 와 달리 set 은 기본적으로 컨테이너의 요소들이 Sort 되어서 저장되는 Sorted Associative Containers 로써, 이들 알고리즘을 매우 효율적으로 적용시킬수 있기 때문이다(알고리즘에 대해서는 나중에 다루겠다.).

다음은 set_union 을 이용하여 두개의 set 컨테이너의 합집합을 구하는 예제이다. Sequence 컨테이너의 선언에 단지 정렬을 위한, 함수만 하나 추가되었다고 보면 된다.

표 3. 템플릿 Parameters

Parameter	설명	기본값
Key	set 의 key 이다.
Compare	set 요소가 정렬되기 위해사용되는 크기 비교함수이다. 첫번째 아규먼트가 2번째 아규먼트보다 작으면 true 를 그렇지 않으면 false 를 리턴하도록 만든다.	less<key>
Alloc	set의 할당기 이다. set 은 이 할당기를 통해서 메모리 관리를 한다.	alloc

set 도 정렬 연관 컨테이너 이므로 원소를 정렬 할 수 있도록 비교함수가 정의되어 있어야 한다. 물론 int, string 과 같은 타입의 원소를 컨테이너에 적재 할 때는 굳이 비교함수를 정의할 필요가 없을것이다.

역시 다른 컨테이너들과 중복되는 비슷한 일을 하는 같은 이름의 함수들이 많으므로, 익히고 사용하는데 어려움이 없을것이다.

map 와 마찬가지로 "첨자" 접근이 불가능하므로 iterator 를 통해서 접근해야 한다. begin()과 end()를 사용해서 각각 컨테이너의 처음과 마지막의 위치를 되돌려줄수 있다.

아래는 사용 예이다. {[{#!plain #include <set> struct ltstr { bool operator()(const char *s1, const char *s2) const { return strcmp(s1, s2) < 0; } };

int main() { set<char *, ltstr> mydata; mydata.insert("a"); mydata.insert("b"); mydata.insert("c");

set<char *, ltstr>::iterator mi = mydata.begin();

while(mi != mydata.end()) { cout << *mi << endl; *mi++; } } }}} 특정키의 위치를 알고 싶을때는 find() 함수를 사용하면 된다. 이함수를 사용하면 해당키의 위치를 가리키는 iterator 를 리턴한다. 만약 찾는 값이 없다면 NULL 을 리턴한다. 삽입을 위해서 insert()라는 함수를 사용한다. 만약에 동일한 키가 컨테이너 안에 있다면 겹치게 되고, 그렇지 않다면 insert 하게 된다. insert()할때 원소는 비교함수에 의해서 자동적으로 정렬이 된다. 삭제를 위해서 erase() 함수를 사용한다. key 값으로 지울수 있으며, iterator 로 특정한 위치를 지정하거나, 특정한 범위내(first 와 last)의 원소를 삭제할수 있다. 모든 원소를 삭제하기 원한다면 clear()를 사용한다. 현재 컨테이너에 포함된 원소의 크기를 알기 위해서 사용한다. 원소가 있는지 없는지만 확인하기 원한다면 empty()를 사용하도록 하자. 이외에도 count()라는 함수가 있다. 이것은 동일한 key 값을 가지는 원소가 몇개있는지를 검사하고자 할때 사용하는데, set 은 한번에 하나의 key 만 가질수 있으므로 별로 사용할 필요가 없을것이다. 이것은 multiset 컨테이너에 유용하게 사용될수 있을거이다.

하나의 키 값만을 가질수 있는 set 에 비해서 동일한 여러개의 키값을 가질수 있다. 그 점을 제외하고는 set 과 동일하게 사용하면 된다.

set 과 마찬가지로 집합관련 알고리즘과 함깨 유용하게 사용될수 있다. set 과 동일하다. 다만 count() 함수와 lower_bound()와 upper_bound()등의 함수등을 좀더 현실적으로 사용할수 있다. 이상 Association Container 에 대한 간략한내용에 대해서 알아보았다. 사실은 그럴듯한 예제를 하나 만들어서 설명하고 싶었지만 컨테이너에 대한 내용자체가 방대한 관계로 사용방법을 익히는데 무리 없을 정도의 코드로 설명을 대신하였다.

이 다음장에서는 지금까지 STL 을 다루면서 자주 보아왔던 iterator 와 알고리즘에 대해서 알아보도록 하겠다(우리는 이미 알고리즘을 이번장에서 사용했다. set_union 과 같은 것들이 그것이다).