C++ ] Hash - unordered_map

Hash란

Key-value쌍으로 데이터를 저장하는 자료구조입니다.

 

---

Unordered maps

are associative containers that store elements formed by the combination of a key value 

and a mapped value, 

and which allows for fast retrieval of individual elements based on their keys.

 

Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average).

 

 

 

💊 멤버 함수

	Member functions	definition	example
-	-	-	#include <unordered_map> unordered_map<string, int>example; // unordered_map<KEY, VALUE>
capacity	empty	-	example.empty(  )? yes : no;
	size	요소 수를 계산합니다.	example.size(  );
Iterators	begin	처음에 대한 반복자를 return합니다.	example.begin(  );
	end	last + 1의 원소를 return합니다.	example.end(  );
Element access	at	지정된 키 값이 있는 요소에 접근합니다.	example = {  {"Mars" 3000} ,                   {"Jupiter", 7000}  }; example.at( "Mars" ) = 25; > example 내의 Mars의 value는 25로 바뀝니다.
Element lookup	find	Get iterator to element	example.find( "Mars" ); find 함수의 경우 만일 해당하는 원소가 존재한다면 이를 가리키는 반복자를, 없다면 end 를 리턴합니다.
	count	Count elements with a specific key (find와 동일)	example.count( "Mars" )
Modifiers	insert	Insert elements	example.insert({"three", 3}); example.insert(make_pair("four", 4));
	erase	Erase elements	example.erase( example.find( "Hi" ) ); 간단히 find 함수로 원소를 가리키는 반복자를 찾은 뒤에, 이를 전달하면 됩니다.

 

 

 

+ capacity 출력 함수 비교

size (  )	bucket_count(  )

 

 

📖 예시

1. 기본 예제

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    // Create an unordered_map of three strings (that map to strings)
    unordered_map<string, string> u = {
        {"RED","#FF0000"},
        {"GREEN","#00FF00"},
        {"BLUE","#0000FF"}
    };
 
    // Iterate and print keys and values of unordered_map
    for( const auto& n : u ) {
        cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    }
 
    // Add two new entries to the unordered_map
    u["BLACK"] = "#000000";
    u.insert({"WHITE", "#FFFFFF"});
    // or
    // u.insert(make_pair("WHITE", "#FFFFFF"));
 
    // Output values by key
    cout << "The HEX of color RED is:[" << u["RED"] << "]\n";
    cout << "The HEX of color BLACK is:[" << u["BLACK"] << "]\n";
}

 

2. 활용 예제

프로그래머스 Level 1 '완주하지 못한 선수'

코딩테스트 연습 - 완주하지 못한 선수

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    
    for(auto elem : completion)
    {
        if(strMap.end() == strMap.find(elem)) // 현재 맵에 elem 값이 없다면
            strMap.insert(make_pair(elem, 1));
            // make_pair(변수1, 변수2) : 변수1과 변수2가 들어간 pair 생성
        else
            strMap[elem]++;
    }

    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem))
        {
            answer = elem;
            break;
        }
        else
        {
            strMap[elem]--;
            if(strMap[elem] < 0)
            {
                answer = elem;
                break;
            }
        }
    }
    return answer;
}

 

프로그래머스 Level 2 '전화번호 목록'

코딩테스트 연습 - 전화번호 목록

 

---

reference

unordered_map - C++ Reference

unordered_map 클래스