set과 unordered_set 무엇을 선택할까?

글이 온라온 지는 꽤 지났고 그 글이 아니더라도 이미 많은 이가 알고 있는 내용이긴 하겠지만, 요즘 트윗 읽는 속력이 꽤 느린 편이라 이제 읽기도 했고 나중에라도 쉽게 참고할 수 있게 정리해 본다. 상세 내용은 Should you be using something instead of what you should use instead?에서 볼 수 있다. 제목에는 setunordered_set만 적었지만 C++ 라이브러리에서 균형 이진 트리를 사용하는 컨테이너와 해시 테이블을 사용하는 것 중 무엇을 선택하느냐로 보면 된다.

  • 요소 수가 20~50 개 미만이라면 vector에 담아 정렬하지 않고 순차 검색해도 무방.
  • 그 외엔 해시 테이블 추천. 요소 수가 많을 수록 검색 속력 차이가 크며, 균형 이진 트리를 사용하는 컨테이너에 비해 메모리도 적게 쓴다.

즉 일반적인 상황에서는 무조건 해시 테이블 쓰면 손해 볼 일 없다는 얘기다. 물론 은총알은 없으므로 생각과 다르게 느리다면 입력 값을 확인해 컨테이너를 바꾸든지 성능 분석을 해야겠지만 기본적인 지침으로 사용하기엔 충분하다.