[C++] 연관 컨테이너, 집합과 맵

[C++] 연관 컨테이너, 집합과 맵

---

연관 컨테이너 (Associative Container)

삽입/제거된 요소의 순서를 유지는 하는 순차컨테이너의 특성을 무시하고 요소를 검색하는 과정을 최대한 빠르게 수행하는데 초점을 맞춘 컨테이너이다. 속간 복잡도는 O(logN) or O(1)를 가진며 set, map, hash등이 있다.

---

집합 (Set)

#include <set>
//...
set<key, compare, alloc>
//key : 요소의 타입, compare : 삽입하는 요소를 비교하는 함수
//
set<DataType> s;

수학의 집합의 성질을 가지고 있는 컨테이너로 개체들이 집합에 포함되거나 포함되지 않는 두가지 형태를 가진다.

Set의 구조

▹ 같은 개체의 인스턴스를 한개만 보관가능. 즉, 중복을 없앤다.

▹ 요소들이 추가된 순서가 아닌 특정한 순서(compare : 비교함수)에 따라 보관하므로 정렬된 연관 컨테이너라고도 불린다.

▹O(logN)의 속도를 위해 균현 잡힌 이진트리로 구현한다.

집합 함수

set<DataType> s;

s.insert(x); //x원소 추가
s.erase(x); //x원소 제거
s.clear(); //모든 원소 제거
s.find(x); //x에 해당하는 반복자 반환(위치를 알수 있음)
s.count(x); //해당 x원소가 있으면 1, 아니면 0 반환
s.empty(); //비어있는지 조사 bool
s.size(); //원소들의 수 반환

---

맵 (Map)

#include <map>
//...
map<key, data, compare, alloc>
//key : 맵의 키로 이용될 데이터형
//data : 실제 요소에 이용될 데이터형
//compare : 맵에 추가될 키를 비교/정렬하는 함수

//생성자
map<key, value> //key와 value는 pair형태이다

연관 컨테이너답게 빠른 검색작업을 지원하는 목표를 가지며 특정요소에 대한 검색이 빠르다. 집합과 비슷한 메모리 이용패턴을 가지지만 키의 두가지 분리된 데이터를 이용한다.

▹ 요소들이 보관된 순서로 요소들을 탐색할 수 있다.

▹ 균형잡힌 이진트리로 구성이 되어있다.

▹ 존재하지 않는 키로 요소를 읽으려하면 키의 디폴트 요소가 추가되고 리턴된다. 

맵 함수

map<DataType1, DataType2> m;//DataType1 = key, DataType2 = valye
//함수
m.insert(make_pair(key,value)) //원소를 pair형태로 추가
m.erase(key) //key값에 해당하는 원소 제거
m.clear() //모든 원소 제거
m.find(key) //key에 해당하는 반복자 반환
m.count(key) //key값에 해당하는 원소들의 개수를 반환
m.empty() //비어있는지 조사 bool
m.size() //원소들의 수 반환

---

집합과 맵 요약표

	집합(Set)	맵(Map)
요소 추가/삭제	O(logN)	O(logN)
요소 검색	O(logN)	O(logN)
메모리 할당	삽입 / 제거 시 매번	삽입 / 제거 시 매번
탐색 성능	리스트보다 약간 느림	리스트보다 약간 느림

---

오늘은 연관 컨테이너와 집합과 맵에 대해서 알아보았다. 연관 컨테이너는 순차 컨테이너와는 다르게 검색에 용이하며, 집합과 맵 또한 연관 컨테이너이기에 검색에 용이하며 이것의 속도를 위해 균형잡힌 이진트리로 구성이 되어있다.

집합은 동일 좌표를 여러번 처리하지 않도록 해주는 충돌 집합에 유용하며 맵은 문자열을 이용해 특정한 개체를 찾는 빠른 사전으로 이용하는 것에 유용한것 같다.