警示后人,关于upper_bound
查看原帖
警示后人,关于upper_bound
288135
MichaelLee楼主2022/2/10 21:41

我提交了28次、花费了三个小时,用血与眼泪告诫大家:

STL中的upper_bound函数,不能用于查找set里的元素,否则复杂度会从 O(log2n)O(log_2n) 退化成 O(n)O(n)

所以只能使用set的成员函数(方法) upper_bound !!

lower_bound同理!!!

示例:

//  auto tmp=upper_bound(mp[a[x]].begin(),mp[a[x]].end(),x);
//  上面写法会多T五个点,bound里面套set复杂度会退化成O(n)! 
    auto tmp=mp[a[x]].upper_bound(x);	//直接调用成员函数!
2022/2/10 21:41
加载中...