c++ set,map,unorded_set,unordered_map 정리

set, map은 트리 구조여서 O(log(n))으로 remove,insertion,access가 가능하다.

또한 sorted 되어 있다.

그리고 별도로 comparision operator를 정의해야 한다.

 

unordered_set, unordered_map은 hash를 사용하여 O(1)로 가능하다.

이름과 같이 unordered이기 때문에 sort는 불가능하다.

그러나 사이즈가 커지면 O(n)의 복잡도로 rehashing이 일어날 수 있다.

이를 방지하기 위해서 reserve로 메모리를 미리 확보해야 한다.

 

또한 ==operator와 hashing 구조체를 별도로 구현해야 한다.

 

그리고 unoredred_map의 코드를 첨부한다.

 

set과 unordered_set은 Key만 고려하면 되고

map과 unordered_map은 Key-Value 관계를 고려해야 한다.

또한 중복을 허용하는 multiset, multimap도 있다.

 

코드 >>

#include <iostream>
#include <string>
#include <unordered_map>
 
 
int main()
{
    // unorder_map은 time complexity가 O(1)이다.
    //std::unordered_map<int, std::string> idNames;
    std::unordered_multimap<int, std::string> idNames; // 중복 허용
    idNames.emplace(1, "nocope");
    idNames.emplace(2, "kitty");
    idNames.emplace(3, "nabi");
    idNames.emplace(1, "bingo"); // 충돌
    //idNames[1] = "bingo";
    //std::cout << idNames[100] << std::endl;
    for (const auto& idname : idNames)
    {
        std::cout << idname.first << " " << idname.second << std::endl;
    }
    
    return 0;
}