C++ STL 프로그래밍(해시 맵 hash_map)

7. 해시 맵(hash_map)



7.1 시퀀스 컨테이너와 연관 컨테이너
    - STL컨테이너는 시퀀스 컨테이너와 연관 컨테이너로 나눈다.
    - 시퀀스 컨테이너 : 순서대로 자료 보관(iterator 사용). list, vector, deque
    - 연관 컨테이너 : key와 value 짝을 이뤄 자료 보관. 탐색이 빠른 대용량 자료 저장
        


7.2 연관 컨테이너로는 무엇이 있을까?
    - 키 값이 중복되지 않을 때 사용 : map, set, hash_map, hash_set
    - 키 값이 중복될 때 사용(multi) : multi_map, multi_set, hash_multimap, hash_multiset

    7.2.1 map, set과 hash_map, hash_set 의 차이
        - map, set : 자료를 정렬해 저장하므로 탐색 시 정렬 순서대로 순회
        - hash_map, hash_set : 정렬 없이 저장. hash 자료구조를 사용해 탐색이 더 빠르다.

    7.2.2 hash_map, hash_set 은 표준이 아니다
        - 표준에 들아갈 예정이고 현업에서 매우 유용
        - 2007 에서 unordered_map, unordered_set 이름으로 사용되었다.


7.3 hash_map의 자료구조
    - '해시 테이블'. Key값 해시 함수에 대입 -> 버킷 번호 -> 버킷의 빈 슬롯에 저장
        


7.4 hash_map을 사용할 때
    - 많은자료(천 이상)를 저장하고, 검색이 빨라야 할 때
    - 자료 삽입, 삭제가 적을 때


7.5 hash_map 사용방법
    - 헤더 파일 포함 : #include <hash_map>
    - 네임스페이스 선언 : using namespace stdext;
    - 선언 : hash_map<Key 자료형, Value 자료형> 변수이름;
    - 동적할당 : hash_map<자료형, 자료형>* 변수이름 = new hash_map<자료형, 자료형>;

    7.5.1 hash_map의 주요 멤버들
        - find, lower_bound, upper_bound 가 다른 컨테이너와 다른 점
        - push_back 과 같은 추가 함수는 삭제되고insert로 추가 한다.
        


    7.5.2 추가 insert 세 가지
        


    7.5.3 삭제 erase 세 가지
        - 첫 번째, 두 번째 삭제는 삭제된 요소의 다음을 가리키는 반복자 리턴
        - 세 번째 삭제는 삭제된 개수 리턴
        


    7.5.4 검색 find 두 가지
        
        - Key와 같은 요소를 찾으면 그 요소의 반복자 리턴, 찾지 못하면 end()리턴
        - 두 방법 다 key 값은 변경 불가능(key 앞에 const가 있음을 확인하자)
        - 첫 번째는 value 값 변경 가능
        - 두 번째는 value 값 변경 불가능
            


    7.5.5 lower_bound와 upper_bound
        - key 값으로 해당 요소의 시작 위치를 얻을 때 사용하는 멤버들
        - key 값 비교는 수학적 크기가 아닌, 저장된 요소의 위치의 높이를 의미한다.

        lower_bound : 키가 있으면 해당 위치 반복자 리턴
        upper_bound : 키가 있으면 그 다음 위치 반복자 리턴
            - 저장 요소를 나누어 처리 시 유용(3000개의 캐릭 정보를 100개씩 나누어 처리)