[코딩테스트] map

1. map

맵은 key-value 구조를 갖는 컨테이너이다. 키와 값의 쌍을 entry라고 하며 STL에서 std::pair 타입으로 표현한다. 내부는 균형이진탐색트리(레드블랙트리) 방식으로 동작하기 때문에 중복되지 않은 key 값을 기준으로 데이터가 자동 정렬된다.

검색, 삽입, 삭제하는데 시간복잡도는 O(logN)이다.

#include <map>

// 선언
map<string, int> myMap;

// 초기화
map<string, int> myMaps = {
    { "Meoyoung", 25 }
};

 

(1) 데이터 접근

myMap["Meoyoung"];       // [] 연산자
myMap.find("Meoyoung");  // find() 메서드

// 반복문 기반
for(auto it = myMap.begin(); it != myMap.end(); ++it)
{
    cout << it->first << " " << it->second << endl;
}

// 범위 기반
for(auto it : myMap)
{
    cout << it.first << " " << it.second << endl;
}

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

- [ ] 연산자의 경우 주의할 점이 있는데, 맵에 없는 키에 접근하려고 하면 오류가 발생하는 것이 아니라 새로운 키가 만들어진다.

- 키가 없는 상태를 유지하고자 할 때에는 find( ) 메서드를 활용하는 것이 적합하다.

- 반복문 기반에서 auto는 map<Key, Value>::iterator 타입이고, 범위 기반에서 auto는 pair<Key, Value> 타입이다. 따라서, 반복문 기반에서의 요소는 "->"를 사용해야 하며, 범위 기반에서의 요소는 "."을 사용해야 한다.

- 범위 기반에서 auto와 auto& 모두 사용이 가능하다. auto를 사용할 경우 myMap의 요소를 복사해서 it에 가져오는 것이고, auto&를 사용할 경우 myMap의 요소를 참조하여 it에 가져오는 것이다. 참조하여 사용하는 것이 성능적으로 우수하니, auto보다 auto&를 사용하는 것을 습관화하자.

 

(2) 값 변경

myMap["Meoyoung"] = 10;

[ ] 연산자로 간단하게 값을 변경하면 된다.

 

(3) 삽입

myMap.insert(make_pair("Meoyoung", 25));
myMap.insert({"Meoyoung", 25});
myMap["Meoyoung"] = 25;

어떻게보면 [ ] 연산자가 만능처럼 느껴지는데, 코드의 가독성을 위해 각각의 상황에 맞게 만들어진 메서드를 활용하는 것이 좋다.

 

(4) 삭제

myMap.erase("Meoyoung");

auto it = myMap.find("Meoyoung");
myMap.erase(it);

erase의 인자값으로 해당 키를 넘겨주거나, find를 통해 얻은 iterator를 넘겨주어도 된다.

 

myMap.clear();

myMap의 모든 원소를 삭제한다.

---

2. multimap

multimap은 key 값의 중복을 허용하는 map이라고 보면 된다.

 

(1) 동일한 키 접근

#include <map>

multimap<string, int> myMap = {
    { "Meoyoung", 25 },
    { "Meoyoung", 20 },
    { "Seongkyu", 25 },
    { "Sejin", 25 }
    };
    
auto range = myMap.equal_range("Meoyoung");
// auto& range = myMap.equal_range("Meoyoung") 은 불가

for(auto it = range.first; it != range.second; ++it)
{
    cout << it->first << " " << it->second << endl;
}

range의 타입은 pair<iterator, iterator>이다. 따라서, range.first, range.second로 각각의 iterator에 접근이 가능하다.

 

그렇다면 auto& range로 pair<iterator, iterator>를 참조할 수도 있겠지만, 위의 경우에서는 불가능하다. 그 이유는 lvalue, rvalue의 차이를 알아야 한다. myMap.equal_range( )는 rvalue에 해당한다. 즉, 임시객체에 해당하므로 참조를 할 수가 없다. 실제로 auto& range로 코드를 작성해보면, "cannot bind to a temporary of type pair<...>"이라는 오류메세지가 출력된다. 임시객체가 왜 참조가 불가능한지는 더 깊게 들어가야하니 생략하겠다.

 

range.first는 lower_bound로, myMap의 key 값중에 인자 값 이상의 값이 처음 등장하는 위치를 가리킨다.

range.second는 upper_bound로, myMap의 key 값중에 인자 값을 초과하는 값이 처음 등장하는 위치를 가리킨다.

인자 값이 myMap에 존재하지 않는 경우, range.first, range.second 모두 myMap.end( )를 가리킨다.

 

쉽게 말해, range.first는 myMap의 key 값중에 "Meoyoung"과 동일하거나 큰 값이 처음 등장하는 위치에 해당하므로 Meoyoung이 처음 등장하는 위치인 { "Meoyoung", 25 }에 해당한다.

range.second는 "Meoyoung"을 초과하는 값이 처음 등장하는 위치에 해당하므로 Meoyoung을 초과하는 값이 처음 등장하는 위치인 { "Seongkyu", 25 }에 해당한다.