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은 진짜 안쓸듯;