C++ 刷题坑点(上)

这几周校队集训因为 C++ 兼容性、版本等等的各种问题,经常被各 OJ 给坑得不要不要得,稍微记录一下以免再次踩坑。

  1. C++ 刷题坑点(上)
  2. C++ 刷题坑点(下)

接口不一致坑

C++ STL 中,大部分容器都有统一的接口,一般而言,越是近似的操作,它们的复杂度、效果都更可能相同。不过总有少数的那么几个例外存在,容易掉坑里。

vector<bool>

两个字,别用就是了。

有时候会想到类似储存 int 一样用 vector 来储存一些对象,但是天下所有类型都可以,唯独 bool 不可取, vector<bool> 和 vector<int> 是两个完全不同的类型,它不是你熟悉的 vector 。

这是 C++ 早期的一个彻头彻尾设计失败的实验品,因为设计得太傻逼,所以导致根本没法用。和 bitset 一个天上一个地下(虽然说 bitset 也是为了填 vector<bool> 的坑被发明的)。它不支持位运算、迭代器强制引用、速度奇慢无比,不论是哪一点都完全掩盖了压位赚到的那一点可怜的空间效率的微弱优势。

简单地说, vector<bool> 为了空间效率(压位)而带来了种种问题,对于程序设计竞赛而言,影响最大的恐怕就是——在旧版本的编译器下慢了一个数量级。

尽管较新的库实现效率优化了很多,但是还是无法赶上 vector<char> (x86-64 架构下,相同 size vector<char> 每次 realloc 都比 vector<bool> 多复制 8 倍数据,还是比它快),还是不建议使用。

替用方案:

  1. 长度不定用 vector<char> ,可以考虑手动压位使用更长的类型
  2. 长度固定用 bitset

double 格式化字符串问题

和 long long 类似, double 也存在格式化字符串上的问题,但这里的问题是出现在读入和输出的格式化字符串不一致。

我们读入输出 double 类型习惯性地都会使用的格式化字符串 "%lf" 。但是坑爹的是,这在 C++11 之前是错误的!读入应当使用 "%lf" ,而输出应当使用 "%f"

首先,我们来谈论一下类型提升相关话题:

除了整型之外,浮点数在作为变长参数的一部分传入至调用函数(如 scanf printf 的第二个及之后的参数)时,也会有提升。确切地说,有以下三种类型的提升:

  • 转换 nullptr_t 到 void * (C++11 之后)
  • 转换 float 到 double
  • 转换 bool 、 char 、 short 及无作用域枚举到 int 或更宽的整数类型

所以实际上变长参数函数不可能在变长参数中收到 float 类型,函数内部也不需要考虑 float< 的问题。 然后我们来看 printf 和 scanf 。 C++11 之前, printf 中处理 double 的格式化字符串是 “%f” , scanf 中处理 double 类型的格式化字符串是 "%lf" ,而 "%f" 留给了 float 类型。

是什么造成了这种差异呢?

当我们需要用 scanf 读入某个变量的时候,我们需要传入的是这个变量的地址,根据上面的规则,虽然 float 会提升成 double , float * 和 double * 却不会互相转换,因此 scanf 必须分别处理这两种类型。

而对应的,使用 printf 输出的时候,由于 float 类型会被自动提升成 double 类型,所以 printf 就不需要再给 float 单独提供另一个格式化字符串了,scanf 中属于 float 的留给了 double ,而属于 double 的则无人认领—— printf 不会处理 "%lf" ,按照标准,这是未定义的行为,也就是出 bug 了。

要我说,这当然是一个严重的设计失误,不过好在 C++11 修正了这一行为,从此在 printf 中使用 "%lf" 也是可以的了。

C++11 又一次拯救了人类。

替用方案:

  1. 牢记格式化字符串规则
  2. 使用 iostream

list::size() 低效

和一开始说的一样,这东西的时间复杂度可能O(n) 的( C++11 之前)。

究其原因,是由于 list 支持一个 splice 操作,它的作用是将另一个blistb的一个区间或者单个元素提取出来、插入到当前链表的某个位置,就这个操作导致了链表大小无法维护。

给你提供了区间首尾、插入位置三个指针和被截断与被插入的两个链表,让你来实现这个操作,不去考虑其它的东西,不难吧, O(1) 就可以了,岂不轻松?

然后问题来了,如果满足了 O(1) 区间 splice ,则不可能在 O(1) 维护被截断、被插入的链表的大小:如果不知道 splice 的区间的大小,就无法调整两个链表的大小;如果去计算 splice 区间的大小,在链表中就只能 O(n) 迭代, splice 就无法 O(1)

( C++11 之前)标准对这两者的实现没有做要求,交由实现来决定,两害相权取其轻。不同的实现有不同的考量。 举例而言 size 在 GNU 中的实现是 O(n) 而 MSVC 是 O(1) ,区间 splice 的复杂度则相反, GNU 的是 O(1) 而 MSVC 是 O(n) 的。两种选择均无可厚非, MSVC 的实现使得 API 更统一,对于不知情的人来说不会因为频繁调用 size 而白白浪费 CPU 算力;而 GNU 的实现则保留了更大人为优化的可能,对于有 O(1) splice 需求的人来说,只需要手动维护 size 仍能达到全局 O(1) 的复杂度。

C++11 之后强制要求 size 实现为 O(1) 。虽然这在设计上更为统一不容易犯错了,但是这也导致了 splice 不可能在 O(1) 达成。相对来说,反而使得 list 更加鸡肋了。本来可能期望一个 O(1) splice ,手动维护大小可以达到全局 O(1) 的,现在是不行了。

不过 list 本来就是鸡肋的说,除了中间插入删除理论复杂度比 vector 低,常数被完全碾压。

C++11 另外引入了一个 forward_list ,是为单向链表。还是没啥用,引入其的目的是缩小内存使用,而非替代 list ,更甚者,这个类型根本不提供 size ,而 splice 也是 O(n) 的。

顺便一提 basic_string (好吧,你就当它是 string 就好了)的 size 复杂度也是没有保证的,但是我没有另外拿出来讲,原因是虽然标准没有保证 O(1) ,但是我至今没有见过不是 O(1) 的实现,大可不必担心。

替用方案:

  1. 手动维护 list 的大小
  2. 如果需要 O(1) 区间 splice ,只能手动实现链表,目前标准库不支持。

可重复关联容器 count 低效

关联容器有 set 、 map 、 multiset 、 multimap 四种,C++11 又引入了无序关联容器(本质哈希表)有 unordered_set 、 unordered_map 、 unordered_multiset 、 unordered_multimap 四种。可重复的指的是它们中的 multi 版本。可重复的关联容器可以保存多个等价或相等的元素。

关联容器对象在调用 assoc.count(value) 的时候的复杂度为 O(\log n + r) 。无序关联容器在调用 assoc.count(value) 的时候平均复杂度为 O(r) ,最坏为 O(n+r)。此处 n 为容器大小,r 为函数返回值。也就是说如果 r 很大,甚至整个容器都是查询值,一次调用的复杂度就至少是 O(n) 的。

对于非重复的关联容器来说,返回值永远为 0 或 1 ,所以这个 r 实际上不会存在,但是对于可重复来说,这里就不一样了。经常看到会有 if (assoc.count(value)) { /* ... */ } 这样的代码,如果 assoc 是可重复的关联容器是可能会被卡的,因此 TLE 了还是不容易马上注意到这里有问题的。

这其实也算不上是接口不一致,不过第一次得知此事还是挺令人讶异的。

究其原因,是因为 < 和 == 以及 hash 的判断可能不会使用对象中所有信息,如果容器使用这两者判等并直接合并等价元素维护个数,可能会导致信息的丢失。因此容器不会对等价元素作合并,而是保留每个副本,在需要计数的时候找出首个元素,往后迭代统计等价元素个数,这个操作均摊是 O(r) 的。

一个比较粗暴的解决方法是手动合并、维护重复个数,将 multiset<T> 改为 map<T, size_t> , multimap<Key, Val> 改为 map<pair<Key, Val>, size_t> ,将个数作为值维护。

如果只是判断存在性,标准更推荐的做法是使用 assoc.find(value) != assoc.end() ,或者采用 C++20 的 assoc.contains(value) ,上述两种方法是完全等效的。

替用方案:

  1. 使用 map<pair<T, size_t>> 取代 multiset<T> ,手动维护 size
  2. 使用 map<pair<Key, Val>, size_t> 取代 multimap<Key, Val> ,手动维护 size
  3. 存在性判断 assoc.count(value)) 应当改用 assoc.find(value) != assoc.end()
  4. C++20 存在性判断 assoc.count(value) 应当改用 assoc.contains(value)

qsort 复杂度无保证

虽然没人用,不过我就想提一提这个函数,以说明人类的自以为是是多么可怕以及标准库真的不会取名。 qsort 是 C 语言 stdlib.h 中提供的一个排序算法。你别看它叫做 qsort 就以为它是 quick sort 了,它仅仅是排序而已,什么排序都行,只是名字前莫名其妙带了一个 q ……

标准再一次地,没有对实现作任何限制,允许作者为了库撰写简便而使用 O(n^2) 的算法。甚至使用 O(n!n) 的真 · 暴力排序也是符合标准的(“符合标准”真是万恶之源啊)。

当然,良心的 GNU 和 MSVC 还是用 quick sort 实现了这个函数,所以通常来说期望复杂度还是 O(n\log n) 的。

就算如此,没有引用的 C 语言在撰写比较函数的时候传参也是一个大麻烦,必须显式使用指针,这就导致了比较函数非常恶心,只能传入两个 void * 指针(类型擦除也是泛型的一部分,不爽不要玩!),在内部类型转换并判断大小,如果我需要对一个指针数组根据指向的对象进行排序,比较函数的内容就会让人眼花缭乱。

总之,不推荐使用 qsort ,赶紧使用 GNU 实现的优秀的内省算法 sort 吧!

替用方案:

  1. 改用 sort 或 stable_sort

发表评论

电子邮件地址不会被公开。 必填项已用*标注