C++ STL 프로그래밍(맵)

8. 맵(map)



8.1 map의 자료구조
    - 트리(tree) 구조중 하나인 레드-블랙 트리(Red-Black tree)
        
        * 용어 설명
            - 루트 노드(root node) : 5. 최상위 노드
            - 리프 노드(leaf node) : 9, 30, 35, 20. 자식노드가 없는 노드
            - 부모 노드(parent node) : 상하 관계의 두 노드 중 위쪽 노드
            - 자식 노드(child node) : 상하 관계의 두 노드 중 아래쪽 노드


8.2 트리 자료구조의 특징
    - 트리는 노드를 균형 있게 가지는 것이 성능에 유리
    - B-트리, B+트리, R-트리, 레드 블랙 트리, AVL트리 등 트리 자료구조 다양
    - 균형을 이루는 트리는 자료를 정해진 방식에 따라 분류 저장하므로 시퀀스 컨테이너보다 검색이 빠름
    - 규칙때문에 삽입, 삭제가 쉽지않고 구현이 복잡


8.3 map을 언제 사용해야 될까?
    1) 정렬 필요
    2) 많은 자료 저장, 검색이 빨라야 할 때
    3) 삽입, 삭제가 적을 떄


8.4 map 사용방법
    - 헤더파일 포함 : #include <map>
    - 선언 : map<key 자료형, value 자료형> 변수이름;
    - key를 대상으로 오름차순으로 정렬
    - 내림 차순 정렬 선언 : map<key 자료형, value 자료형, 비교함수> 변수이름;
          예시) map<string, int, greater<int>> 변수이름;
          주의) 비교함수를 사용하였다면 iterator 선언 시 동일하게 선언 해줘야 한다.
                
    - 동적할당 선언 가능

    8.4.1 map의 주요 멤버들
        - operator[] 가 있다는걸 눈여겨 보자
        

        * map는 키 값의 중복을 허락하지 않으므로 아래와 같은 방법으로 확인
           
            - 이미 키 값 1이 있으면 insert 실패로 Result.second는 false, 성공은 true

        * operator[] 를 사용하여 추가(편리성 굳)
            

    8.4.4 검색, 삭제 들은 위 hash_map와 동일