728x90
🚦 이번 포스팅에서는 〰️
▶️ 맵(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 보러 가기 🔆
[Reference]
https://cplusplus.com/reference
728x90
'Algorithm > 자료구조' 카테고리의 다른 글
[자료구조] 그래프(Graph)란? +(인접 리스트vs인접행렬) (0) | 2023.08.11 |
---|---|
[자료구조] 트리(Tree)란? (0) | 2023.08.03 |
[자료구조] 힙(Heap)이란? (+우선순위 큐) (0) | 2023.08.02 |
[자료구조] Queue란? (+Circular Queue, Priority Queue, Deque) (0) | 2023.07.10 |
[자료구조] 스택(Stack)이란 (0) | 2023.07.10 |