2012年8月29日 星期三

Set

剛剛發現Set除了記錄是否出現過以外

還具有priority_queue的功用

他的begin()可以O(1)取得最佳值
(端看如何定義,通常為min值)

他的end()則可以O(1)取得最差值

他的erase():
erase(position<iterator>)可以O(1)刪除
erase(object)則可以O(lgN)刪除

還有基本的insert(), count(), find(), size()

主要用這七個便可以在競賽中如魚得水


最後就是要如何定義最佳:

平常都是直接重載小於運算子-

bool operator<(int x, int y) return x<y;

但當你要使用的是原本就存在的type,為了避免override

可以寫成這樣-

#include<set>
struct comp{
    bool operator()(int x, int y){ return x>y; }
};
int main(){
    set<int, comp> S;
}


但寫成這樣好像更好-



#include<set>
struct comp{
    bool operator()(const int& x, const int& y)const{ return x>y; }s
};
int main(){
    set<int, comp> S;
}

沒有留言:

張貼留言