※ std::map 요약
필자가 std::vector와 함께 많이 사용하는 연관 컨테이너 std::map에 대한 설명이다.
std::map은 key와 value의 쌍을 원소로 저장(pair 객체로 저장)하며, set처럼 원소의 key는 중복될 수 없다.
중복 key를 저장해야 한다면 std::multimap을 사용하여야 한다.
연관 컨테이너는 어떠한 key와 짝을 이루어 자료를 보관하는데, 자료를 넣거나 빼거나 찾을 때는 key를 이용하여야 한다.
※ std::map 특징
- std::map은 레드-블랙 트리(Red-Black Tree) 자료구조이다.
- std::map의 key는 중복될 수 없다. 중복 저장해야 한다면 std::multimap을 사용한다.
- 데이터 삽입과 동시에 정렬이 일어난다.
- 정렬은 key를 기준으로 정렬되며 기본 정렬 기준은 less(오름차순) 정렬이다.
- 검색 또한 key를 기준으로 검색(이분검색)한다.
- std::map의 원소는 std::pair 객체로 저장된다.
- 저장할 자료가 적을때는 메모리 낭비와 검색시 오버헤드가 생겨 대포로 파리 잡는 격이다.
※ std::map을 사용해야 하는 경우
- 삽입과 동시에 정렬해야 할때
- 많은 데이터를 보관해야 하고, 동시에 검색이 빨라야 할때
- 데이터 삽입, 삭제가 적을때