C++ STL 정렬되지 않은 셋과 맵

unordered_set 과 unordered_map 은 C++ 11 에 추가된 비교적 최근 나온 컨테이너들 입니다.

 

이 두 개의 컨테이너는 이름에서도 알 수 있듯이 원소들이 정렬되어 있지 않습니다.

 

이 말이 무슨 말이냐면, 셋이나 맵의 경우 원소들이 순서대로 정렬되어서 내부에 저장되지만, unordered_set 과 unordered_map 의 경우 원소들이 순서대로 정렬되서 들어가지 않는다는 뜻입니다. 따라서 반복자로 원소들을 하나씩 출력해보면 거의 랜덤한 순서로 나오는 것을 볼 수 있습니다.

 

#include <iostream>

#include <string>

#include <unordered_set>

using namespace std;

template <typename K>

void print_unordered_set(const unordered_set<K>& m) {

  // 셋의 모든 원소들을 출력하기

  for (const auto& elem : m) {

    cout << elem << endl;

  }

}

int main() {

  unordered_set<string> s;

  s.insert("hi");

  s.insert("my");

  s.insert("name");

  s.insert("is");

  s.insert("psi");

  s.insert("welcome");

  s.insert("to");

  s.insert("c++");

  print_unordered_set(s);

}

 

 

 

그렇다면 여러분이 만든 클래스를 직접 unordered_set 혹은 unordered_map 에 넣으려면 어떻게 해야 할까요?

안타깝게도 셋이나 맵에 넣는것 보다 훨씬 어렵습니다.

왜냐하면 먼저 내 클래스의 객체를 위한 '해시 함수'를 직접 만들어줘야 하기 때문입니다.

(그렇기 때문에 셋과 맵을 사용하는 것을 권장하는 것입니다!)

 

물론 셋이나 맵 과는 다르게 순서대로 정렬하지 않기 때문에 operator< 는 필요하지 않습니다.

하지만 operator== 는 필요한데, 왜냐하면 해시 충돌 발생 시에 상자안에 있는 원소들과 비교를 해야하기 때문이지요.

한 가지 다행인 점은 C++ 에서 기본적인 타입들에 대한 해시 함수들을 제공하고 있습니다.

우리는 이들을 잘만 이용하기만 하면 됩니다.