[C/C++]STL 컨테이너 - std::map/std::set 그리고 std::deque

이 글은 이전에 운영하던 깃 블로그에서 옮겨온 글입니다.

 

서론

이전 글인 [C/C++]STL 컨테이너 - std::vector 와 std::list 에 이어지는 글입니다. 이번 글에서는 std::map과 std::set 그리고 std::deque에 대해서 알아보겠습니다.

---

std::map과 std::set

위의 두 컨테이너는 기능상으로는 매우 유사하기에 같이 다루겠습니다. 차이라고 한다면 map은 key와 그 키의 값에 해당하는 value가 함께 저장되고, set은 key값만 저장되는 구조입니다. 간단한 특징들은 다음과 같습니다.

map

• 레드 - 블랙 트리 기반
• Key값과 데이터를 한쌍의 원소로 관리하는 컨테이너
• Key값의 중복을 허용하지 않음 (multmap의 경우 key 부분의 중복을 허용함)
• Key값은 int 이외에 다른 타입을 가질 수 있음
• 연관 배열처럼 사용됨

set

• 연관 컨테이너, 균형 바이너리 트리구조로 양방향 반복자를 가짐
• 레드 - 블랙 트리 기반
• Key만을 저장, 중복을 허용하지 않음 (multset의 경우 중복을 허용함)
• 원소 값 변경을 권하지 않음
  => 연관 컨테이너인 set은 원소가 정렬된 상태이기 때문에 원소 값 자체를 바꾼다는 것은 규칙을 깨는 행위
• 정렬 알고리즘 등 랜덤 액세스를 요구하는 알고리즘을 사용할 수 없다
• 삽입시 자동으로 정렬된 상태가 됨 (기본 정렬자 : less, 내림 차순)
• 삽입 성공 여부가 pair로 반환됨 (first : 값 위치의 반복자 / second : bool 성공 여부)

여담으로 std::set과 std::map의 삽입 삭제가 빈번하면 좋지 않은 이유는 O(logN)의 시간 복잡도를 가지지만, 레드-블랙 트리의 구조를 내포하고 있기에 밸런싱(트리의 균형을 유지하는 작업)을 삽입과 삭제 시 수행하기 때문이다.

 

특징에서 볼 수 있듯이, 큰 차이는 없습니다. 사실 std::map과 std::set의 차이보다는 std::map과 std::hash_map의 차이에 대해서 많이 물어봤던 것 같네요.

---

std::hash_map

 

std::map과 std::set 차이에서 마지막에 언급했던 std::hash_map 에 관하여 간단히 알아보고 가겠습니다.

 

std::hash_map 역시 key와 value의 쌍을 이루는 구조입니다. 음? 같은 거 아닌가? 일단 내부에 사용된 자료구조가 다릅니다. std::hash_map은 Hash table 자료구조를 이용합니다. 즉, key값을 해쉬 함수에 대입하여 테이블의 버켓 번호를 분포시키고 이 분포가 어떠냐에 따라 성능에 영향을 받게 되는 거죠. 잘 구현된 해쉬 함수(중복 없는 고른 분포를 만들어주느냐)에서는 검색 속도가 O(1)의 시간 복잡도를 가지게 됩니다. O(logN)의 std::map보다 빠르다고 합니다.

아니 그러면 std::hash_map을 쓰는 게 좋지 않으냐 하는 의문을 가질 수 있겠네요. 저의 생각은 ‘글쎄’입니다. 일반적으로 std::hash_map을 쓰는 게 빠른 게 맞다고 생각해요. 하지만 해쉬 함수가 어떠냐에 따라 성능은 천차만별일 수 있겠죠. 이러한 이유 때문에 STL의 표준으로 등록되지도 않았다고 합니다. 사실 표준이 아니라 다루지 않으려 했지만, 많이 나오길래 다뤄 봤습니다. (물론 std::unodered_map이라고 해쉬 테이블을 사용하는 컨테이너가 표준으로 등록되어 있습니다)

결론, 뭐… 어떤 걸 사용하냐는 이것 또한 사용자의 취향이라고 생각합니다.

 

---

std::deque

• 자료구조 큐 + 스택 기반의 컨테이너
• 데이터의 삽입 삭제가 양끝에서 일어날 수 있음
• vector 컨테이너의 단점을 보안하기 위하여 여러 개의 블록을 할당하고 하나의 블록처럼 사용하는 기능 제공
• 연속된 메모리 공간이 아니어서, 원소 간들 간의 포인터 연산이 불가능함
• Capacity = Size

이것은 제가 면접 볼 때는 한 번도 안 물어봤지만, 심심치 않게 나오기도 한다기에 간단한 설명만 하겠습니다.

두 가지 자료구조의 조합이라니 재밌기는 하네요. 큐와 스택의 차이나, 이를 조합했을 때 얻게 되는 이점을 유추할 수 있는지 활용능력도 파악하기 좋아서 물어보는 게 아닐까 싶습니다.

---

결론

컨테이너를 선택할 때 자료구조에 대한 기본적인 이해와, 상황에 맞는 응용력이 필요한 것 같습니다. 잘못된 컨테이너의 선택은 성능이나 유지/보수에 좋지 않은 영향을 끼치기도 합니다. 최소한 내가 이 자료구조를 왜 채택했고, 어떤 부분이 타협이 됐는지는 알고 사용하는 게 중요합니다.