OI 中的坑

OI 中的坑

记录了一些 OI 中会遇到的巨坑,希望能对看到这篇文章的你有所帮助。

  • std::unordered_map

是的,unordered_map 很快,但只在它没有清空操作的时候。虽然 cppreference 上面指明 clear 操作应该是 $O(n)$ 的,但实测就是很慢。

  • std::abs

你会说:这怎么会有问题?很遗憾,这确实有问题。请看下面一份代码:

1
2
3
4
5
6
7
#include <cmath>
#include <iostream>

int main() {
int x, y; std::cin >> x >> y;
std::cout << std::max(std::abs(x), y) << std::endl;
}

在大多数编译器上,这段代码是正确的。但在部分老旧的编译器版本中(别指望 OI 评测用的编译器版本能有多新),这段代码会编译失败,原因是 std::max 必须接受两个相同类型的元素,但 std::abs 在这种老旧的编译器版本中只有一种重载 double abs(double)。解决方法是额外引 #include <cstdlib>

此外,std::abs(INT_MIN) == INT_MIN,有毒瘤出题人可能会卡(肝)。

  • 不加返回值类型的函数定义

这是同学遇到的… 同学因为过于手残打出了如下代码:

1
inline link(int x, int y) { /*blah blah blah*/ }

然后在自己的电脑上编译通过,提交后惨痛 CE。因为老版本一点的编译器貌似是默认以 int 作为默认类型,所以上段代码不会报错,但任何其它正常的编译器都会告诉你 C++ 必须为每一个元素指定类型

  • 函数不返回

恩,很熟悉的坑。总之就是这样做本地大概率不会 WA,提交则会大概率 RE。在 Windows 不写返回值(也不用到)还好,但 Linux 上不写返回值则会直接 RE(Illegal Instruction),所以请不要擅自作死。可以添加 -Wall -Wextra -Wpedantic 来显示所有可能的警告。

  • std::seterase

在 C++11 之前,std::seterase(iterator) 是不返回的(草),在 C++11 之后才会被删除的迭代器的 next。此外,std::seterase(const key_type& key) 返回被删除的元素数量(size_t),虽然在 std::set 里面恒为一就是了。

要不是我考试时 C++98 编译了一遍就爆零了(

  • 指针转整型

因为怕 time(0) 不够随机(?)于是 srand((unsigned long) malloc(1)) 然后光荣 CE。64 位机子上编译器会告诉你强转会丢失精度,而且它!不!是!警!告!是!个!错!误!

  • set 的比较函数

需要往一个 set 里面加很多点,然后按 x 的值排序:

1
2
3
4
5
6
struct cmp_t {
inline bool operator()(const point &x, const point &y) const {
return x.x < y.x;
}
};
std::set<point, cmp_t> w;

光荣爆炸。为什么?当两个点 a, bx 值相同时,(a < b) == (b < a) == false,因此 set 认为它们是一个元素然后给你去重。BOOM!

  • for 循环的变量
1
2
3
4
5
6
7
int v;
namespace test {
void foo() {
for (int v = 1; v <= 1; ++v) {}
v = 1;
}
}

NOI Linux 上 / gcc 6.1 以下的版本光荣 CE!产生原因仍旧是谜,可认为是低版本 gcc 的 bug。


有新的坑再记在这里。

作者

Mivik

发布于

2020-11-16

更新于

2022-08-08

许可协议

评论