败犬日报

Appearance

败犬日报 2024-12-09 ​

1. std::hive 容器 ​

未来可能进 C++26。

std::hive 是一个对象池，支持 O(1) 时间内的插入删除和双向迭代操作，插入删除不会导致其他迭代器失效。

实现原理：块状链表、跳跃域、空闲链表。

推荐阅读：https://zhuanlan.zhihu.com/p/11456846151

2. 一个经典错误：std::vector 扩容导致引用失效 ​

运行结果不符合预期：

cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int inf = numeric_limits<int>::max();
int main() {
    int n;
    cin >> n;
    vector<vector<int>> tr;
    tr.emplace_back(26, -1);
    vector<int> near{ 0 };
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int len = s.size();
        int res = inf;
        function<int(int, int, bool)> go = [&](int cur, int matched, bool new_node) {
            if (!new_node)
                res = min(res, len - matched + near[cur]);
            if (matched == len)
                return near[cur] = 0;
            int& nxt = tr[cur][s[matched] - 'a'];
            bool nxt_new_node = false;
            if (nxt == -1) {
                near.push_back(inf);
                tr.emplace_back(26, -1);
                nxt = tr.size() - 1;
                nxt_new_node = true;
            }
            return near[cur] = min(near[cur], go(nxt, matched + 1, nxt_new_node) + 1);
        };
        go(0, 0, false);
        cout << res << '\n';
    }
    return 0;
}

return near[cur] = min(near[cur], go(nxt, matched + 1, nxt_new_node) + 1); 这句话中，如果 near[cur] 先执行得到引用 const T &，后执行 go 函数让 near 扩容从而使引用失效。

（为什么是“如果”，因为这两个部分的求值顺序是未指定的）