[C++][STL Container] 연관 컨테이너 (set/map, multiset/multimap, unordered_set/unordered_map)

연관 컨테이너란?

• 연관 컨테이너(Associative Containers)는 C++에서 제공하는 STL 컨테이너 종류(시퀀스 컨테이너, 연관 컨테이너, 컨테이너 어뎁터) 중 하나로, 키(key)와 값(value)을 연관지어 데이터를 저장하는 컨테이너이다.

 

연관 컨테이너의 종류

• set / map
• multiset / multimap
• unordered_set / unordered_map

---

셋(set)이란?

• 셋은 특정 키(key)가 컨테이너 안에 존재하는지 알아보기 위한 자료구조이다.
• 중복되는 원소는 허용하지 않는다.
• 내부 구조가 레드-블랙 트리(RB-Tree)로 구현되어 있음으로, 아래와 같은 특성을 가진다.
  • 원소의 검색 / 삽입 / 삭제가 O(logN)의 시간복잡도를 가진다.
  • 원소들은 정렬된 상태를 유지한다. (기본 정렬 기준은 less<_Key>로, 오름차순이다)
• 제공하는 반복자는 "BidirectionalIterator"로, 리스트(List) 자료구조처럼 증감연산자를 통해서만 이동 가능하고, (itr + 5)와 같이 임의의 위치에 있는 원소에 접근하는 것은 불가능하다.
  • 내부 구조 특성에 의해 반복자 순회 시 정렬된 출력 결과를 얻을 수 있다.

 

레드-블랙 트리(RB-Tree)란?

레드-블랙 트리 예시

• 레드-블랙 트리는 이진 검색 트리(BST)의 특성을 지니며, 원소 삽입 / 삭제 시 “5가지 특성”을 만족하도록 트리를 변형하며 균형을 잡는(balancing) 트리이다.
• 레드-블랙 트리는 균형을 잡음으로써 “BST에서 불균형한 트리(ex. 편향된 트리)가 만들어지는 최악의 경우, 검색 작업이 O(logN)에서 O(N)으로 성능이 떨어진다”는 문제를 해결하였고, 결과적으로 최악의 경우에도 검색 작업이 O(logN)의 시간복잡도를 가져 안정적인 검색 성능을 보여준다.
• (참고로 레드-블랙 트리처럼 스스로 균형을 잡는 이진트리를 "자가 균형 이진트리"(self-balancing binary search tree)라고 부른다.)

---

set 멤버 함수

 

수정 관련(Modifiers)

insert()	해당 키 삽입. (삽입된 위치, 성공 여부를 pair<iterator, bool>로 반환)
erase()	해당 키 삭제. (삽입된 위치, 성공 여부를 pair<iterator, bool>로 반환)
clear()	set을 비운다.
swap()	지정한 set과 swap한다.

 

 

크기 관련(Capacity)

empty()	set의 size가 0인지 확인한다.(bool 타입 반환)
size()	set의 크기(원소의 개수) 반환
max_size()	가능한 최대 size 반환

 

 

조회 관련(Lookup)

count()	해당 키의 원소 개수를 반환(1 또는 0)
find()	해당 키의 반복자(iterator)를 반환. (키가 없다면 end()를 반환)
equal_range	해당 키에 매칭되는 원소의 범위를 반환 (begin(), end()를 pair로 반환)
lower_bound	해당 키보다 작지 않은(not less) 첫번째 키의 반복자(iterator)를 반환
upper_bound	해당 키보다 큰(greater) 첫번째 키의 반복자(iterator)를 반환

 

 

더 자세한 내용은 아래 참고

https://en.cppreference.com/w/cpp/container/set

std::set - cppreference.com

 

---

알아두어야 할 점

클래스를 키값으로 넣기

• set은 내부에서 정렬을 유지하기 때문에 키 타입은 반드시 정렬 기준이 될 비교 함수가 정의되어 있어야 한다.
• 따라서 클래스를 키값으로 넣게 된다면 비교 함수를 같이 넘겨줘야 한다. 넘겨주는 방법은 2가지 방법이 있다.
  • 클래스 내부에 operator < 오버로딩
  • 비교 함수가 정의된 functor를 두 번째 템플릿 인자로 넘겨주기

비교 함수 정의 방법 1. 클래스 내부에 operator <를 오버로딩

bool operator<(const Todo& t) const {
  if (priority == t.priority) {
    return job_desc < t.job_desc;
  }
  return priority > t.priority; // 중요도가 높은 값이 위로 가도록 정렬
}

 

오버로딩 시 주의사항

• operator < 오버로딩 함수는 반드시 상수 레퍼런스(const&)를 매개변수로 받는 const 함수로 정의해야 한다.
  • set은 정렬 시에 상수 반복자를 사용하기 때문에 상수 함수가 아닌 함수는 호출할 수 없다.
• 두 키 값의 비교값이 같을 경우 나중에 삽입된 키가 중복된 키로 판단되어 삽입되지 않으므로, 키 값이 다르다면 반드시 비교값이 다르도록 구분되어야 한다.

 

비교 함수 정의 방법 2. 비교 함수가 정의된 functor를 두 번째 템플릿 인자로 넘겨주기

struct TodoCmp {
  bool operator()(const Todo& t1, const Todo& t2) const {
    if (t1.priority == t2.priority) {
      return t1.job_desc < t2.job_desc;
    }
    return t1.priority > t2.priority;
  }
};

std::set<Todo, TodoCmp> todos;

 

functor 사용 시 주의사항

• 오버로딩 방식과 동일하게 두 키 값의 비교값이 같을 경우, 나중에 삽입된 키가 중복된 키로 판단되어 삽입되지 않으므로, 키 값이 다르다면 반드시 비교값이 다르도록 구분되어야 한다.

---

맵(map)이란?

map 예시

• 맵은 셋과 달리, 특정 키(key)가 컨테이너 안에 존재하는지 뿐만 아니라 키에 대응하는 값(value)까지 보관하고 있는 자료구조이다.
• 각 노드의 데이터는 <key, value> 쌍을 pair <> 타입으로 저장하고 있다.
• 맵은 값을 추가로 저장한다는 점을 제외하곤 셋과 내부 구조가 일치하므로, 셋과 동일하게 아래의 특성들을 가눈다.
  • 중복되는 원소는 허용하지 않는다.
  • 내부 구조가 레드-블랙 트리(RB-Tree)로 구현되어 있음으로, 아래와 같은 특성을 가진다.
    • 원소의 검색 / 삽입 / 삭제가 O(logN)의 시간복잡도를 가진다.
    • 원소들은 정렬된 상태를 유지한다.(기본 정렬 기준은 less <_Key>로, 오름차순이다)
  • 제공되는 반복자는 BidirectionalIterator로, 리스트처럼 증감연산자를 통해서만 이동 가능하고, 임의의 위치에 있는 원소에 접근하는 것은 불가능하다.
    • 내부 구조 특성에 의해 반복자 순회 시 출력 결과가 정렬되어 있다.

---

map 멤버 함수

 

원소 접근 관련(Element access)

at()	해당 키에 접근 (범위 검사 O)
operator []	해당 키에 접근 (범위 검사 X)

 

 

수정 관련(Modifiers)

insert()	해당 키와 값 삽입. (삽입된 위치, 성공 여부를 pair<iterator, bool>로 반환)
erase()	해당 키 삭제. (삽입된 위치, 성공 여부를 pair<iterator, bool>로 반환)
clear()	map를 비운다.
swap()	지정한 map와 swap한다.

 

 

크기 관련(Capacity)

empty()	map의 size가 0인지 확인한다.(bool 타입 반환)
size()	map의 크기(원소의 개수) 반환
max_size()	가능한 최대 size 반환

 

 

조회 관련(Lookup)

count()	해당 키의 원소 개수를 반환(1 또는 0)
find()	해당 키의 반복자(iterator)를 반환. (키가 없다면 end()를 반환)
equal_range	해당 키에 매칭되는 원소의 범위를 반환 (begin(), end()를 pair로 반환)
lower_bound	해당 키보다 작지 않은(not less) 첫번째 키의 반복자(iterator)를 반환
upper_bound	해당 키보다 큰(greater) 첫번째 키의 반복자(iterator)를 반환

 

 

더 자세한 내용은 아래 참고

https://en.cppreference.com/w/cpp/container/map

std::map - cppreference.com

 

---

알아두어야 할 점

insert()보단 [] 연산자

• 셋과 달리 맵은 [] 연산자가 있는데, 이 [] 연산자 하나로 데이터 삽입 / 검색 / 수정 작업을 다할 수 있기 때문에 매우 편리하다.
• 맵에 없는 키를 [] 연산자로 검색하는 경우, 자동으로 디폴트 생성자를 호출하여 기본값으로 초기화된 원소를 삽입한다.
  • 따라서, [] 연산자를 사용하는 경우 해당 키가 존재하는지 알고 싶다면 사용 전에 find로 먼저 확인해야 한다.
• 맵에 있는 키를 [] 연산자로 값을 삽입했다면, 키의 존재 유무와 상관없이 해당 값으로 갱신된다.
  • 반대로, insert는 중복된 키인 경우 해당 값이 무시된다.

 

map의 반복자(iterator)

• 셋의 경우 반복자의 역참조(*itr)는 키 값을 반환했지만, 맵의 반복자의 역참조는 pair <key, value>를 반환한다.
• 따라서, ranged for based for문에서 auto를 사용하면 pair<key, value>를 반환한다.

map<int, char> m1 = {
    {1, 'a'}, {2, 'b'},
    {3, 'c'}, {4, 'd'},
    {5, 'e'}, {6, 'f'}
};

for(auto elem : m1){ // auto = pair<int, char>
    cout << elem.first << ' ' << elem.second << '\n';
}

 

실행 결과

1 a
2 b
3 c
4 d
5 e
6 f

 

 

---

multuset, multimap

• multiset과 multimap은 각각 set, map에서 중복된 원소를 허락한 자료구조이다. 나머지는 전부 똑같다.
• multimap과 multiset은 잘 활용하지 않는다.

 

알아두어야 할 점

• 멀티 셋은 반복자를 통해 순차적으로 출력하면, 같은 키 값을 가진 데이터들이 전부 출력된다.
• 멀티맵은 하나의 키에 여러 원소가 대응하기 때문에 [] 연산자를 사용할 수 없으므로, equal_range() 함수를 통해 접근해야 한다.

조금 다른 의미를 가지는 몇몇 멤버함수

• 같은 키에 여러 데이터가 담기게 되면서, 셋, 맵과 다른 의미를 가지는 함수들이 있다. 목록은 다음과 같다.

count()	해당 키의 중복된 원소 개수를 반환.
find()	해당 키에 대응하는 “아무 원소”의 반복자(iterator)를 반환. (키가 없다면 end()를 반환) +) 아무 원소인 이유는 C++ 표준에서 반환 기준을 정해놓지 않았기 때문.
equal_range	해당 키에 매칭되는 원소의 범위를 반환 (begin(), end()를 pair로 반환)
lower_bound	해당 키보다 작지 않은(not less) 첫번째 키의 첫 번째 원소의 반복자(iterator)를 반환한다.
upper_bound	해당 키보다 큰(greater) 첫번째 키의 첫 번째 원소의 반복자(iterator)를 반환한다.

 

 

---

unordered_set, unordered_map(C++11)

• 내부 구조를 레드-블랙 트리가 아닌, 해시 테이블을 사용하는 set, map자료구조이다. (사용 방법은 기존 set, map과 똑같다.)
• 내부 구조가 해시 테이블로 구현되어 있음으로써, 아래와 같은 특성을 가진다.
  • 삽입 / 삭제 / 검색 모두 amortized O(1)의 시간복잡도를 가진다.
  • rehashing 하는 경우 O(N)만큼의 추가 수행 시간이 발생한다.
  • 각 원소들은 정렬된 상태를 유지하지 않는다. (unordered_xxx의 특징)

💡 unordered_set / unordered_map에서 각 작업의 시간복잡도가 amortized O(1)인 이유?

- 대부분의 경우 삽입 / 삭제 / 검색이 모두 O(1)의 시간복잡도를 가진다. 하지만 운이 나쁠 경우 모든 키가 하나의 리스트에 몰릴 수 있으므로, 최악의 경우 검색 작업은 O(N)의 시간복잡도를 가진다.
- 삽입 / 삭제는 검색 작업이 완료된 후 진행되므로, 최종 삽입 / 삭제 / 검색의 최종 수행 시간은 최악의 경우 O(N)이 된다. 
- 결과적으로 각 작업은 대부분의 경우 O(1) + 아주 가끔 O(N)이므로, amortized O(1)의 시간복잡도를 가진다.

 

해시 테이블(Hash Table)이란?

해시 테이블 예시

• 해시 테이블은 키 값이 해시 함수를 통해 만들어진 값, 즉, 해시 값을 테이블의 index를 결정하는데 활용하여 데이터를 저장하는 테이블이다.
• 해시 테이블은 해시값을 사용 가능한 index로 변환하기 위해 각 해시 값을 나머지 연산(mod) 한다.
• unordered_set, unordered_map의 경우 해시 함수의 계산 결과(해시 값)를 얻기 위해 내부적으로 아래와 같은 hash 함수 객체를 사용한다.

hash<string> hash_fn; // string -> size_t(해시 값)으로 변환하는 hash 함수 객체
size_t hash_val = hash_fn(str); // 변환된 해시 값을 저장.

 

해시 충돌(Hash Collision)

• 해시 충돌(Hash Collision)은 1) 해시 함수에서 서로 다른 키 값이 같은 해시 값으로 나오거나, 2) 서로 다른 해시 값의 나머지 연산(mod) 계산 결과가 같아 index에 충돌이 발생하는 경우를 말한다.
• 해시 충돌이 발생한 경우, 해시 테이블은 각 데이터를 리스트(list)로 저장하되, 기존 키를 함께 저장하여(<key, value> 쌍으로 저장) 데이터를 식별한다.
  • 리스트로 저장하고 있기 때문에 같은 index에서의 각 데이터 접근 시간은 O(N)이다.
  • 키 값이 string처럼 비교 연산 비용이 큰 경우, 해시 값도 같이 저장하여 해시 값을 먼저 비교하는 방식으로 비교 연산 비용을 줄이기도 한다.

리해싱(rehashing)

• 리해싱(rehashing)은 해시 테이블의 크기를 증가시키고, 기존의 모든 데이터를 새로운 테이블에 재배치하는 과정을 말한다.
• 해시 테이블의 크기가 한계에 도달하거나, 충돌이 너무 많이 발생하여 성능 저하가 우려되는 경우에 리해싱 작업을 진행한다.
• 리해싱은 모든 데이터를 재배치하므로 O(N)의 시간이 소요된다.

---

연관 컨테이너 사용 정리

• set : 해당 키 값이 존재하는지만 궁금한 경우
• map : 키에 대응하는 값을 저장하고 싶은 경우
• multiset / multimap : set / map에서 중복 키값을 허용하는 경우
• unordered_set / unordered_map : 정렬이 필요 없고, 저장되는 데이터가 100만 개 이상 되어 최적화가 필요한 경우.

---

참고 자료

https://www.scaler.com/topics/cpp/map-in-cpp/

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94

https://en.cppreference.com/w/cpp/container

https://modoocode.com/224