C++ 자료구조 - unordered map(hash map)

unordered map(hash map)

map과 비슷하지만 정렬이 되어있지 않다.

insert, erase, find 모두가 O(1)O(1) 으로 수행된다

셋이나 맵의 경우 O(log n)O(logn) 이었지만, unordered_set 과 unordered_map 의 경우 상수 시간에 원소를 삽입하고, 검색할 수 있다.

원소의 key 값(데이터형)을 hash function을 통해 생성한다.(대부분 정수값)

다른 원소이지만 같은 해시값을 가질 수 있다(해시 충돌(hash collision))

 

1. 사용

- #include<unordered_map>

- unordered_map<[data type], [data type]> [변수이름]

 

2. 생성자와 연산자(int로)

 - unordered_map<int, int> um;

   - 비어있는 unordered_map um을 생성

 

3. 멤버 함수

- um.at(idx);

   - idx번째 원소를 참조.

   - um[idx] 보다 속도는 느리지만, 범위를 점검하므로 안전

 

- um[idx];

   - idx번째 원소를 참조.

   - um[idx] 보다 속도는 빠르지만, 범위를 점검하지 않음

 

 

- um.clear();

   - 모든 원소 제거

 

- um.insert(make_pair(key, value));

   - key, value 삽입

 

- um.begin();

  - 첫번째 원소를 가리킴(iterator 반환)

 

- um.end();

  - 마지막 원소를 가리킴(iterator 반환)

 

- um.find(key);

  - 특정 키를 가진 원소를 찾는다

 

- um.count(key);

  - 특정 키를 가진 원소의 개수

 

- um.size();

   - 원소의 갯수를 리턴

 

- um.empty();

  - 현재 컨테이너가 비어있는지 확인

 

- um2.swap(um1)

  - um1과 um2의 원소와 capacity 바꿔줌

 

- um.erase(key);

  - key의 원소를 제거

 

멤버변수가 많지만 기본만 작성

나머지는 아래 링크 참조

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