Algorithm - set, map, multiset, multimap, priority_queue (C++)
set / map
[ set ]
이진트리
로 구성
- key값을 가짐 (중복 허용 X)
- 자동정렬
element
값 수정이 안됨 (map
은 가능)
set<int> s;
set<int>::iterator it;
s.insert(4); //s : 4
s.insert(1): //s : 1 4
s.insert(2); //s : 1 2 4
vector<int> v;
v.push_back(3); //v : 3
v.push_back(5); //v : 3 5
v.push_back(6); //v : 3 5 6
s.insert(v.begin(), v.end()); //s : 1 2 3 4 5 6
s.erase(4); //s : 1 2 3 5 6
s.erase(s.begin()); //s : 2 3 5 6
//지울 원소를 입력받음
int toErase;
scanf("%d", &toErase);
it = s.find(toErase);
//지울 원소가 존재하는 원소일 때만 지움
if(it != s.end())
s.erase(it);
[ map ]
- 인덱스로 int가 아닌 다른 자료형을 사용할 수 있다
- key와 value쌍으로 이루어진
이진 트리구조(레드 블랙 트리로 구현)
- key값은 중복 불가(덮어 씌워져 버림)
iterator
보유
miltiset / multimap
[ multiset ]
set
처럼 자동정렬 / 이진트리
로 구성
- 중복값 허용(
set
은 X)
- 삭제 위치가 자유롭다(
priority_queue
는 X)
[ multimap ]
- 중복값 허용
(map을 사용하는 경우 중복값 비허용이여서 유용한 경우가 많음
--> 그래서 multimap
은 잘 안쓰이는 듯)
[]
를 이용한 접근이 안됨 --> 값수정도 안됨 (치명적인 단점)
priority_queue
Heap구조
를 가진 자료구조
- 자동정렬 해주는
queue
--> 결국 queue
라서 삭제
는 맨 앞
에서만 된다
queue
의 특성상 iterator
가 없다
queue
는 q.front() / q.back()
를 쓰지만,
pq.top()
으로 element
를 확인해야 함
정리
map
/ set
은 꼭 알아야한다
multiset
의 장점
: priority_queue
처럼 자동정렬 + 삭제위치 자유로움
map
은 레드 블랙 이진트리
로 구현,
unordered_map
은 hash table
로 구현
multimap
은 진짜 안쓸듯;
Author And Source
이 문제에 관하여(Algorithm - set, map, multiset, multimap, priority_queue (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Algorithm-set-map-multiset-multimap-priorityqueue-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ set ]
이진트리
로 구성- key값을 가짐 (중복 허용 X)
- 자동정렬
element
값 수정이 안됨 (map
은 가능)
set<int> s;
set<int>::iterator it;
s.insert(4); //s : 4
s.insert(1): //s : 1 4
s.insert(2); //s : 1 2 4
vector<int> v;
v.push_back(3); //v : 3
v.push_back(5); //v : 3 5
v.push_back(6); //v : 3 5 6
s.insert(v.begin(), v.end()); //s : 1 2 3 4 5 6
s.erase(4); //s : 1 2 3 5 6
s.erase(s.begin()); //s : 2 3 5 6
//지울 원소를 입력받음
int toErase;
scanf("%d", &toErase);
it = s.find(toErase);
//지울 원소가 존재하는 원소일 때만 지움
if(it != s.end())
s.erase(it);
[ map ]
- 인덱스로 int가 아닌 다른 자료형을 사용할 수 있다
- key와 value쌍으로 이루어진
이진 트리구조(레드 블랙 트리로 구현)
- key값은 중복 불가(덮어 씌워져 버림)
iterator
보유
[ multiset ]
set
처럼 자동정렬 /이진트리
로 구성- 중복값 허용(
set
은 X)- 삭제 위치가 자유롭다(
priority_queue
는 X)
[ multimap ]
- 중복값 허용
(map을 사용하는 경우 중복값 비허용이여서 유용한 경우가 많음
--> 그래서multimap
은 잘 안쓰이는 듯)[]
를 이용한 접근이 안됨 --> 값수정도 안됨 (치명적인 단점)
priority_queue
Heap구조
를 가진 자료구조
- 자동정렬 해주는
queue
--> 결국 queue
라서 삭제
는 맨 앞
에서만 된다
queue
의 특성상 iterator
가 없다
queue
는 q.front() / q.back()
를 쓰지만,
pq.top()
으로 element
를 확인해야 함
정리
map
/ set
은 꼭 알아야한다
multiset
의 장점
: priority_queue
처럼 자동정렬 + 삭제위치 자유로움
map
은 레드 블랙 이진트리
로 구현,
unordered_map
은 hash table
로 구현
multimap
은 진짜 안쓸듯;
Author And Source
이 문제에 관하여(Algorithm - set, map, multiset, multimap, priority_queue (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Algorithm-set-map-multiset-multimap-priorityqueue-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Heap구조
를 가진 자료구조- 자동정렬 해주는
queue
--> 결국queue
라서삭제
는맨 앞
에서만 된다 queue
의 특성상iterator
가 없다queue
는q.front() / q.back()
를 쓰지만,
pq.top()
으로element
를 확인해야 함
map
/set
은 꼭 알아야한다
multiset
의 장점
:priority_queue
처럼 자동정렬 + 삭제위치 자유로움
map
은레드 블랙 이진트리
로 구현,
unordered_map
은hash table
로 구현
multimap
은 진짜 안쓸듯;
Author And Source
이 문제에 관하여(Algorithm - set, map, multiset, multimap, priority_queue (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Algorithm-set-map-multiset-multimap-priorityqueue-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)