[STL] [2] 연관 컨테이너 정리 (Associative Container, std::set, std::map)

이전 글

[STL] [1] 순차 컨테이너 정리 (Sequence Container, std::array, std::vector, std::list, std::deque)

 

이전 글에서 STL container 개념과 그 중 하나인 Sequence Container에 대해서 정리하였다. 오늘은 STL container 중 Associative container (연관 컨테이너)에 대해서 정리하고자 한다.

 

 

 

Associative Container

Associative Container (연관 컨테이너는)는 컨테이너 내 저장된 데이터를 key 기반으로 빠르게 접근할 수 있는 컨테이너를 의미하며, 컨테이너 내 저장된 데이터는 정렬되어 있다[1].

 

An AssociativeContainer is an ordered Container that provides fast lookup of objects based on keys.

 

앞서 배운 순차 컨테이너와 구별되는 특성은 바로 Key를 기반으로 작동한다는 것이다. 순차 컨테이너 내 데이터들은 1, 2, 3, ... 순서있게 저장되어 번호를 통해서 접근할 수 있다. 그에 비해 연관 컨테이너 내 데이터들은 내부적으로 어떻게 저장되었든 상관없이 key를 통해 빠르게 접근할 수 있으면 된다. 즉 핵심은 key라는 값을 통해 어떻게 데이터에 빠르게 접근할 수 있는 지 이다[2]. (순차 컨테이너는 순서를 통한 데이터 접근을, 연관 컨테이너는 키를 통한 데이터 접근을 최적화하기 위해 설계됨[2])

 

일반적으로 연관 컨테이너는 컨테이너내에 데이터 추가, 읽기, 삭제, 확인 등을 O(log(N))의 time complexity로 수행가능하도록 설계되었다. 그렇기에 일반적으로 self-balancing binary search tree (red-black tree) 로 구현된다고 한다[2]. 이러한 자료구조는 데이터를 정렬하여 저장하는데 이를 통해 빠르게 데이터에 접근할 수 있다. 따라서 연관 컨테이너에는 strict weak ordering을 따르는 데이터(간단히 말하자면 순서를 매길 수 있는 데이터)만 추가될 수 있다. 데이터간의 순서를 매길 수 없다면 데이터를 정렬해서 저장할 수 없기 때문일 것이다. 다만 unordered associative container (hash_set, hash_map, etc.) 또한 존재하긴 한다.

 

연관 컨테이너에는 set, map, multiset, multimap이 있으며 unordered associative container 또한 포함한다면 hash_set, hash_map, hash_multiset, hash_multimap이 추가로 존재한다. 모두 key를 통해 데이터를 빠르게 참조할 수 있게 구현되어 있다. 특징을 간단히 한 줄로 정리하자면 다음과 같다.

 

• std::set[3]: key를 정렬하여 저장하는 컨테이너. Key 자체가 저장되는 데이터이고, key를 기준으로 key를 정렬함. key를 이용해 컨테이너 내에 key 추가, 삭제, 찾기가 가능함. 중복된 key는 허용되지 않음
• std::map[4]: key-value 쌍을 정렬하여 저장하는 컨테이너. Key를 기준으로 정렬하며, 중복된 key를 허용하지 않음. Key를 통해 컨테이너에 저장된 value값에 접근할 수 있음.
• std::multiset[5]: std::set과 기능적으로 동일하나, 중복 key 저장을 허용함. 같은 값을 가지는 key 여러 개가 컨테이너 내에 저장될 수 있음.
• std::multimap[6]: std::map과 기능적으로 동일하나, 중복 key 저장을 허용함. 같은 key 값을 가지는 key-value 쌍 여러 개가 컨테이너 내에 저장될 수 있음.
• std::unordered_set (hash_set)[7]: std::set과 기능적으로 동일하나, 데이터(key)를 정렬하여 저장하지 않고 hash table 상에 저장함. 각 hash table entry는 데이터를 양방향 linked list로 관리함.
• std::unordered_map (hash_map)[8]: std::map과 기능적으로 동일하나, 데이터(key-value 쌍)를 정렬하여 저장하지 않고 hash table 상에 저장함. 각 hash table entry는 데이터를 양방향 linked list로 관리함.

 

 

 

Set (std::set)

std::set은 수학에서 사용하는 집합과 같이 요소(데이터)를 중복을 허용하지 않고 저장하는 컨테이너이다. 다만 빠른 데이터 접근(추가, 삭제, 읽기, 찾기 등)을 위해서 내부적으로는 데이터를 정렬하여 저장한다는 점에서 수학에서 말하는 집합과는 다르다.

 

앞서 얘기했듯 연관 컨테이너는 Key 값을 이용하여 빠른 데이터 접근을 위해 만들어진 자료구조이다. std::set은 key라는 개념 없이 데이터만을 저장하기에 이게 왜 연관 컨테이너인지 의심할 수도 있다. 사실 std::set은 데이터 자체를 key라고 보고 key 자체를 저장하는 컨테이너이기에 연관 컨테이너라고 한다[1]. 즉 데이터(=key)만을 이용하여 std::set에서 데이터를 빠르게 저장, 삭제, 찾기가 가능하다.

 

std::set에 저장되는 데이터(=key)는 정렬가능한 데이터만 가능하다. (정확히는 strict weak ordering을 만족하는 데이터) 디폴트로 std::less<Key> 함수자를 이용하여 데이터간 순서를 결정하는데, 쉽게 생각하면 operator< 를 호출하여 둘 사이의 순서를 결정한다고 한다. (즉 일반적으로 오름차순으로 정렬된다)

 

std::set은 데이터가 있는 지 없는 지를 빠르게 찾는데에 사용될 수 있다. 예를 들어 한 나라의 모든 초등학생 개인정보를 std::set을 통해 저장했다고 하자. 그 중 "홍길동"이 초등학생인지를 확인하고 싶으면 std::set에 "홍길동"이 포함되었는 지 확인하면 된다. std::set은 O(log(N))의 time complexity를 가지기에 빠르게 확인할 수 있다.

 

 

 

Map (std::map)

std::map은 dictionary라고도 하는데 key-value 쌍을 데이터로 저장하는 컨테이너이다. 즉 쉽게 생각하면, key를 입력하면 key에 해당하는 value가 출력되는 자료구조이다. std::set과 마찬가지로 같은 key를 가지는 key-value 쌍은 허용되지 않는다.

 

빠른 데이터 접근(추가, 삭제, 읽기, 찾기 등)을 위해서 내부적으로 key 값에 따라 key-value 쌍을 정렬하여 저장한다. 따라서 std::map에 저장할 수 있는 key-value 쌍 데이터는 key 값에 대해서 정렬가능하여야 한다.

 

std::map은 key-value 쌍을 데이터로 저장하는데 주로 저장하고자 하는 값은 value이다. value를 key라는 tag를 달아 std::map에 저장, 이후 빠르게 value 값에 접근하기 위해 사용된다. value 접은 operator[]를 통해 이루어지며, braket []안에 key를 넣으면 value가 출력된다.

 

 

 

Reference

[1] C++ named requirements: AssociativeContainer - cppreference.com

[2] https://en.wikipedia.org/wiki/Associative_containers

[3] https://en.cppreference.com/w/cpp/container/set

[4] https://en.cppreference.com/w/cpp/container/map

[5] https://en.cppreference.com/w/cpp/container/multiset

[6] https://en.cppreference.com/w/cpp/container/multimap

[7] https://en.cppreference.com/w/cpp/container/unordered_set

[8] https://en.cppreference.com/w/cpp/container/unordered_map