STL - 27 (map -1)

1. map의 자료구조

• map의 자료구조는 '트리(tree)'이다. 정확하게는 '레드 블랙 트리(Red-Black tree)'이다.
  
  

2. 트리 자료구조의 특징

• 트리는 노드를 균형 있게 가지는 것이 성능에 유리하기 때문에
  기본 트리에서 변형된 B-트리, B+트리, R-트리, 레드 블랙 트리, AVL트리 등 다양한 종류의 자료구조가 있다.
• 균형을 이룬 트리는 정해진 방식에 따라서 분류하여 저장하기 때문에 시퀀스(일렬로)하게 자료를 저장하는 연결 리스트에 비해서 검색이 빠르다. 그렇지만 정해진 규칙에 따라서 자료를 삽입, 삭제 해야 되기 때문에 삽입과 삭제가 간단하지 않으며 구현이 복잡하다.
  
  

3. map은 언제 사용해야 할까?

• map은 많은 자료를 정렬하여 저장하고 있고 빠른 검색을 필요로 할 때 자주 사용한다!
  많은 자료를 빠르게 검색한다고 하는 부분은 앞 글에서 hash_map과 비슷하다!
  그러나 hash_map과 크게 다른 부분이 있는데, map은 자료를 저장할 때 내부에서 자동으로 정렬하고, hash_map은 그렇치 않다.(중요!) 정렬이 필요하지 않는 곳에서 map을 사용하는 것은 불필요한 낭비이다.
  
  
  # 정리
  map은 다음 조건일 때 사용하는 것이 좋다!
• 정렬해야 한다.
• 많은 자료를 저장하고, 검색이 빨라야 한다.
• 빈번하게 삽입, 삭제를 하지 않는다.