셋/맵

• [C++] 셋/맵

  STL 연관 컨테이너(associative container)

  연관 컨테이너 (Associative Contatiner) : 키(key) - 값(value) 구조를 가지는 컨테이너로써 set, map, hash 등이 있다. 특정 키 값을 가지는 데이터가 존재하는지만 확인하고 싶을 경우 set을 사용하고, 키 값에 따른 데이터를 확인하고 싶을 경우 map을 사용하는 것이 좋다.

  set

  해당 key값을 가지는 데이터가 존재하는지 확인하기 위한 컨테이너.

  • 시간복잡도

    • 원소를 추가 및 제거 O(logN)
    • 특정 원소 찾기 O(logN)

    

  • 특징

    원소는 순서가 없으며(key로 구별하기 때문에), 중복되는 원소가 없고(key에 따른 data가 없기 때문에), 자동으로 정렬된다.

    사용자 정의 클래스를 key값으로 사용하기 위해서는 operator < 를 구현해야 한다. 그리고 다음과 같은 조건을 만족해야한다.

    • A < A 는 거짓

    • A < B != B < A

    • A < B 이고 B < C 이면 A < C

    • A == B 이면 A < B 와 B < A 둘 다 거짓

    • A == B 이고 B == C 이면 A == C

  map

  key 와 data로 구성돼있는 컨테이너

  • 시간복잡도는 레드-블랙 트리(Red-Black Tree)를 사용하므로 최선 O(n), 최악O(logn)

  • 특징

    key 값에 따라서 자동으로 정렬된다. 원소를 추가할 때 pair 타입으로 추가하거나 [] 연산자를 통해 추가/변경할 수 있다.

  multiset, multimap

  원소의 중복을 허용하기 때문에 [] 연산자를 사용할 수 없다. key값이 중복되는 원소에 find 함수를 사용할 때 어떤 값이 반환될지 알 수 없다. 이러한 단점을 극복하기 위해 begin()과 end()를 가지는 pair를 반환하는 equal_range(key) 함수를 제공한다.

  unordered_set, unordered_map

  • 정렬되지 않지만 삽입/삭제/탐색 이 O(1) 로 수행된다.

  • 해시함수(Hash function)을 사용할 때 해시 크기(메모리 크기와 비슷)가 원소의 갯수보다 적으면 다른 원소간의 해시 값이 같은 해시 충돌(Hash collision)이 발생할 수 있다. 해시 충돌이 일어날 경우 같은 해시값을 같은 원소안에서 다시 탐색해야 원하는 원소를 찾을 수 있으므로 최악의경우 O(N)의 시간복잡도가 소요된다.

  • 사용자 지정 클래스를 사용하고 싶을 경우 해시 함수를 만들어주어야한다. 기본적인 데이터 타입의 해시 함수는 C++에서 제공하므로 이를 조합해서 만들 수 있다.

    하지만 일반적으로 해시 함수가 지원되지 않는 unordered 컨테이너는 만들지 않는 것이 일반적이다.