STL 坑点/细节

引自 cppreference.com 的语句会标粗体。

有些可能不是标准中的内容，但是 GCC 是这么实现的。

所有 STL

1. 如果两个对象 a 与 b 相互不比较小于对方：!comp(a, b) && !comp(b, a)，那么认为它们等价。

   即在 STL 中，a == b \(\iff\) !comp(a, b) && !comp(b, a)

std::multiset<Key, Compare, Allocator>

1. erase(const Key& key) 将移除键等价于 key 的所有元素。如果只想删除一个，请使用 erase(find(key))。

2. count(const Key& key) 的时间复杂度：与容器大小成对数，加上与找到的元素数成线性，即 \(O(\log \operatorname{size}+\operatorname{count}(x))\)。

3. 比较等价的元素顺序是插入顺序，而且不会更改。(C++11 起)

   我的理解就是 Key 相同时，后插入的元素排在后面。

4. find(const Key& key) lower_bound(const Key& key) upper_bound(const Key& key) 都返回最先插入的元素。

对于 3, 4 两点的示例：

#include<bits/stdc++.h>
using namespace std;
struct Value {
    int val, id;
    Value(int v, int i): val(v), id(i) {}
    bool operator<(const Value &b) const {
        return val < b.val;
    }
};
multiset<Value> st;
signed main() {
    for(int i = 1; i <= 5; ++i) 
        st.emplace(19260817, i);
    for(int i = 6; i <= 10; ++i)
        st.emplace(1, i);
    for(auto i : st) cout << i.id << ' ';

    cout << endl;
    cout << st.find(Value(19260817, 100))->id << endl;
    cout << st.lower_bound(Value(12345678, 100))->id << endl;
    cout << st.upper_bound(Value(12345678, 100))->id << endl;

    st.erase(st.find(Value(19260817, 100)));
    cout << st.find(Value(19260817, 100))->id << endl;
    cout << st.lower_bound(Value(12345678, 100))->id << endl;
    cout << st.upper_bound(Value(12345678, 100))->id << endl;
    return 0;
}

输出：

6 7 8 9 10 1 2 3 4 5 
1
1
1
2
2
2