(C++)연관컨테이너(set, multiset, map, multimap)

연관 컨테이너와 시퀀스 컨테이너(vector, deque, list)의 차이

 

각 원소를 삽입할때 연관 컨테이너는 자동으로 함수객체(디펄트로 less객체)에 따라 정렬되며, 또한 시퀀스컨테이너는 배열, 리스트로 구현되는것과 다르게 내부 데이터가 Balaced Tree로 구현된다.  push_back(), push_front(), front(), back()같은 함수가 존재하지 않는다.

 

그렇기에 접근에 유리한 vector와 deque / 삽입, 삭제에 유리한 List 에 비해 연관 컨테이너는 탐색에 Log 시간대를 가지며 유리하다.

또한 연관컨테이너는 4개 모두 같은 인터페이스를 가진다.

 

multi?

multi가 붙은 컨테이너는 키값의 중복을 허용한다. equalrange(), lower_bound(), upper_bound() 함수를 통해 중복되는 데이터의 범위를 가져올 수 있다. 

 

set

set은 키값과 value가 하나로 통일된 컨테이너이다.  

 

multiset 

set에서 키값의 중복이 허용된 set이다.

 

map

키값과 value가 따로 분리된 컨테이너로써 map객체[key값] = value값; 식으로 손쉽게 원소를 집어넣을 수 있다. 만약 []안에 들어간 key값이 없다면 새로 만들어서 value값을 집어넣는다.

 

multimap

map에서 키값의 중복을 허용한 컨테이너로써 map과같이 []을 통한 원소 삽입은 불가하다.

 

map vs unordered_map

map과 다르게 unordered_map이 존재하는데 map이 트리 구조로 구현되어 순서가 필요한 구조나 반복자를 돌때 빠르지만 컨테이너의 크기가 커질수록 Insert, delete,탐색 시 시간이 점점 오래 걸린다.

 

하지만 unordered_map은 내부가 해쉬맵으로 구현되어 있다. 그렇기에 탐색 시 map은 O(logn)에 비해 unordered_map은 O(1)의 시간대를 가진다. 

 

기본적인 STL의 컨테이너들을 살펴봤는데, 가장 중요한건 이들을 적재적소에 사용 함으로써 실제 수행속도를 올려야 된다는것이다.  

 

앞으로 프로젝트 시 배운 특징들을 기억하여 잘 써먹어 봐야겠다.