map

왜 나는 모르는게 이토록 많고 정리할 것도 끝이 없는 것인가.. 하루에 글을 몇 개나 쓰는지 모르겠다. 그래도 그만큼 나의 지식과 프로그래밍 실력은 조금씩이라도 발전하고 있는 것 같아 힘을 내본다.

맵(std::map)

map은 키 - 값(key - value)쌍을 저장하는 연관 컨테이너이다. 각 키는 고유(유일)해야하며 키를 기준으로 자동으로 정렬된 순서로 데이터를 저장된다. 특정 키를 통해 값을 빠르게 찾을 수 있게 해준다. 따라서 값을 추가, 제거, 수정하는 등의 작업에 주로 사용되며 키-값 쌍을 관리하고자 할 대 유용하다.

사진 출처 : https://www.scaler.com/topics/cpp/map-in-cpp/

맵 컨테이너는 다음처럼 선언한다

#include <map> // <map> 헤더를 포함해야 한다.

std::map<std::키_형식, 값_형식> 객체_이름;

예를 들어 학생의 이름과 그에 해당하는 점수로 구성된 키-값 쌍을 맵 컨테이너로 만든다고 가정해보면 이름은(Key) 문자열이므로 string, 점수(Value)는 정수이므로 int형식으로 선언할 수 있다.

std::map<string, int> scores;

• 정렬된 상태 : 기본적으로 std::map은 키를 기준으로 오름차순으로 정렬된다. 사용자 정의 기준으로 정렬하고 싶다면, 비교 함수(Comparator)를 사용할 수 있다.
• 중복 키 불가 : std::map에서는 같은 키를 두 번 저장할 수 없다. 만약 이미 존재하는 키로 값을 삽입하려고 하면 기존의 값이 수정된다.
  • 맵에 키-값 쌍을 삽입할 때는 insert함수를 이용한다. 이때 키와 값을 묶어 std::pair 객체로 만들어 주는 std::make_pair 함수를 사용할 수 있다. make_pair함수는 템플릿 매개변수를 이용하므로 키-값 쌍으로 묶을 원소의 데이터 형식을 따로 지정하지 않아도 된다.

scores.insert(std::make_pair("Bob", 85));

• 빠른 검색, 삽입, 삭제 : std::map은 이진 탐색 트리로 구현되기 때문에 평균적으로 O(log n)의 시간 복잡도를 가진다.
  • 특정 키를 기준으로 원소를 검색할 때는 find 함수를 이용한다. find 함수는 맵에서 특정 키에 해당하는 반복자를 반환한다. 이 반복자로 키에 해당하는 값을 찾을 수 있다. 키가 존재하지 않으면 end()를 반환한다.
  • 삭제를 할때는 erase 함수를 사용한다. 특정 키를 가진 값을 삭제한다.
  • 검색을 할때는 operator[]를 사용하여 키에 직접 접근할 수있다. 키가 존재하지 않으면 새 값을 삽입한다.
  • 그 외 size() 는 map에 저장된 요소의 개수를 반환하고, empty()는 맵이 비었는지 확인한다.

std::map 의 특수한 점

• 키가 유일하므로 같은 키로 여러 값을 저장할 수 있다. 만약 여러 값을 저장하고 싶다면 std::multimap을 사용해야 한다.
• 정렬 순서는 기본적으로 오름차순, 다른 비교자Comparator을 사용하여 내림차순이나 사용자 정의 정렬도 가능하다.