[C++ STL] 3-2. 컨테이너 - 연관 컨테이너(associate container)

공부 내용을 정리하는 목적 이므로 참고용으로만 읽어 주시기 바랍니다. 틀린 부분에 대한 지적은 감사합니다.

1. 연관 컨테이너(associate container)란?

연관 컨테이너는 key 와 value를 통해 관계있는 값을 묶어서 저장하는 컨테이너이다. 따라서 key 와 value를 통해 요소에 빠른 접근은 가능하지만 연관 컨테이너는 자체적인 기준을 가지고 요소를 정렬하기 때문에 삽입되는 요소의 위치를 지정할 수 없다. 주로 균형 이진 트리(balanced binary search tree)나 해시 함수(hash function)을 사용해 구현된다.

2. set & multiset

set은 key만 가지고 있는 연관 컨테이너 이다. 따라서 저장하는 값이 key가 되고 오름차순으로 정렬된 위치에 요소를 삽입하여 검색 속도가 매우 빠르기 때문에 데이터의 존재 유무를 파악하는데 유용하다. 다른 정렬 기준을 사용하고 싶다면 템플릿 매개변수에서 지정할 수 있다. 또한 정렬시 key의 중복을 허용하지 않는다.

multiset 은 key를 중복되게 컨테이너에 저장할 수 있다는 것 외에는 set과 다른 것이 없다. 따라서 set을 사용해야 하는데 key의 중복을 허용해야 한다면 multiset을 사용하면 된다. multiset은 키의 중복이 허용되어 같은 값을 여러개 저장할 수 있다.

 

문법)

#include <set>

 

set<타입> 셋이름(생성자 인수);

multiset<타입> 멀티셋이름(생성자 인수);

 

set과 multiset은 차이가 없기 때문에 set을 기준으로 정리하자. 생성자 인수에 따른 컨테이너의 생성은 다음과 같다.

set s; : 빈 set컨테이너 생성 

set s(pred); : s는 빈 컨테이너로 정렬 기준은 pred 조건자를 사용한다 

set s(s2); : s는 s2 컨테이너의 복사 생성자 

set s(b,e); : s는 반복자 구간 [begin, end)로 초기화된 원소를 갖는다. 

set s(b,e, pred); : s는 반복자 구간 [begin, end)로 초기화된 원소를 갖는다. 정렬 기준은 pred 조건자를 이용한다 

 

간단한 예시를 통해 set을 확인해 보면

정수 데이터를 순서없이 무작위로 10 50 40 20 30로 set컨테이너에 추가했다. 그리고 바로 set의 원소를 차례로 출력해보니 오름차순으로 정렬이 되어있는것을 확인할 수 있다. 또한 find함수를 통해 set에 원소의 존재 유무를 빠르게 파악할 수 있는데 반환값으로 해당 요소가 존재하면 요소의 위치를 담은 반복자를 반환해주고 존재하지 않는다면 end()의 반복자를 반환한다.

set의 경우 데이터를 중복되게 넣을경우 중복을 허용하지 않지만 multiset은 중복된 데이터도 전부 오름차순으로 정렬하여 가지고 있는것을 확인할 수 있다.

 

set의 멤버함수를 정리하면 다음과 같다.

s.size() : s의 원소 개수를 반환

s.empty() : s가 비어있는지 확인

s.clear() : s의 모든 원소를 제거

s.begin() : s의 시작을 가리키는 반복자 반환

s.end() : s의 끝을 가리키는 반복자 반환

s.insert(x) : s에 값이 x인 원소 추가

s.erase(x) : s에서 값이 x인 원소 삭제

s.erase(iter) : 반복자 iter가 가리키는 원소 삭제

s.erase(b,e) : 반복자 구간 [b, e)의 모든 원소를 삭제한다.

s.find(x) : s에서 값이 x인 원소를 찾아 존재하면 해당 원소의 위치를 가리키는 반복자를 반환하고 존재하지 않으면 end() 반복자를 반환

s.count(x) : s에서 값이 x인 원소의 개수를 반환

s.rbegin() : s의 역순의 시작을 가리키는 반복자를 반환

s.rend() : s의 역순의 끝을 가리키는 반복자를 반환

3. map & multimap

map은 key와 value를 쌍으로 가지는 연관 컨테이너이다. key를 인덱스로 value를 해당 인덱스에 대응하는 요소로 사용하여 인덱스를 int가 아닌 다른 자료형으로 사용하여 value에 접근할 수 있다. 따라서 데이터와 데이터를 묶어서 빠르게 검색할때 유용하게 쓰인다. 또한 map은 key의 중복을 허용하지 않기 때문에 하나의 key에는 하나의 value만이 연결되어있다. 

multimap또한 map과 다른점은 key를 중복해서 가질수 있다는 점이다. 하나의 key가 여러 value와 연결될수 있다.

 

문법)

#include <map>

 

map<key type, value type> 맵 이름;

multimap<key type, value type> 멀티맵 이름;

 

간단한 예시를 통해 map을 확인해 보자.

위와 같은 3가지 방법으로 map에 원소를 추가할 수 있다. key와 value로 이루어진 pair객체를 insert함수로 삽입하거나 m[key] = value;처럼 한눈에 보기 쉬운 방식을 지원한다. 또한 map컨테이너의 멤버 변수로 first는 key값을 second는 value값을 저장하고 있으므로 반복자를 이용해 접근하면 확인할 수 있다. 

find함수를 사용하면 해당 key가 존재한다면 해당 key의 위치를 가리키는 반복자를 반환하고 그렇지 않으면 end()에 해당하는 반복자를 반환한다. 반복자를 반환하기 때문에 earse()함수를 이용해 바로 삭제를 진행할 수 있다.

 

map의 멤버 함수를 정리하면 다음과 같다.

m[k] = v; : m에 key가 k이고 value가 v인 값을 저장한다.

m.insert(pair<key type, value type>(k, v)); : m에 key가 k이고 value가 v인 값을 저장한다.

m.insert(make_pair(k, v)); : m에 key가 k이고 value가 v인 값을 저장한다.

m.size() : m의 원소 개수를 반환

m.empty() : m이 비어있는지 확인

m.begin() : m의 시작을 가리키는 반복자 반환

m.end() : m의 끝을 가리키는 반복자 반환

m.erase(k) : m에서 key가 k인 원소 삭제

m.erase(iter) : 반복자 iter가 가리키는 원소 삭제

m.erase(b,e) : 반복자 구간 [b, e)의 모든 원소를 삭제한다

m.find(k) : m에서 key가 k인 원소를 찾아 존재하면 해당 원소의 위치를 가리키는 반복자를 반환하고 존재하지 않으면 end() 반복자를 반환

m.count(k) : m에서 key가 k인 원소의 개수를 반환

 

4. 순서가 정해지지 않은 연관 컨테이너(unordered associate container)

순서가 정해지지 않은(unordered) 연관 컨테이너는 앞서 정리한 map, set 등과 완전히 같게 동작한다. find(), earase()등의 함수를 사용하는데 차이가 없다.

다른점은 앞의 연관 컨테이너는 원소가 저장될때 정렬기준에 따라 저장되었지만 unordered는 랜덤하게 저장되며 앞의 컨테이너는 tree를 기반으로 동작하지만 unordered는 해쉬 함수(hash function)을 기반으로 동작한다. 따라서 원소의 추가, 삭제, 검색 속도가 상수 시간으로 동작되므로 빨라졌으며, 다양한 검색 알고리즘을 사용할 수 있다.

 

#include <unordered_set>, #include <unordered_map> 의 헤더파일이 필요하며

• unordered_set
• unordered_multiset
• unordered_map
• unordered_multimap

이 존재하고 사용법은 기존의 set, map과 동일하다.