std::unordered_set, std::unordered_map으로 hashing 효과 구현하기

C++에서는 std::unordered_set과 std::unordered_map 컨테이너를 사용해 효율적으로 해시 기반 자료구조를 구현할 수 있다. 이 컨테이너들은 내부적으로 해시 테이블을 사용하므로 평균적인 삽입, 삭제, 검색 연산의 시간복잡도가 O(1)로 매우 효율적이다. (하지만 해시 충돌이 많아질 경우 최악의 경우 O(n)이 될 수도 있다)

반면, std::set과 std::map은 내부적으로 균형 이진 탐색 트리로 구현되어 삽입, 삭제, 검색 연산이 O(log n)의 시간복잡도를 가지며, 요소들이 항상 정렬된 상태로 저장된다.

따라서, 정렬이 필요하지 않은 경우에는 unordered 컨테이너를 사용하는 것이 더 효율적이며, 정렬이 필요한 경우에는 set이나 map을 사용하는 것이 적합하다.

이번 포스팅에서는 unordered_set과 unordered_map을 활용하는 방법들에 대해 정리하려고 한다.

std::unordered_set

• 선언하기

  	unordered_set<string> words;

• 값 삽입하기

  words.insert("car");
   words.insert("radio");
   words.insert("orange");
   words.insert("ear");
  
   string word = "radio";
  

• 중복 데이터가 있는지 확인해보자

    if (words.find(word) != words.end()) 
   	 cout << word << " is used!" << endl;
    else 
       cout << word << " is NOT used!" << endl;
  

• vector를 unordered_set에 삽입하고 중복을 제외한 데이터 개수 구하기

  • 내가 시도한 방법

    vector<int> numbers {1, 5, 3, 1, 5, 7, 4, 5, 6, 3, 2, 7, 3, 6, 2};
    unordered_set<int> numbers_set;
    for (int i : numbers) {
    	numbers_set.insert(i);  
    }
    for (int i : numbers_set) {
    	if (numbers_set.find(i) != numbers_set.end()) {
    		count += 1;
      }
    }

  • 생성자를 활용해서 vector의 처음과 시작을 가져오는 방식으로 삽입할 수 있다.

    unordered_set<int> numbers_set(numbers.begin(), numbers.end());
    cout << numbers_set.size() << endl;

    훨씬 간단하게 구현할 수 있었다!
    

std::unordered_map

기존 map 과 사용법이 거의 유사하다. 다만 수행될 때의 시간복잡도가 O(1)이라는점!

• header 파일 추가

  #include <unordered_map>

• 선언하기

  unordered_map<string, int> fruits;

• 값 삽입

  fruits.insert({"banana", 1500});
  fruits.insert({"watermelon", 4000});

  map의 경우 Key, Value 쌍으로 타입을 선언하고 값을 추가할 수 있다. (Swift의 딕셔너리와 매우 유사한 듯하다. 딕셔너리 또한 해시를 이용해 구현된 자료구조이니 시간복잡도 또한 비슷하다.)

• 각 key값과 value 값 순회하고 값에 접근하기

  for (const auto& p : fruits) 
    cout << p.first << " is " << p.second << " won." << endl;

• 삭제하기

  fruits.erase("orange");

• value 변경하기 (Swift와 사용법이 거의 동일하다)

  fruits["apple"] = 3000;

• C++ 17 이상의 최신문법에서는 이름을 지정하고 그 이름으로 접근하는 것 또한 가능하다.

  for (auto [name, price] : fruits)
    cout << name << " is " << price << " won. " << endl;