[자료구조] 맵(Map), 셋(Set) 이란?

🚦 이번 포스팅에서는 〰️

▶️ 맵(Map) 이란? + multimap
▶️ 셋(Set) 이란?
▶️ 맵(Map) vs 셋(Set)

 

📌 맵(Map) 이란?

---

: 연관 컨테이너로, pair<key, value> 를 원소로 저장하는 컨테이너이다. key를 기준으로 데이터를 정렬한다.

연관 컨테이너는 원소를 빨리 찾기 위해서 사용한다. (연속 컨테이너인 array, vector, list보다 속도가 빠르다)

 

• insert 멤버 함수에 의해 삽입되면, 원소가 자동으로 정렬된다. (default=오름차순)
• key를 기준으로 정렬된다.
  ➡️ 내림차순 : map<int, int, greater> m로 선언 or 데이터에 -붙여 삽입처리
• 저장공간의 필요에 따라 allocator객체 사용 (동적할당)

 

🔆 맵(Map)의 구현 및 함수 -C++

 

STL 구현 : map<key, value> pair 형태로 선언

 

STL map의 함수들

〰️iterator

begin(), end()

 

〰️추가 및 삭제

insert(pair), erase(key), clear()

 

〰️조회

find(key), count(key)

 

〰️기타

empty(), size()

 

 

📌 multimap이란??

: key값이 중복 가능한 map으로, 나머지는 거의 동일하다.

 

 

 

📌 셋(Set) 이란?

---

 

: 맵과 같이 연관 컨테이너로, 중복되지 않는 값들을 모아둔 컬렉션이다.

 

• 연관 컨테이너 중 하나이다. = 자료와 key값이 서로 관련이 있다.
• 노드 기반 컨테이너로, 균형 이진트리로 구현되어있다.
• key라 불리는 원소들의 집합으로, key값은 중복이 허용되지 않는다.
• value가 따로 없다. 즉, key와 value가 같은 데이터를 원소로 저장한다.
• 원소가 insert 멤버 함수에 의해 삽입되면 원소가 자동으로 정렬된다. (defalut=오름차순)
• 중위순회(inorder traversal)을 통해서 순서대로 출력이 가능하다.
  중위순회(inorder traversal) : 왼쪽->루트->오른쪽 순서대로 방문하는 순회방식
• Fast Lookup이 필요할 때 주로 쓰인다.
  ➡️ 연속 컨테이너보다 빠르다. O(nlogn)
  ➡️ 원소 삽입 O(logn)

 

 

🔆 set의 구현 방법 및 함수 - C++

 

STL 구현 : set<data_type> 형태로 선언

 

STL set의 함수들

〰️iterator

begin(), end()

 

〰️추가 및 삭제

insert(pair), erase(key), clear()

 

〰️조회

find(key), count(key)

 

〰️기타

empty(), size()

 

 

📌 multiset이란?

: key값의 중복이 허용되는 set이다.

 

📌 맵(Map) vs 셋(Set)

---

맵 (Map)	셋 (Set)
중복되지 않는 값을 저장하는 연관 컨테이너 (이진트리로 구성됨)
<key, value> pair 값을 저장한다.	value값이 따로 없다.
multimap : 중복이 허용되는 맵	multiset : 중복이 허용되는 셋

 

 

 

🔆 [자료구조] 다른 Posting 보러 가기 🔆

✅ 스택(Stack)이란?

✅ 큐(Queue)란?

✅ 힙(Heap)이란?

 

 

[Reference]

https://cplusplus.com/reference 

https://blockdmask.tistory.com/79

https://www.geeksforgeeks.org/set-vs-map-c-stl/