关于STL容器的一些技巧

关于STL容器的一些技巧

今天写一道题，发现了STL的自定义cmp函数实际上是一个效率很低的东西。如果能够用基本变量的自然顺序作为容器的比较器，就不要写cmp函数。

例如，对于有序序列查询<=x的最大数和<x的最大数，我们可以这样实现：

struct cmp{
    bool operator()(const int& a, const int& b){
        return a > b;
    }
};

multiset<int, cmp> st;

// <= x 的最大数
auto it = st.lower_bound(x)
    
// < x 的最大数
auto it = st.upper_bound(x)

但也可以这样实现

multiset<int> st;

// <= x 的最大数
auto it = st.upper_bound(x);
if(it != st.begin()){
    --it;
}else{
    // doesn't exist
}

// < x 的最大数
auto it = st.lower_bound(x);
if(it != st.begin()){
    --it;
}else{
    // doesn't exist
}

做题发现，下面一种写法比上面一种写法至少快二十倍。