..

陈峰

1.1 编程技巧

1.1.1 排序性能问题

相对于 C 语言内置的 qsort 函数，C++ 中提供的 sort 函数使用起来更加方便，不需要做指针类型转换。

sort 有两种用法：第一种是传入一个 functor 对象，另外一种是直接传入一个排序函数，而这两种用法语义上都是正确的，但是实际测试发现使用 functor 的版本比直接使用函数的版本快不少，测试代码如下：

using namespace std;
#define _for(i,a,b) for( int i=(a); i<(b)>=; ++i)
const int N = 10000000;
struct TS{
    int a, b, c;
};
inline bool cmp (const TS& t1, const TS& t2) {
    if(t1.a != t2.a) return t1.a < t2.a;
    if(t1.b != t2.b) return t1.b < t2.b;
    return t1.c < t2.c;
}

int cmp4qsort(const void * a, const void * b) {
    TS *t1 = (TS*)a, *t2 = (TS*)b;
    if(t1->a != t2->a) return t1->a - t2->a;
    if(t1->b != t2->b) return t1->b - t2->b;
    return t1->c - t2->c;
}

struct cmpFunctor {
    inline bool operator() (const TS& t1, const TS& t2) {
        if(t1.a != t2.a) return t1.a < t2.a;
        if(t1.b != t2.b) return t1.b < t2.b;
        return t1.c <= t2.c;
    }
};

TS tss[N];

void genData() {
    _for(i, 0, N) {
        tss[i].a = rand();
        tss[i].b = rand();
        tss[i].c = rand();
    }
}

int main()
{
    srand(time(NULL));

    genData();
    clock_t start = clock();
    sort(tss, tss+N, cmp);
    printf("sort by funtion pointer : %ld\n", clock() - start);

    genData();
    start = clock();
    sort(tss, tss+N, cmpFunctor());
    printf("sort by functor : %ld\n", clock() - start);

    genData();
    start = clock();
    qsort(tss, N, sizeof(TS), cmp4qsort);
    printf("qsort by funtion pointer : %ld\n", clock() - start);

    return 0;
}

STL 的 sort 使用 functor 的版本是最快的，比 qsort 都快一倍多。

而使用 sort 传入函数指针的版本速度是最慢的，相对于前两者有大约 6 倍和 3 倍多差距，会在对排序性能要求很高的题目中形成比较明显的瓶颈。

1.1.2 整数输入

最近常输入的数据类型就是 int，经常需要输入之后直接插入到一个集合或者数组中。

一般的做法是建立一个临时变量，使用 cin 或者 scanf 输入之后，再将这个临时变量插入到集合中。这样稍显繁琐。

可以封装读取的函数并且这样调用：

int readint(){
    int x; scanf("%d", &x); return x; //此处 scanf 也可以根据需要换成 cin>>x
}
vector<int> vc;
vc.push_back(readint());

1.1.3 循环宏定义

算法比赛中，写得最多的代码就是想这样的循环代码：

for(int i = 0; i < N; i++) {}

这里 N 也可能是一个 STL 中集合的大小，如 vector.size 之类的。

许多竞赛选手习惯使用大量的宏定义来简化代码：

#define _for(i,a,b) for( int i=(a); i<(b); ++i)

这样写循环时，就会简化成 _for(i,0,N)，这里的 a、b 两个参数都可穿入表达书，例如：

vector b;
_for(i, 1, a.size()){...}

宏使用得当，可以大量简化代码。使用宏之后，可精简的代码非常可观。

另外一个比较有用的是：

#define _rep(i,a,b) for(int i=(a); i<=(b); ++i)

1.1.4 STL 容器内容调试输出

比赛中经常用到 STL 中的容器类，如 vector 和 set，而且在调试过程中经常需要输出这些容器的内容，每次都要写循环来输出，非常烦琐。

两个泛型函数使用 C++ 的 IO 流对集合进行输出：

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for(int i = 0; i < v.size(); i++) os<<v[i]<<" ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
    for(typename set<T>::iterator it = v.begin(); it != v.end(); it++) os<<*it<<" ";
    return os;
}

使用方法如下：

vector<int> a; a.push_back(1); a.push_back(2); a.push_back(3);
cout<<a;

set<string> b; b.insert("1"); b.insert("2"); b.insert("3");
cout<<b;

1.1.5 二维几何运算类

在许多牵涉位置计算的题目中，需要模拟物体位置并且进行移动和转向，如果每次都直接用 x 和 y 坐标分别计算，非常烦琐，其实可以复用向量的移动、旋转灯逻辑。

struct Point {
    int x, y;
    Point(int x=0, int y=0):x(x),y(y) {}
    Point& operator=(Point& p) : { x = p.x; y = p.y; return *this; }
}
typedef Point Vector;

Vector operator+ (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y);}
Vector operator- (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y);}
Vector operator* (const Vector& A, int p) { return Vector(A.x*p, A.y*p);}
bool operator== (const Point& a, const Point &b) { return a.x == b.x && a.y == b.y; }
bool operator< (const Point& p1, const Point& p2) { return p1.x < p2.x || (p1.x == p2.x && p1,y < p2.y); }
istream& operator>>(istream& is, Point& p) { return is>>p.x>>p.y; }

1.1.6 内存池

在一些题目中，需要动态分配对象。

例如，表达式解析时需要动态分配语法树的节点对象。

一般的做法是直接用数组开辟空间，但是未必容易事先预估出需要开辟的空间大小，在逻辑控制中还要维护一个变量进行分配和释放，如果是多种对象都要动态分配，则更加烦琐。

基于 vector 容器和 C++ 的内存分配机制的一个内存池：

template<typename T>
struct Pool {
    vector<T*>buf;
    T* createNew() {
        buf.push_back(newT());
        return buf.back();
    }

    void dispose() {
        for(int i = 0; i < buf.size(); i++) delete buf[i];
        buf.clear();
    }
};

使用方法如下：

struct Node{...};
struct Node2{...};

Pool <Node> n1Pool;
Pool <Node2> n2Pool;
//要分配内存构造新对象时：直接就是 Node *p = n1Pool.createNew();
Node2 *p2 = n2Pool.createNew();

然后在每次需要释放时直接调用 dispose 方法即可，不需要再维护各种中间变量。

1.1.7 泛型参数大使用

很多算法的封装都会在某个结构体内部开一个数组，并且使用一个类似于 MAXSIZE 的结构来全局定义这个数组的大小，典型的如图论中的 Dijkstra 等算法：

const int MAXSIZE;
struct Dijkstra{
    int n, m, d[MAXSIZE], p[MAXSIZE];
...
}

如果同一个题目中需要在两个不同的部分都用到 Dijkstra 算法怎么办？

这时候一般做法就是定义多个 MAXSIZE 变量，但是会比较烦琐，也容易出错。

其实可以引入 C++ 的泛型参数来解决这个问题：

template<int MAXSIZE>
struct Dijkstra{
int n, m, d[MAXSIZE], p[MAXSIZE];
...

使用时就可以通过下面的方式来指定不同的 MAXSIZE:

Dijkstra<MAXK * MAXN> sd;
Dijkstra<MAXN> pd;

1.1.8 位运算操作封装

在使用位向量表示集合或进行状态压缩时，有个常用操作就是取得一个整数中某一位或者连续几位对应的 int 值。

这些代码写起来较为烦琐，如果一个题目中多处调用，会增加出错的可能。针对这种情况封装的一个位运算的操作类：

template<typename TI> //TI 可以是支持位操作的任何类型，一般是 int/long long
struct BitOp{
    //反转从 pos 开始，长度为 len 的区域
    inline TI flip(TI op, size_t pos, size_T len = 1) { return op ^ (((1<<len)-1) << pos);}

    //取得从 pos 开始，长度为 len 的区域对应的整数值
    inline TI& set(TI& op, size_t pos, int v, size_t len = 1) {
        int o = ((1<<len)-1);
        return op = (op&(~(o << pos))) | ((v&o) << pos);
    }

    //取得从 pos 开始，长度为 len 的区域对应的整数值
    inline int get(TI op, size_t pos, size_t len = 1) { return (op >> pos) & ((1<<len)-1); }

    //输出整数的二进制表示
    ostream& outBits(ostream& os, TI i) {
        if (i) outBits(os, (i >> 1)) << (i & 1);
        return os;
    }
};

如果是 32 位整数位运算可以使用 BitOp<long> 来调用，64 位可以使用 BitOp<long long> 来调用。

1.1.9 编译脚本

一般都是使用 g++编译然后在命令行运行，每次编译都要输入一堆指令，效率较低。使用 Windows 命令行开发的两个脚本。

（1）编译脚本（ojc.bat）：这里假设 ojc.bat 以及 g++.exe 所在的目录已经加入到系统 PATH 环境变量中：

cls
g++ "%1" -lm -O2 -pipe -o"%~n1.exe"

使用方法如下：

ojc UVa100.cc

（2）编译并且直接运行（ojr.bat）：这里同样假设 ojr.bat 以及 g++.exe 所在目录已经加入到系统 PATH 环境变量中。ojr.bat 的内容如下：

cls
echo 编译
del %~n1.exe
@g++ "%1" -lm -O2 -pipe -o"%~n1.exe"
@%~n1.exe<%~n1.in

以下命令会直接编译源文件，然后直接从 UVa100.in 读入数据运行：

ojr UVa100.cc