C++ 刷题坑点(下)

上一篇文章中提到了几个标准设计的坑。接下来有更加常见的几个、竞赛中经常遇到的坑,主要是由于 C++ 实现的问题。

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

使用不当坑

出现在这里的问题,一般都是程序员对于语言了解程度不足,作出了错误假设,错误地使用了一些接口导致的问题。只要多熟悉一下语言就可以解决这些问题。

字符串拼接字符方法错误导致多余复制

当然,我说的是对于 string 类型来说, str = str + chr 这样的操作。可能会有人以为这个操作和 str.push_back(chr) 一样是均摊 O(1) 的,但是实际上我是 O(n) 哒!

因为见到有人在群里讨论过所以拿出来说一说。

思考一下, str.push_back(chr) 是直接在 str 本身做修改,所以和 vectorpush_back 一样,直接改就是了。而 str + chr ,你有可能可以把这个加法计算结果赋值到别的字符串对象中, str 本身在加法运算中不变的,因此这个操作就需要复制了一遍 str 再拼接上 chr ,自然就是 O(n) 的。

同理 str1 = str1 + str2 的复杂度就是两者长度相加, str1 += str2 复杂度仅为 str2 的长度(均摊)。

替用方案:

  1. 使用 C 字符数组,维护长度
  2. 使用原地操作的成员函数: push_back append +=

不使用引用导致的多余的复制

感觉这是一个很常见的错误,经常出现在函数参数以及范围 for 循环中。

C++ 的(左值)引用语法最基本的用处是,可以在作为函数参数传入之后,函数中任何对该参数的修改都会反应到原变量上。对这个操作,最直观的理解就是,参数作为指针传入函数,通过指针对参数本体进行修改,只是反应给程序员的还是好像是直接对对象进行操作而已。所以本质上,如果函数参数是引用,我们认为没有出现任何复制,如果不是引用,就会出现复制构造。

为什么设计得这么愚蠢暂且不讨(其实还是为了和 C 行为一致,万恶的向后兼容),在程序设计竞赛中,我们只要记住函数参数尽可能使用引用即可,如果担心手贱写错改了参数,可以加上 const 。一个简单粗暴的判断方法,如果整个对象复制构造需要复制的数据大小比两个指针大小要大,那就可以考虑使用引用。

题外话,如果是只读,尽可能使用 const T & ,不是为了什么契约,编译器在知道这个变量不会被修改的保证下可以对程序进行更大胆的优化。

稍微测试了一下 sort 的比较函数,在使用引用的时候会进行约 \frac14n\log n\frac13n\log n 次复制,在不使用引用的时候则会进行约 2n\log n3n\log n 次复制。测试代码在下面给出:

#include <cmath>      // log2
#include <algorithm>  // std::{min, max, shuffle}
#include <iostream>   // std::cout
#include <limits>     // std::numeric_limits
#include <random>     // std::{random_device, mt19937_64, uniform_int_distribution}

struct Int {
  int value;
  static int copy_count;
  Int(int value = 0)
    : value{value} {
  }
  Int(const Int &that)
    : value{that.value} {
    ++copy_count;
  }
};
int Int::copy_count;

bool with_ref(const Int &lhs, const Int &rhs) {
  return lhs.value < rhs.value;
}

bool with_cpy(const Int lhs, const Int rhs) {
  return lhs.value < rhs.value;
}

int main() {
  using namespace std;

  constexpr int size_max = 512;
  constexpr int shuffle_times = 1024;
  constexpr auto cmp = with_ref;

  constexpr int int_min = numeric_limits<int>::min();
  constexpr int int_max = numeric_limits<int>::max();
  random_device rd{};
  mt19937_64 seed{rd()};
  uniform_int_distribution<int> unif{int_min, int_max};
  Int n[1000000];

  cout << "size\tmin\tmax\tn log n\n";

  for (int i = 0; i != size_max; ++i) {
    for (int j = 0; j != i; ++j) n[j] = unif(seed);
    int maxi = int_min, mini = int_max;
    int shuffle_count = shuffle_times;
    while (shuffle_count--) {
      shuffle(n, n + i, seed);
      Int::copy_count = 0;
      sort(n, n + i, cmp);
      maxi = max(maxi, Int::copy_count);
      mini = min(mini, Int::copy_count);
    }
    cout << i << ":\t" << mini << '\t' << maxi;
    cout.put('\t') << i * log2(i) << '\n';
  }
}

以上是对于函数参数,应当在该使用引用的时候就使用引用。

除了函数参数中有必要使用引用之外, C++11 的范围 for 也是一个若不注意使用引用就会出现多余复制的地方,其本质和函数类似,若不使用引用,则默认复制。

std::vector<std::string> vs;
// Insert strings to `vs'.
for (auto s: vs) {
  // Iteration through `vs', do anything to s.
}
// Strings in `vs' were copied and destroyed vs.size() times in iteration.

范围 for 循环可以等价替换为普通 for 循环,此处等价代码如下:

std::vector<std::string> vs;
// Insert strings to `vs'.
for (auto iter = vs.begin(), end = vs.end(); iter != end; ++iter) {
  auto s = *iter;
  // Iteration through `vs', do anything to s.
}
// Strings in `vs' were copied and destroyed vs.size() times in iteration.

于是这里的 auto 就会被类型推导为 string ,然后每次都会从 *iter 复制构造一次,下一次循环开始前析构,然后进行下一次循环的构造、析构……为了避免多余复制构造、析构的出现,此处只要使用引用,等价代码中 s 也会变成 *iter 的引用,就不会出现多余的复制:

std::vector<std::string> vs;
// Insert strings to `vs'.
for (const auto &s: vs) {
  // Iteration through `vs', do anything to `s'.
}
// No string was ever copied and destroyed, same as follows.
for (auto iter = vs.begin(), end = vs.end(); iter != end; ++iter) {
  const auto &s = *iter;
  // Iteration through `vs', do anything to `s'.
}

解决方案:

  1. 对于循环,可以手写循环
  2. 当拷贝的对象过大的时候,使用引用

类型不匹配隐式转型导致多余复制

这个现象也是在范围 for 循环中比较常见,毕竟其他地方没人会这么用。考虑下面这种代码:

using Key = std::string;
using Val = int;

std::map<Key, Val> msi;
// Insert string to int mappings into `msi'.
for (const std::pair<Key, Val> &psi: msi) {
  // Iteration through `msi'.
}

这个代码乍一看是非常正常的,使用 const std::pair<Key, Val> & 迭代 std::map<Key, Val> 怎么会有问题?

事实上查一下文档就可以知道 std::map<Key, Val>::value_type 实际上是 std::pair<const Key, Val> ,和 std::pair<Key, Val> 类型不兼容,不能直接绑定到引用上去,必须要构造出 std::pair<Key, Val> 之后才行。而这个构造,是隐式的。这个操作会莫名其妙地把整个 map 的键值对复制一遍。

上面的情况是最不容易发现的,还有其它类似的操作如:

std::vector<const char *> vs;
// Insert strings to vs.
for (const std::string &s: vs) {
  // Iteration through `vs'.
}

这也会导致整个 vs 的 const char * 被用来重新复制构造一遍 string ,然后循环下一趟开始前销毁。

解决方案:

  1. 牢记容器的 value_type
  2. 手写普通 for 循环
  3. 几乎总是使用 auto

搜索算法复杂度无保证

C/C++ 中自带有多种搜索算法,但是可惜, C++17 前,无一有良好的复杂度保证,均应以 O(nm) 复杂度度之。

尽管 C++ 的 sort 可以说是在可实现范围内效率相对最高的排序算法,但是相对应的 GNU 和 MSVC 实现的标准库 search 算法都是最差的 O(nm) 的,这里 n,m 分别指代模式串和匹配串。

包括 basic_string 的成员函数 find 和 rfind ,它们也是没有复杂度保证的,常见的实现中,同样使用了 O(nm) 复杂度的暴力。

C 库中同样也有一个字符串子串匹配算法,是为 strstr 系列函数,但是标准对于它的实现也没有要求。 GNU (glibc >= 2.9) 的实现是使用 Two-Way 算法,理论平均复杂度 O(m+n) ,空间 O(m) 。不过就我某次用了这个函数结果导致 TLE 的情况来看,可能效率没有我想象中的那么高。

C++17 另外要求实现提供 BM 和 BMH 算法的搜索器,这两种算法的均摊复杂度均为 O(n+m) ,等 C++17 普及后大概可以利用一波。另外,搜索器这个名字又是 C++17 的一个新概念了,此处暂且不表。

替用方案:

  1. 手动实现高效搜索算法
  2. 使用 C++17 的 boyer_moore_serarcherboyer_moore_horspool_searcher

实现细节 (bug) 坑

这里的问题是各个 C++ 实现中不统一或出现 bug 造成的问题。当实现出现问题时,我们唯一的方法就是避开实现的 bug 。

long long 格式化字符串问题

关于 long long 这个类型,在 C/C++ 中有一段比较奇妙的历史。它最初 (C89/C++98) 并不是 C/C++ 的标准类型之一。所有在 C89/C++98 编译器下可以编译通过的带 long long 类型的代码,其实都是不符合标准的。

——实际上,这些都是编译器的扩展。

当然啦,因为是编译器扩展,所以编译器(或者说标准库)处理 long long 类型的行为也可以有所不同,其中最著名的当属格式化输入输出函数中 long long 的格式化字符串的区别。

广为流传的:

  • Windows 下 long long / unsigned long long 格式化字符串为 "%I64d" / "%I64u"
  • Linux 下 long long / unsigned long long 格式化字符串为 "%lld" / "%llu"

实际上,这一点在 C++11 标准化了 long long 之后就不再有差异了。所以如果习惯使用了支持 C++11 或更新版本的编译器,就不需要再担心这个问题啦。

替用方案:

  • 手写输出优化
  • 使用 iostream

MinGW long double 格式化字符串问题

上面见识了 double 的,现在轮到 long double 了。long double 的格式化字符串应该是 "%Lf" ,但是(经测试)在基于 MinGW 编译器的 OJ (没错,说你们呢 HDOJ POJ )上使用该格式化字符串会输出铁定 WA 。

这次的错,完全是早期 MinGW 的 bug ,它就是无法正常使用格式化输入输出工具来正常输入输出 long double ,即使你写对了也不能用。

至于原因,首先 MinGW 是 GCC 在 Windows 下的一个分支,它使用了 GCC 前后端来编译生成二进制可执行程序,所以所有的类型都和 GCC 中一致。但是对于库函数 MinGW 使用了 Windows 的库来链接程序,问题出在它们之间的类型不兼容上。

x86 和 x86-64 架构下 GCC 中 long double 是 IEEE-754 中的 extended format ,而 MSVC 以及 Windows 提供的运行库使用的是 IEEE-754 中的 double format 。于是在 MinGW 中,它会使用 10 字节长的 extended ,而当参数传入 Windows 提供的运行库时,反而会被认为是 8 字节的 double 。无法正常输出反而成了小问题了,它甚至直接未定义行为了。

替用方案:

  • 换用编译器 C ,本质 MSVC (注意 MSVC 的 long double 就是 double
  • 改用 iostream
  • 输出前转为 double

GCC regex 不完全实现

GCC 4.9.0 之前的版本, regex 是未完全实现的,一些函数调用会给出错误的结果。

4.9.0 以及之后的版本都完全实现并可用了。

这完全是编译器捣鬼,没有正确实现的头文件就不应该可以直接被程序员使用还不报错,运行时错误比编译期错误难以排查多了,更何况出错源还是在标准规范过的头文件中。

替用方案:

  1. 匹配相关问题自己实现状态机
  2. 换语言

random_device 导致 RE

在 Linux 下的 libc++ 和 libstdc++ 中 random_device 的实现为读取 /dev/urandom 文件,可以认为这是一个特殊的生成真随机数的设备。而由于一般的 OJ 平台都会禁用 open 系统调用,这不会导致编译失败,但通常都会导致运行时错误。(罚时++ )

某些实现 (如 MSVC )可能会使用 x86 指令 RDRND ,这个指令不会造成异常(其它部分不保证,HDOJ 可用)。

没错,这是傻逼的我踩的坑。

替用方案:

  • 改用 stdlib 的 rand 系函数
  • 改用其它随机数生成算法(推荐梅森旋转)

小坑

gets 编译失败

这大概是一个老生常谈的话题了。出于安全考虑, C++11 弃用了 gets 函数, C++14 移除了 gets 函数。

gets 用着爽是爽,不过在工程开发中,由于没有限制读入的字符串长度, gets 带来的危害是极大的,具体内容超出了本文的范围,有兴趣的可以去搜一搜缓冲区溢出攻击相关知识(安利 ctf-wiki 上的栈溢出堆溢出的基础知识)。

替用方案:

  • fgets(buffer, size, stdin) 替代 gets(buffer) 以限制最多读入 n 个字符。
  • getline(cin, str) 来直接读入 string ,不限长度,还可以自定义分隔符。

除了 gets 之外还有的危险函数,其实数不胜数(可以参考我在逼乎上的这个回答 ),但是在竞赛中一般都不会考虑溢出的问题,毕竟题目都会给你提供数据范围,只要数组开得足够大就行。好在 gets 问题只会带来编译错误,修复也是稍加改动即可,不会有太大影响。

不过 HDOJ 的 contests 里 CE 居然算罚时,坑爹吗?

vector deque 空间问题

C++11 之前,对于一个 vector 或 deque 而言,除非被析构或重新赋值(包括 swap ),它们的 capacity ,也就是内存占用是只增不减的。在 C++11 之后提供了一个成员函数 shrink_to_fit 来将 capacity 缩小至和 size 相等,不过需要注意的是这个操作有可能会是 O(n) 的。

也就是一个 vector 或 deque 在它们的生存周期内,所占用的内存是随着时间不减的,即使是 clear 也不会缩小。

这在多组测试数据、需要开多个 vector 的时候可能会出现问题。极端情况下,如果总计需要数千个 vector ,每组数据最多对所有 vector 插入数千个元素,最多有数千组数据,极有可能导致 MLE 。虽然这种极端情况不容易出现,但这也容易造成一定的问题。

这也是一个比较隐蔽,如果不熟悉空间分配的原则可能会踩上的坑。

解决方案:

  1. 对于每组测试数据,定义 vector 为局部变量
  2. vector 数组考虑改用 std::vector<std::vector<T>>
  3. 如果可行的话,在知道 size 上界之后 reserve 足够大小
  4. 使用 v = vector<int>() 清空 vector
  5. C++11 可使用 shrink_to_fit 缩小容量

发表评论

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