1. 关于 std::sort

(2023.9.19)

最近在写一道题，调用 sort 时比较函数有一只 log 的额外复杂度，结果 T 飞了。后来发现把 sort 改成 stable_sort 就过了，并且用时大约是原来的 $\frac{1}{3}$。

经过实测，发现 std::sort 调用 cmp 的次数大约是 std::stable_sort 的 1.6 倍（当 $n \approx 5.5\times10^6$ 时），所以 如果你的比较函数自带大常数 / 复杂度比较高，请慎用 std::sort。

  1. 关于 std::vector

(2023.9.20)

今天在写一道 DS 时发现 RE 了，死活调不出来。

后来发现挂了的其实是这样一个状物：

vector<int> a;
size_t ins() { 
  size_t id = a.size();
  a.eb(0);
  return id;
}
void upd(int & p) {
  int pre = p;
  p = ins();
  // ...
}
void doit(int pos) {
  upd(a[pos]);
  // ...
}

std::vector 中插入一定量元素后会扩容，扩容完原先元素的引用会失效，然后就寄了。

十分恼火 /fn。

(upd on 2024.2.22)

众所周知 std::vector 有一个构造函数是元素个数+元素的值。但是你如果想构造一个只有 1 个 0 的 vector，并且这样写：

vector<int>{1, 0}

恭喜你，你得到了一个长度为 2 的 vector，其值为 [1, 0]。

这是因为构造函数传花括号的时候会优先调用对 initializer_list 的重载。

正确的写法应该是 vector<int>{0} 或者 vector<int>(1, 0)。

  1. 关于 __gcd

(2023.9.21)

经过测试：

  • 在值域范围 $2^{64}$ 时，std::gcd [c++17] 处理用时约是 std::__gcd 和手写 gcd 的 $51\%$（其中手写 gcd 略快于 std:__gcd）
  • 在值域范围 $2^{32}$ 时，std::gcd [c++17] 处理用时约是另外两者的 $74\%$。

(upd 2024.10.2)

上述结论和机器架构、编译器版本有关，可能并不准确。如果追求极致效率可以采用 platelet 论文中的写法。

更多细节请参阅 各种代码常数 benchmark 中的 EP.2。

  1. 关于 std::abs

(CSP-S 2023 后)

这个东西的实现是 shaber 的函数重载。因此，往里面丢一个 __int128 会喜提一个 ambiguous call 并且 CE。

(upd after 2024 联合省选)

NOI Linux 上编译器的默认选项是 -std=gnu++14，而 gnu 标准提供了 __int128 相关重载。因此造成了臭名昭著的 i128-abs 惨案。此外，unordered_map<__int128> 也会导致类似的问题。

  1. 关于 std::cin

(2024.8.26)

c++20 及以后，为了避免读入 C 风格字符数组时出现溢出，必须显式指定其长度，标准库会在读入时防止数组越界访问。所以如果你开了一个长度为 50 的字符数组，其实只能读入长度为 49 的字符串。

  1. 关于 std::unordered_map 和 __gnu_pbds::gp_hash_table

(2024.10.1)

标准库中的哈希表，如果插入一个元素之后爆了某个阈值，会全局 rehash，这会导致已有的迭代器 全部失效。所以不要轻易使用哈希表的迭代器。

此外，__gnu_pbds::gp_hash_table 的默认哈希函数不是很合理，可以使用如下自定义哈希函数：

using u64 = uint64_t;

struct chash { // large odd number for C
  const u64 C = u64(4e18 * acos(0)) | 71;
  u64 operator()(u64 x) const { return __builtin_bswap64(x * C); }
};
// __gnu_pbds::gp_hash_table<ll, int, chash> h({}, {}, {}, {}, {1 << 16});
  1. 关于 std::int64_t

(2024.10.2)

在某些机器上 std::int64_t 是 long 的别名，如果你对 std::int64_t 和 std::int32_t 都重载了某个函数，传入一个 long long 的时候就会 ambiguous call 并且 CE。

  1. safe bool idiom
(2024.10.2)
struct Info {
  int val, wi;
  Info(int _wi = 0) : val(-1), wi(_wi) {}
  operator bool() const { return val != -1; }
  Info operator + (const Info &rhs) const { /* do something... */ }
}

看上去很对对吧，我们可以用 if (a) 来代替冗长的 if (a.val != -1)。

但是考虑如下代码：

// Info f[MAXN];
int qwq{}; // should be `Info qwq` !!!
vector<Info> ovo = ...;
for (Info x : ovo) { qwq += x; }
f[x] = qwq;

这段代码通过了编译，并且没有任何 warning！

原理： x 通过 operator bool 被隐式转成了 bool，然后再经由整形提升变成了 int，最后和 qwq 做了加法。

解决方案：

将 operator bool 换成 explicit operator bool。这样该转换函数只会在某些特定的表达式（如 if）或者显式转换中生效。

以下是标准中规定生效的表达式：

  • controlling expression of if, while, for;
  • the logical operators !, && and ||;
  • the conditional operator ?:;
  • static_assert;
  • noexcept.
  1. mt19937 与 FHQ

(2024.10.20)
mt19937 构造很慢，operator() 是均摊 $O(1)$ 的，但是有一定常数。

在 duck.ac 上，调用 1e8 次 mt19937::operator() 需要 ~580ms。（测试代码）

标签: none

添加新评论