[C++ STL] 연관 컨테이너와 셋(Set)

연관 컨테이너(associative container)란?

이전에 배운 시퀀스 컨테이너가 단순하게 순차적으로 자료를 저장하는 구조라면, 연관 컨테이너는 각 원소가 키(key) - 값(value)의 구조를 가지는 컨테이너다. 특정한 키를 넣으면 이에 대응되는 값을 돌려준다.

key - value 대응 구조

연관 컨테이너는 대표적으로 다음과 같은 작업을 수행한다.

• 특정 키가 연관 컨테이너에 존재하는가?
• 특정 키에 대응되는 값은 무엇인가?

첫 번째 작업에는 셋(set)과 멀티셋(multiset), 두 번째 작업에는 맵(map)과 멀티맵(multimap)을 사용한다.

맵의 경우 셋보다 사용하는 메모리가 많으므로 단순히 키의 존재 유무만 궁금하다면 셋을 사용하는 것이 좋다.

나머지는 차차 알아보도록 하고, 먼저 셋부터 알아보자.

---

개요

셋은 원소들을 저장하지만 원소들의 포함 여부만 중요한 정보로 생각하기 때문에 시퀀스 컨테이너와는 다르게 '어디에' 저장되는 지에 대한 정보가 없다. 

시간복잡도

• 셋은 내부적으로 트리 구조로 구성되어 있기 때문에 O(log N)의 시간 복잡도로 연산이 가능하다.
• 원소 삽입 및 제거: O(log N)
• 원소 확인: O(log N)

주요 기능 및 특징

반복자

셋에 저장되어 있는 원소들에 접근하기 위해 반복자가 제공되며, 반복자는 BidirectionalIterator 타입이다.

그렇기 때문에 순차적으로 하나씩 접근해야 한다.

정렬

셋에 들어간 원소들은 항상 정렬된 상태를 유지하고 있다.

중복

셋에는 중복된 원소가 존재하지 않는다. 만약 insert로 중복된 원소를 추가하려고 한다면, 그 작업은 무시된다.

만약 중복된 원소를 허용하고 싶다면 멀티셋을 사용하면 된다.

원소 삽입 및 제거

원소 삽입에 insert(value), 원소 제거에 erase(iterator or value)를 사용한다.

원소 찾기

find 함수를 통해 셋에 원소가 존재하는 지 확인할 수 있다. 원소가 존재하면 그 원소를 가리키는 반복자를 리턴하고, 없으면 셋.end()를 리턴한다.

참고 및 이미지 출처

모두의 코드 - 씹어먹는 C++ PDF [https://modoocode.com/312]