STL - map / set

📒 map / set

📌 map이란?

• 각 요소를 const key, value로 이루어져 데이터를 저장하는 연관 컨테이너이다.
• 키값은 고유하며 데이터를 자동으로 정렬하는 데 사용된다.
• map에 있는 요소의 값은 직접 변경할 수 있다. 키값은 상수이며 변경할 수 없다.
• map은 C++에서 균형 이진 트리(Red-Black Tree)로 구현되어 있다.
• Red-Black Tree의 자세한 설명 : https://velog.io/@liz/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-red-black-tree
  
  

📌 map의 특징

• 키값을 기반으로 요솟값을 효율적으로 검색할 수 있다.
• 요소가 지정된 함수에 따라 키값을 기준으로 자동으로 정렬되어 있다.
• 양방향 반복자(iterator)를 제공한다.
• 연관 컨테이너인 만큼 탐색과 삽입 및 제거에 최적화되어 있다.
• 그러나 데이터를 정렬하여 저장하기 때문에 최악의 경우 O(log n)의 시간이 걸린다.
• 키와 값을 연결하는 조건일 경우 map을 선택하는 것이 좋다.
• 키가 고유하지 않은 경우에는 multimap이 적합하다.
• 키값만 저장하려는 경우에는 set이 적합하다.
• 키값이 중복되는 경우에는 multiset이 적합하다.
  
  

📌 정렬

• 맵은 key_compare의 저장된 함수 개체를 호출하여 요소를 정렬한다.
• 이 저장된 개체는 key_comp 메서드를 호출하여 비교한다.
• Red-Black Tree를 기반으로 정렬된 이진 탐색 트리 형태이다.
  
  

📌 map의 멤버 함수와 연산자는 아래 링크

• https://learn.microsoft.com/ko-kr/cpp/standard-library/map-class?view=msvc-170
  
  

📌 set이란?

• 데이터를 저장하고 검색되는 데 사용된다.
• set의 값(key)은 고유하며 데이터가 자동으로 정렬되는 연관 컨테이너 이다.
• set의 값은 변경할 수 없다. 이전 값을 삭제하고 새 값의 요소를 삽입해야 한다.
• map과 마찬가지로 균형 이진 트리(Red-Black Tree)로 구현되어 있다.
• Red-Black Tree의 자세한 설명 : https://velog.io/@liz/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-red-black-tree
  
  

📌 set 특징

• 키값을 기준으로 하여 값의 효율적인 탐색을 지원하는 가변 크기의 연관 컨테이너이다.
• 양방향 반복자(iterator)를 제공한다.
• 연관 컨테이너인 만큼 조회와 삽입 및 제거 작업에 최적화되어 있다.
• 키의 중복이 허용된 경우에는 multiset이 적합하다.
• 키와 값이 연결된 경우에는 map이 적합하다.
• 키와 값이 연결되어 있고, 키가 고유하지 않으면 multimap이 적합하다.
  
  

📌 정렬

• map과 동일하게 key_compare의 저장된 함수 개체를 호출하여 요소를 정렬한다.
• 이 저장된 개체는 map과 동일하게 key_comp 메서드를 호출하여 비교한다.
• map과 동일하게 Red-Black Tree를 기반으로 정렬된 이진 탐색 트리 형태이다.
  
  

📌 set의 멤버 함수와 연산자는 아래 링크

• https://learn.microsoft.com/ko-kr/cpp/standard-library/set-class?view=msvc-170
  
  

📌 map과 set의 비교

차이점

• map은 const key, value를 원소로 저장하고 key를 기준으로 데이터를 정렬한다.
• set은 key 값만 저장하고 정렬한다.

같은 점

• map과 set 모두 연관 컨테이너이다.
• 연관 컨테이너의 자세한 설명 : https://velog.io/@liz/STL-associate-container-%EB%B3%B5%EC%8A%B5%EC%9D%84-%EC%9C%84%ED%95%B4-%EC%9E%91%EC%84%B1%ED%95%98%EB%8A%94-%EA%B8%80-2023-11-14