C++의 std::map을 사용할 때 이 사실을 몰라 한참동안 삽질에 빠진 사람들을 많이 보았다.
C++의 STL을 사용해본 사람이라면 99%는 map을 사용해봤을 것이다. 하지만 모두가 그 기능을 정확히 알고 사용하지는 않는다.
그렇기 때문에 모두가 한 번 쯤은 당하기 쉬운 사실에 대해서 설명해보고자 한다.
문제의 원인을 찾아보자
우선 아래의 코드와 실행 결과를 보고 문제의 원인을 찾아보자.
#include <bits/stdc++.h>
int main() {
std::map<int, int> mp_test;
mp_test.insert({2, 2});
if (mp_test[1]) {
std::cout << "The value of Key 1 is: " << mp_test[1] << '\\n';
}
mp_test.insert({1, 1});
for (auto each : mp_test) {
std::cout << each.first << " : " << each.second << '\\n';
}
return 0;
}
C++
복사
분명 맵에 Key 1을 가지는 요소가 있는지 체크하고 이후 바로 insert()로 value에 1을 넣었다. 하지만 마지막에 맵에 저장된 모든 요소를 순회해보니 key 1에 value 0이 저장되어 출력되었다.
대체 무슨 일이 일어난걸까?
std::map::operator[]의 비밀
사실.. map의 인덱스 참조 연산자는 놓치기 쉬운 비밀이 숨겨져 있다.
바로, 참조하는 순간 해당 key와 value가 없다면 만들어서 추가해버리는 것이다.
이는 cppreference와 cplusplus 문서에서도 잘 나타나있다.
이는 실제 gcc 코드를 통해서도 파악할 수 있다.
아래: gcc map의 operator[]과 insert 코드
map.operator[]에서 인자로 들어온 요소로 pair를 만들어 그대로 insert() 하는 것을 볼 수 있다.
map에서 insert의 작동 방식은 key가 unique 해야하므로 기존에 해당 key가 이미 존재한다면 새로 들어온 value로 교체하지 않고 기존 값 그대로 둔다. 그리고 기존 자료에 대한 iterator와 false로 pair로 만들어 반환한다.
이는 공식문서에서도 나타나 있다.
실제 이에 대한 rb_tree 코드는 아래와 같다.
아래: map.insert() 내부에서 사용하는 rb_tree의 insert_unique (참고로 위 gcc 코드에서 변수 t의 자료형이 rb_tree다.)
요약하면 해당 key에 대한 node를 찾고 없으면 실제 삽입과 함께 pair(interator, true)를 반환하고 아니라면 기존 iterator로 value에 false를 반환한다.
이와 같은게 왜 문제가 될 수 있냐하면 인덱스로 참조 후에 값이 없는 줄 알고 insert() 연산자로 원하는 값을 넣었지만 그 값이 들어가지 않는 상황이 있을 수 있기 때문이다.
map의 인덱스 연산자와 insert의 내부 작동 방식을 제대로 알지 못한다면 디버깅하다가 허송세월을 보낼 가능성이 농후하다.
Map의 요소를 안전하게 참조하는 방법
어쨌든 map 인덱스 참조의 비밀을 알았으니 인덱스를 써서 실제 요소를 탐색할 때 주의해야한다는 것을 알았을 것이다.
그러면 어떻게 주의해서 탐색할지 대표적인 예 2가지 정도를 알아보자.
1. value의 기본값을 이용
사실 이 경우는 그닥 추천하는 방법은 아닌데 가능하므로 소개한다.
인덱스로 참조할 경우 기존 값이 없으면 value 생성자의 기본값으로 저장된다.
int나 long long 같은 정수형일 경우 0이 기본값으로 설정되고 string은 빈문자열이 저장된다.
즉, value가 정수형일 경우 0인지 확인거나 value가 string일 경우 ""와 같은 빈문자열인지 확인할 수 있다면 기존에 없던 값이라는 것을 알 수 있다.
다만 이후에 주의해야하는 점은 실제로 원하는 값을 넣을 때 더 이상 insert를 쓰면 안 된다는 것이다. insert는 기존에 해당 key 값이 저장되어 있다면 새로 들어온 값을 저장하지 않으니까 말이다.
이 때는 다시 인덱스 연산자로 실제 저장된 값을 레퍼런스로 받아와서 대입 연산자를 통해 저장해야한다.
#include <bits/stdc++.h>
int main() {
std::map<int, int> mp_test;
mp_test.insert({2, 2});
if (mp_test[1] == 0) {
mp_test[1] = 1;
}
for (auto each : mp_test) {
std::cout << each.first << " : " << each.second << '\\n';
}
std::map<int, std::string> mpstr_test;
mpstr_test.insert({2, "string2"});
if (mpstr_test[1] == "") {
mpstr_test[1] = "string1";
}
for (auto each : mpstr_test) {
std::cout << each.first << " : " << each.second << '\\n';
}
return 0;
}
C++
복사
하지만 이 방법은 value에 0을 쓰지 않는 상황에만 쓸 수 있으므로 활용에 제약이 있다.
또한 이후 코드를 읽었을 때 다른 의도로 파악할 수 있으므로 추천하지는 않는다.
2. find() 이용
이 방법이 본래 의도에 적절하고 이후 코드를 읽을 때도 바로 의미를 파악할 수 있어서 유지보수에 용이하다고 생각한다.
#include <bits/stdc++.h>
int main() {
std::map<int, int> mp_test;
mp_test.insert({2, 2});
if (mp_test.find(1) == mp_test.end()) {
mp_test.insert({1, 1});
// or
// mp_test[1] = 1;
}
for (auto each : mp_test) {
std::cout << each.first << " : " << each.second << '\\n';
}
std::map<int, std::string> mpstr_test;
mpstr_test.insert({2, "string2"});
if (mpstr_test.find(1) == mpstr_test.end()) {
mpstr_test[1] = "string1";
// or
// mpstr_test.insert({1, "string1"});
}
for (auto each : mpstr_test) {
std::cout << each.first << " : " << each.second << '\\n';
}
return 0;
}
C++
복사
이 때는 insert()와 인덱스 연산자 둘 다 이용해서 원하는 값을 대입할 수 있다.
마무리
STL map 에서 요소를 탐색할 때, 인덱스와 insert()를 쓸 때 유의해야하는 부분에 대해서 알아보았다.
이 부분은 공식문서에도 적혀있으므로 실제 라이브러리 코드를 뜯어보지 않아도 인지할 수 있는 부분이다.
하지만 많은 이들이 그렇듯 읽기만 해서는 실제 활용할 때 그 사실을 망각하기 쉽다.
필자는 C++로 알고리즘 문제를 풀면서 이 사실을 계속 상기하기도 했지만 실제 STL의 map을 구현하면서도 이 사실을 인지하고 체화할 수 있었다.
그러므로 무조건 해야하는 상황이 아니더라도 자신만의 STL을 한 번 쯤은 구현해보길 추천한다. ㅎㅎㅎㅎ
