1. 개요

vector만큼이나 많이 쓰이는 type이 map이다.

map은 해쉬나, adjacency list/ matrix 등의 자료 형을 표현하기 위해 사용된다.
python으로 따지면 dict과 같은 역할을 한다.
다른 점은 map은 tree 구조이다.

---

1-1 std::map vs std::unordered_map

unordered_map과 hash_map을 거의 동일하게 보면 이런 차이점이 있다.

	std::map	std::unordered_map
탐색 시간 복잡도	$O(\log(N))$	$O(1)$
key 값 정렬 여부	O	X

#include <iostream>
#include <map>
#include <unordered_map>

int main(){
    std::map<std::string, int> mapping{
        {"BBBB", 2},
        {"AAA", 1},
        {"1", 0},
        {"CC", 3}
    };
    std::unordered_map<std::string, int> unordered_mapping{
        {"BBBB", 2},
        {"AAA", 1},
        {"CC", 3}
    };

    std::cout << "_____________" << std::endl;
    std::cout << "     map" << std::endl;
    std::cout << " Key: value" << std::endl;
    for(auto it: mapping){
        std::cout << it.first << ": " << it.second << std::endl; 
    }

    std::cout << "_____________" << std::endl;
    std::cout << "unordered map" << std::endl;
    std::cout << " Key: value" << std::endl;
    for(auto it: unordered_mapping){
        std::cout << it.first << ": " << it.second << std::endl; 
    }

    return 0;
}

위 예시 코드를 보면 map은 key 값이 사전 순으로 정리됐음을 알 수 있다.

---

1-2 std::map 과 std::pair

std::map의 각 원소는 std::pair로 이루어졌다.
std::pair는 다음과 같이 선언될 수 있다.

std::pair<T1, T2> pairName;

위 예시 코드에서는 암묵적으로 mapping 속에 각 원소가 std::pair<std::string, int>로 이루어져있다.

std::map을 선언할 때, std::pair를 중괄호(braces) {}로 묶고,
std::pair의 원소는 또다시 중괄호로 묶인다.

range-base-for 문으로 출력할 때 std::pair의 특성이 가장 잘 나타난다.

	for(auto it: mapping){
    	std::cout << it.first << ": " << it.second << std::endl;
    }

중괄호로 묶인 모습과 다르게 std::pair는 index로 접근하는 것이 아닌, member인 .first, .second로 접근한다.

---

2. .insert()

2-1 map.insert({key, value}), map[key]=value 공통점

std::map은 [] 연산자로 key-value 쌍을 추가할 수 있다.

#include <iostream>
#include <map>

int main(){
    std::map<std::string, int> mapping{
        {"BBBB", 2},
        {"AAA", 1},
        {"CC", 3}
    };
    std::cout << "---------------" << std::endl;
    std::cout << "before add pair" << std::endl;
    for(auto it: mapping){
        std::cout << it.first << " : " << it.second << std::endl;
    }
    std::cout << "---------------" << std::endl;
    std::cout << std::endl;

    mapping["DDD"] = 4;
    
    std::cout << "---------------" << std::endl;
    std::cout << "after add pair" << std::endl;
    for(auto it: mapping){
        std::cout << it.first << " : " << it.second << std::endl;
    }
    std::cout << "---------------" << std::endl;

    return 0;
}

mapping["DDD"] = 4; 라인에서 []연산자 속에 key 값을, = 연산자 오른쪽에 value 값을 넣으면 된다.

이런 연산은 .insert() method로도 할 수 있다.

mapping.insert({"DDD", 4});

[] 사용과 다른 점은 직접 pair로 묶어 집어 넣는 것이다.
그 차이를 코드와 같이 살펴보자.

---

2-2 map.insert({key, value}), map[key]=value 차이점

다음은 mapping.insert({"AAA", 5});로 실행한 결과이다.

"AAA"에 해당하는 value 값이 바뀌지 않았다.

반면, mapping["AAA"] = 5;로 실행하면 다음과 같은 결과를 얻는다.

"AAA"에 해당하는 value 값이 달라졌다.

이런 현상은 std::map은 key-value 쌍을 하나만 허용하기 때문이다.

mapping.insert({"AAA", 5});는 쌍을 만들고 이를 집어넣는다.
"AAA"를 key로 갖는 쌍은 이미 존재하기 때문에 .insert 동작이 이루어지지 않는다.

반면, mapping["AAA"] = 5;는 "AAA"의 value에 접근해서 5를 대입하므로 동작이 이루어진다.
value에 접근하는 말 그대로 "key"인 셈이다.
따라서 mapping["AAA"]++;와 같은 동작도 가능하다.
이렇게 말이다.

"AAA"의 value가 1에서 2로 ++ 됐다.

---

3. .erase()

std::map에서 .erase()는 std::vector와는 조금 다르게 동작한다.

---

3-1 key 접근

std::map은 key-value 쌍으로 이루어지고 key를 이용해 접근하는만큼, key가 중심이 돼서 연산이 이루어진다.

만약 다음과 같이 initialize했다고 가정하자.
ID-PW 쌍이다.

    std::map<std::string, std::string> id_password{
        {"BBBB", "11bb"},
        {"AAA", "222aaa"},
        {"CC", "3c"}
    };

여기서 "BBBB"에 해당하는 쌍은 다음과 같이 지울 수 있다.

id_password.erase("BBBB");

---

3-2 iterator 접근

만약 다음과 같이 initialize했다고 가정하자.
문자열-정수 쌍이다.

    std::map<std::string, int> mapping{
        {"BBBB", 1},
        {"AAA", 2},
        {"CC", 3}
    };

여기서 홀수 value 쌍은 다음과 같이 지울 수 있다.

    for(auto it=mapping.begin(); it!=mapping.end();){
        if(it->second%2 == 1){
            it = mapping.erase(it);
        }
        else{
            it++;
        }
    }

반면, 다음 코드는 다르게 동작한다.

    for(auto it=mapping.begin(); it!=mapping.end(); it++){
        if(it->second%2 == 1){
            it = mapping.erase(it);
        }
    }

{"BBBB", 1}를 만나 .erase가 되면 it++되고 나서 바로 it이 mapping.end()가 되기 때문이다.
그래서 {"CC", 3}는 건너뛴다.

처음 cppreference에서 .erase() 예시 코드를 봤을 때 '왜 저렇게 이상하게 짜지?' 싶었는데, 이런 이유였다.

cppreference erase 예시

---

4. .find()

아마 std::map 메소드 중 가장 많이 사용하지 않을까 싶다.
만약 다음과 같은 std::map에서 "CC"와 "DDDDD"를 찾는다고 가정하자.

    std::map<std::string, int> mapping{
        {"BBBB", 1},
        {"AAA", 2},
        {"CC", 3}
    };

mapping.find(key 값)은 iterator를 반환한다.
찾으면 해당 iterator를, 못 찾으면 .end()를 반환한다.

#include <iostream>
#include <map>

int main(){
    std::map<std::string, int> mapping{
        {"BBBB", 1},
        {"AAA", 2},
        {"CC", 3}
    };

    std::cout << "------------" << std::endl;
    for(auto it: mapping){
        std::cout << it.first << " : " << it.second << std::endl;
    }
    std::cout << "------------" << std::endl;
    std::cout << std::endl;

    std::cout << "------------" << std::endl;
    std::cout << "Find \"CC\"" << std::endl;
    auto it = mapping.find("CC");
    if(it != mapping.end()){
        std::cout << "Found " << it->first << " : " << it->second << std::endl;
    }
    else{
        std::cout << "Not Found" << std::endl;
    }
    std::cout << "------------" << std::endl;

    return 0;
}

이번에는 auto it = mapping.find("DDDDD");로 바꿔준다면 다음과 같이 나온다.

---

다음 포스팅은 <iterator>와 stream과 관련될 예정이다.