Set & MultiSet

이번 시간에는 Set 과 MultiSet 에 대해 알아보도록 하겠다.

Set과 Multiset을 사용하는 가장 큰 이유는 Binary Tree로 구현되어 있기 때문에, Search를 O(logN)에 할 수 있다는 이유로 사용을 하게 된다.하지만 차이점은 Set은 중복을 허용하지 않고 , Multiset은 중복을 허용하기 때문에 중복시 MultiSet 을 통해 구현해야 한다.

#include <iostream>
#include <cstdio>
#include <set>
 
using namespace std;
 
set<int> s;
int main(){
    s.insert(10);
    s.insert(20);
    s.insert(5);
    s.insert(7);
    auto it = s.begin();
    for(int i=0;i<4;i++){
        cout << *it <<" ";
        it++;
    }cout <<endl;
    
    s.erase(10);
    
    it = s.begin();
    for(int i=0;i<3;i++){
        cout << *it <<" ";
        it++;
    }cout <<endl;
    
    it= s.find(8);
    cout << *it <<endl;
    
    return 0;
}

위와같이 insert,erase 등이 간단하고 삽입 시 자동으로 정렬이 되서 아주 편하다 보통 set이나 Multiset을 쓸 때는 lower_bound 등과 함께 쓰는거 같다

for (int i=0; i<n; i++) {
    auto it = s.lower_bound(v[i].second);
    if (it != s.end()) {
        ans += (-v[i].first);
        s.erase(it);
   }
}

이런식으로 말이다

추가적으로 STL 기능을 알아보려면 

http://blog.naver.com/warchife/220921678115 

http://blog.daum.net/coolprogramming/82  를 참고하면 좋을것 같다.