个人总结的OI、ACM竞赛编码技巧：调试，查错，常数优化

技巧1：封装一个能进行越界检查的Array类

C/C++中数组越界是一件很让人头疼的事。内置的数组类型不进行越界检查，而越界后的行为是未定义的。这就导致有时候程序的行为极其诡异，程序员却迟迟定位不了bug的位置。

C++11提供的std::array类提供了at()成员函数，该函数会在下标越界时抛出一个std::out_of_range类型的异常。std::array重载的operator []不进行越界检查。

但有时我们既想要越界检查，又不想牺牲性能，还不想改变用operator []访问元素的写法。为此我们对数组进行一些封装：

 1 #include <array>
 2 template <class Tp, size_t N>
 3 struct Arr: public std::array<Tp, N> 
 4 {
 5 #ifndef NDEBUG
 6     Tp& operator [] (size_t idx) { return this->at(idx); }
 7     const Tp& operator [] (size_t idx) const { return this->at(idx); }
 8 #endif 
 9 };
10 template <class Tp, size_t N1, size_t N2>
11 using Arr2 = Arr<Arr<Tp, N2>, N1>;

这里的Arr类继承了std::array的所有成员。在NDEBUG宏未定义时，派生类Arr的operator []覆盖了基类的版本。（顺便黑一波C++坑出风采的const机制）

不需要越界检查时，只需在前边加一句#define NDEBUG即可。（-O2和-O3编译优化下会自动添加NDEBUG，以禁用assert宏）

最后两行是二维数组的一个typedef。注意第11行里边，第二维的大小N2在里层，第一维的大小N1在外层。

在OI、ACM等比赛中，常数优化虽然不像复杂度优化那样重要，但对于某些数据量很大的题目，如果实现时常数太大，也会有TLE的风险。

不过也要注意，常数优化往往是以程序可读性降低为代价的，在实际编程时需要有所取舍。（更何况卡常数的题很容易被喷成毒瘤￢＿￢）

技巧2：arr[x +1] = f(arr[x])的时间常数通常比arr[x] = f(arr[x - 1])更小

举一个简单的例子：

 1 using LL = long long;
 2 LL arr[50000000];
 3 void foo() {
 4     for (int i = 1; i < size(arr); i++)
 5         arr[i] = i + arr[i - 1];
 6 }
 7 void bar() {
 8     for (int i = 0; i < size(arr) - 1; i++)
 9         arr[i + 1] = i + 1 + arr[i];
10 }

两种递推的作用是完全等效的，不过对于CPU而言，前一种写法更为“缓存友好”（cache friendly）。当访问arr[i]时，CPU会将紧随其后的一小块缓存起来，访问CPU缓存的速度要快于访问内存。

关于“缓存友好”的详细内容可以参考：https://stackoverflow.com/questions/16699247/what-is-cache-friendly-code

测试程序以及运行结果如下：（编译参数：-std=c++17 -O2）

 1 #include <iostream>
 2 #include <utility>
 3 #include <boost/timer.hpp>
 4 
 5 using namespace std;
 6 using LL = long long;
 7 LL arr[50'000'000];
 8 void foo() {
 9     for (int i = 1; i < size(arr); i++)
10         arr[i] = i + arr[i - 1];
11 }
12 void bar() {
13     for (int i = 0; i < size(arr) - 1; i++)
14         arr[i + 1] = i + 1 + arr[i];
15 }
16 
17 int main()
18 {
19     for (int i = 0; i < 5; i++)
20     {
21         cout << "Case " << i + 1 << ":
";
22         boost::timer timer;
23         foo();
24         cout << "foo(): " << timer.elapsed() << '
';
25         timer.restart();
26         bar();
27         cout << "bar(): " << timer.elapsed() << "
";
28     }
29 }
30 
31 /*
32 Case 1:
33 foo(): 0.227
34 bar(): 0.073
35 Case 2:
36 foo(): 0.099
37 bar(): 0.077
38 Case 3:
39 foo(): 0.1
40 bar(): 0.074
41 Case 4:
42 foo(): 0.102
43 bar(): 0.075
44 Case 5:
45 foo(): 0.103
46 bar(): 0.079
47 */

可以看到对于long long类型，bar()的运行时间比foo()短了大约20%（Case 1的数据比较诡异，第一次运行的话耗时都会很长，求大神解释）。

而对于int类型，测试结果表明bar()的运行时间比foo()短了50%~60%，优势更为突出。

——To be continued——