STL 坑点/细节

发布时间 2023-11-03 13:33:41作者: untitled0

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

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

所有 STL

  1. 如果两个对象 ab 相互不比较小于对方:!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