[자료구조] C++ STL - Map과 C++ 적인 사용에 대하여 🗺️

1. About Map

map은 제가 그리 자주 쓰는 자료구조는 아니지만, IT기업 코딩테스트 대비 과정에서 생각보다 Set과 Map의 이용이 잦았고, 정리가 필요함을 느껴 이렇게 정리하게 되었습니다. (굳이 굳이 굳이 직접 해시 함수를 만들어서 테이블을 이용하곤 했습니다.)

map은 자료를 유일한 key와 하나의 value 쌍으로 저장하는 자료구조입니다. 정확히는 각 노드가 key, value 쌍으로 이루어진 'Tree'구조를 띄고 있습니다. key와 value의 타입은 서로 다를 수 있으며, 일반 map은 key 값을 오름차순 정렬하여 저장합니다. 이는 간단한 테스트를 통해 확인 할 수 있습니다.

위와 같이 내부적으로 key를 정렬하는 것을 확인할 수 있습니다. 그래서 수행 속도가 중요시 되는 테스트의 경우에는 key를 정렬하지 않은 버젼인 unordered_map을 쓰는 경우도 많습니다. 저는 사실 코딩 테스트용 문제는 풀이만 올바르면 제한시간 보다 못 미치는 시간에 풀리도록 설계 되어 있다고 생각하기 때문에 그냥 map을 쓰는 경우가 많습니다. 참고로 C++ STL에는 key가 유일하지 않은 버젼의 map인 multimap 자료구조도 있습니다.

내부 구현은.. 찾아본 블로그마다 말이 다른데, C++ 레퍼런스에서는 일반적으로 이진검색트리로 구현한다고 합니다. 삽입, 접근, 삭제가 $Big-O$ 표기법상 $O(logN)$이 되겠습니다. 

2. 기본적인 사용법

제가 사용해본 적 있거나, 앞으로 사용할 가능성이 있어 보이는 것만 간단히 정리하겠습니다.

map<string, int> map;

모든 설명은 위와 같은 map이 선언되어 있다고 가정하고 진행하겠습니다. 원래는 map이라는 이름을 가진 map은 선언이 불가능하지만, 편의상 존재한다고 가정하겠습니다.

2.1 데이터 삽입

map.insert({"Jinho", 96});

기본적인 insert방법입니다. key값은 중복이 허용되지 않습니다. 이미 가지고 있는 key의 데이터 삽입 시도는 무시됩니다.

map["Dog"] = 3;
map["Dog"]++;

map["Pig"];
map["Cat"]++;

위와 같은 삽입이 편리합니다. "Dog"를 key로, 3을 value로 바로 insert해줄 수 있습니다. 접근 할 때도 map["Dog"]++;를 이용하면 value가 4로 늘어나게 됩니다. 또한 map["Pig"]; 처럼 insert 할 수도 있습니다. "Pig"은 넣은 적 없는 key인데 이런 식으로 바로 넣어주면 value를 0으로 갖게 됩니다. map["Cat"]++;과 같은 방식으로 "Cat"을 삽입함과 동시에 value를 1로 만들어 줄 수 있습니다.

2.2 데이터 접근

크게 key를 지정하여 접근하는 방식과, 접근할 key를 특정하지 않고 map 전체를 순회하는 접근으로 나누겠습니다.

2.2.1 인덱스 접근

단순합니다.

map["Dog"]; 

위와 같이 정확한 key값을 넣어주면 올바른 value 값을 반환합니다. 만약에 없는 key의 값을 요구하면 int의 경우 0을 반환합니다. 이는 문제 오류로 이어질 수 있으니, 정확한 key를 입력할 수 있는 상황이 아니라면, 조심할 필요가 있습니다.

2.2.2 전체 순회

정석적으로는 접근자를 이용해 접근합니다. 제가 싫어하는 방식입니다. 문법이 복잡하기 때문입니다. 그래서 보통은 접근자 선언시 auto를 이용해 접근자를 선언하고 접근하곤 했습니다.

for(auto itr = map.begin(); itr != map.end(); itr++) {
  cout << itr->first << " " << itr->second << '\n';
}

보통 위와 같이 접근했습니다. 그러나 요즘은 이런 방법 보다 향상된 for문을 이용하는 편이 더 편하게 느껴집니다. 아래에 향상된 for문을 이용해 접근하는 두가지 방법을 보이겠습니다. 접근자를 이용하는 방식과 pair를 이용하는 방식입니다.

for(auto itr : map) {
        cout << p->first << " " << p->second << '\n';
}

for(pair<string, int> p : map) {
        cout << p.first << " " << p.second << '\n';
}

2.3 데이터 검색

map의 find() 함수를 이용합니다. find() 함수는 접근자 iterator을 이용함에 주의해야 합니다.

if(map.find("Pig") != map.end()) {
  // 존재 O
} else {
  // 존재 X
}

위와 같이 입력으로 준 key를 가진 노드의 접근자를 반환합니다. 존재하지 않을 경우 map의 end의 접근자를 반환합니다.

2.4 데이터 삭제

2.4.1 원하는 key값을 가진 노드 삭제

map.erase("Dog");

2.4.2 접근자 삭제

iterator itr이 있다고 가정합니다.

map.erase(itr);

응용하여 앞에서 부터 특정 위치의 노드를 삭제 할 수도 있습니다.

map.erase(map.begin() + `);

2.4.3 범위 삭제

iterator itr1, itr2가 있다고 가정합니다.

map.erase(itr1, itr2);

응용하여 아래와 같은 삭제도 가능합니다.

map.erase(map.begin(), map.begin() + 2);
map.erase(map.begin(), map.end());  // 전체 삭제

2.4.5 비우기

map.clear();

혹은 위에서 보인

map.erase(map.begin(), map.end()); 

2.5 map의 크기

map.size();

위와 같이 size() 함수를 이용하면, key의 개수를 반환합니다. 즉, 몇 가지 종류의 key가 존재하는지 확인해볼 수 있습니다. 모든 종류의 물건을 가지고 있는지 확인해야 하는 문제에서 활용하면 좋습니다.

참고

C++ STL map Reference: https://www.cplusplus.com/reference/map/map/