[c++] unordered_set / unordered_map

대부분의 STL 컨테이너들은 레드블랙 트리 기반으로 되어있다고 합니다. ㅇ0ㅇ

 

unordered_set

정렬되지 않은 set

 

해시함수를 이용하여 원소를 탐색합니다. 고로 정렬될 필요가 없습니다.

 

해시함수 : 해시함수 값이 같은 값이 나오면 같은 상자에 저장됩니다. 다른 원소 값이 우연히 같은 해시함수 값이 나와서 같은 상자에 저장된다면 해시충돌이 일어날 수 있습니다.

 

해시함수 값을 받아 바로 주소로 찾아가면 되므로 탐색 시간은 O(1) 이지만, 최악의 경우 모든 원소가 같은 곳에 저장되면 O(N) 의 시간이 발생할 수 있습니다.

 

set 과의 차이점

set 은 정렬되었기 때문에 평균, 최악의 상황 모두 O(log N) 의 탐색시간을 가집니다. 

 

원소의 개수가 적을 땐 unordered_set

원소의 개수가 많을 땐 set

 

https://www.cplusplus.com/reference/unordered_set/unordered_set/

unordered_set - C++ Reference

 

생성 방법 (5가지)

// constructing unordered_sets
#include <iostream>
#include <string>
#include <unordered_set>

template<class T>
T cmerge (T a, T b) { T t(a); t.insert(b.begin(),b.end()); return t; }

int main ()
{
  std::unordered_set<std::string> first;                                // empty
  std::unordered_set<std::string> second ( {"red","green","blue"} );    // init list
  std::unordered_set<std::string> third ( {"orange","pink","yellow"} ); // init list
  std::unordered_set<std::string> fourth ( second );                    // copy
  std::unordered_set<std::string> fifth ( cmerge(third,fourth) );       // move
  std::unordered_set<std::string> sixth ( fifth.begin(), fifth.end() ); // range

  std::cout << "sixth contains:";
  for (const std::string& x: sixth) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

여기서 알아둘 것!

unordered_set<int> s(nums.begin(), nums.end());

다른 배열, 벡터에서 바로 선언이 가능합니다.

 

 

 

 

unordered_map

정렬되지 않은 map

 

unordered_map은 hash_table 기반의 hash container

충분한 hash_table의 크기만 있다면 데이터 양이 많아지더라도 Search / insert / Delete 성능을 보장합니다.

 

find(key)

해당 키에 해당하는 원소의 반복자를 리턴합니다.

못찾으면 end() 리턴

 

주의사항 : [] 로 맵에 없는 key를 참조하면 원소를 추가해버립니다.

 

Key에 따른 개수를 저장할 때는 map[Key]++ 가 가능합니다.

 

 

map과의 차이점

map 도 정렬된 상태에서 탐색하므로 탐색시간은 O(log N)

 

unordered_map = hash map 도 해시함수로 탐색하므로 평균 O(1) 상수 시간, 최악의 경우 O(n) 이 걸린다.

 

원소의 개수가 적을 땐 unordered_map

원소의 개수가 많을 땐 map

 

 

https://www.cplusplus.com/reference/unordered_map/unordered_map/

unordered_map - C++ Reference

생성 방법 (5가지)

// constructing unordered_maps
#include <iostream>
#include <string>
#include <unordered_map>

typedef std::unordered_map<std::string,std::string> stringmap;

stringmap merge (stringmap a,stringmap b) {
  stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
}

int main ()
{
  stringmap first;                              // empty
  stringmap second ( {{"apple","red"},{"lemon","yellow"}} );       // init list
  stringmap third ( {{"orange","orange"},{"strawberry","red"}} );  // init list
  stringmap fourth (second);                    // copy
  stringmap fifth (merge(third,fourth));        // move
  stringmap sixth (fifth.begin(),fifth.end());  // range

  std::cout << "sixth contains:";
  for (auto& x: sixth) std::cout << " " << x.first << ":" << x.second;
  std::cout << std::endl;

  return 0;
}

여기서 알아둘 것

unordered_map<int, int> m(arr.begin(), arr.end());

다른 배열, 벡터에서 바로 선언이 가능하다.

 

 

원소의 추가, 수정 방법

map<string, int> map;
map["밥"] = 5;

insert를 사용하면 기존 키가 있을 때 insert가 무시됩니다.