C++ in OI

发表于 2017-10-09 更新于 2020-09-08 阅读次数：本文字数： 7.4k 阅读时长 ≈ 7 分钟

前言

本文分为两个部分，分别总结我所知道的C++在OI中的，和其他软件的推荐。

C++ in OI

C++是相当复杂的一种语言，在OI中除了广为人知的部分外，也有其他有趣的内容。当然，以实用为主。

现在稳定的C++版本有C++98、C++11、C++14，现在很多OJ还只支持C++98，但也不乏对于后两者的支持。在NOI系列比赛中(还是比较功利)，GCC版本为4.8.4，默认标准是C++98，提交的也是，但是也可以在本地使用绝大部分C++11特性(称为C++0x)。最新的GCC稳定版本为7.2，但是由于某些原因，MinGW-w64尚未编译这个版本，因此我一直用7.1。GCC 7.1默认的标准是C++14，但也有部分C++17支持。另外，MSVC也能支持很多新特性。

GCC

GCC-GNU Compiler Collection，而早已不再是GNU C Compiler了，是NOI系列使用的C/C++编译系统。GCC是开源跨平台的，在Windows下，有Cygwin和MinGW系列。而MinGW-w64是MinGW的继任，相比MinGW，不但提供了64位的版本，还提供了更新的版本。

如果你使用64位的OS，那么选择64位的版本是很好的选择，能充分利用64位的优势。

安装MinGW-w64，我推荐直接下载对应的压缩包，而不是用在线安装程序。可以保留压缩包备用，另外最好加上环境变量。

如果你同时也安装了Free Pascal，务必把MinGW的目录放在FPC前面。

GCC的用法为gcc [options] file [options]。

-v:版本检查

在命令提示符中输入gcc -v(g++也可以)来检查版本；可能的输出(…表示省略)：

...
COLLECT_GCC=gcc # GCC的编译器类型
...
Target: x86_64-w64-mingw32 # 生成目标
...
Thread model: posix
gcc version 7.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project) # 版本号

这样可以用于确认MinGW已正确配置。

-o:目标文件名

-o用于指定目标文件名，例如g++ -o sample sample.cpp。如果不指定目标文件名，Windows下默认为a.exe，Linux下默认为a.out。

较早版本的GCC允许目标文件名与源文件名相同，源文件会被直接覆盖，没有任何警告。

-Ox:优化选项

这个大家应该很熟悉，不指定默认为-O0，一般优化-O2，用于调试的优化-Og。

在一些版本的GCC中，使用以下代码可以开启部分优化，请不要在NOI系列中使用：
1
#pragma GCC optimize 2

-Wall:开启所有警告

GCC可以发现代码中可能存在的问题，开启-Wall将显示警告。例如非void的函数没有返回值，表达式求值顺序不确定，if语句可能有歧义，运算顺序可能不对，比较有符号和无符号整数等。建议大家开启这个选项。

-std=xxx:指定语言标准

对于C++，常用的有c++98、c++11(c++0x)、c++14，另外还有对应的GNU扩展版本，提供了一些标准不支持的特性。使用-ansi选项在C++中等价于-std=c++98。

-g:生成调试符号

-g可以在目标文件中加入调试符号，以使用GDB等进行调试。注意在调试时，优化选项应为-Og或-O0，-O2会造成调试无法正常进行。

-pg:性能剖析

-pg选项可以使目标文件在执行时生成gmon.out文件，用于性能剖析。

使用gprof file来分析生成的文件，gprof指定-l选项可以显示关于行的性能剖析，但在编译时应同时指定-g选项。

C++98(ANSI C++)

使用const、内联函数、typedef代替#define

这在Effective C++强调，我认为也很重要。#define是C预处理指令，只是简单的做文本模式替换，存在很多问题。

用*#define*定义的常量，在运行时就无法访问，而且没有类型检查，而这些用const都可以实现。

在OI中，最大的数据范围通常是已知的，用常量来定义数组比较方便。

用*#define*定义的宏，有运算顺序上的问题，即使加了括号，也有运算副作用问题，毕竟不是真正的函数；而使用inline一般不会降低性能(假的)，符合函数的逻辑，~~虽然真正内联的函数也不能调试~~。

inline只是建议编译器内联函数，不一定有效，尤其是函数较为复杂时。使用以下代码强制内联：
1
#define inline __attribute__((always_inline))

用*#define*给类型别名，很多情况下可以用typedef或using(C++11)代替。

当然，有时还是要靠*#define*的，比如#define int long long。

另一个例子是使用把iostream改成fstream时，通常我用fin,fout表示输入输出流，可以
1
2
#define cin fin
#define cout fout

使用template

template在OI中似乎很少用，我们一般不会去写像STL的容器，但是模板函数有时还是有用的。

我写过一个static_heap，因为priority_queue使用vector或deque作为容器效率较低，对于OI使用静态数组更加高效。

#include <algorithm>
template <typename T, class Compare = less<T>>
struct static_heap
{
 protected:
T *heap, *p;
Compare cmp;
size_t maxN;
 public:
static_heap(size_t maxN) : maxN(maxN)
{
	p = heap = new T[maxN];
}
~static_heap()
{
	delete[] heap;
}
bool push(const T &val)
{
	if (p == heap + maxN)
		return false;
	*p++ = val;
	std::push_heap(heap, p, cmp);
	return true;
}
const T &top() const
{
	return *heap;
}
bool empty()
{
	return p == heap;
}
bool pop()
{
	if (empty())
		return false;
	std::pop_heap(heap, p--, cmp);
	return true;
}
};

一个例子是I/O优化，用template可以用多种类型的整数，而不用重载函数。

template <typename Int>
inline void read(Int &x)
{
	char c = nextchar();
	for (; isspace(c); c = nextchar())
		;
	x = 0;
	Int sign = 1;
	if (c == '-')
	{
		sign = -1;
		p++;
	}
	for (; isdigit(c); c = nextchar())
		x = x * 10 + c - '0';
	x *= sign;
}

另一个是快速幂，矩阵和整数的版本可以写成一个模板。

使用构造函数代替初始化列表

很多选手喜欢用大括号初始化列表给struct赋值，可能加上类型转换，实际上是不规范的，与编译器相关。

struct edge
{
	int v, w;
};
vector<edge> mat[N];
while (m--)
{
	int a, b, c;
	cin >> a >> b >> c;
	e[a].push_back((edge){b, c});
	//e[a].push_back({b, c});符合C++11
}

可以使用构造函数来实现同样的功能，同时符合C++规范。

struct edge
{
	int v, w;
	//edge() {}数组需要空构造函数
	edge(int v, int w) : v(v), w(w) {}
};
vector<edge> mat[N];
while (m--)
{
	int u, v, w;
	cin >> u >> v >> w;
	e[u].push_back(edge(v, w));
}

使用<algorithm>中的算法

除了大家常用的sort、lower_bound、upper_bound、min、max、swap、unique、nth_element、push_heap、pop_heap、random_shuffle、next_permutation等算法，如果对用法不清楚可以参见cppreference，还有很多有用但是不太常见的算法。很多情况下，用<algorithm>中的比自己手写更加简洁易读。这里介绍我常用的一些。

count

1
2
3

template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_type
    count( InputIt first, InputIt last, const T &value );

count就是统计区间内值出现的次数，复杂度为$\Theta(N)$。不要用于set等容器，使用自带的方法。

copy

1 2	template< class InputIt, class OutputIt > OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

copy用于复制区间，复杂度也是线性的。

fill

template< class ForwardIt, class T >
void fill( ForwardIt first, ForwardIt last, const T& value );
template< class OutputIt, class Size, class T >
void fill_n( OutputIt first, Size count, const T& value );

fill和fill_n用于填充区间，可以用于初始化数组。对于一维数组，使用fill很方便；而多维数组则可以用fill_n，例如

1 2	int f[N][N]; fill_n(&f[0][0], sizeof(f) / sizeof(int), INF);

减少使用<cstring>中的memset，以及其他C标准库的函数。memset其实和Pascal中的fillchar是基本一样的(参数顺序不同，很多初学者会出错)，是基于字节进行填充的。这意味着，对于一个int数组，填充0或-1的结果是正确的，但是1会填充为0x01010101。所以我们一般会用0x3f3f3f3f来代表int的正无穷，其优点在于两个相加不会溢出int。

const int INF = 0x3f3f3f3f;
memset(f, 0x3f, sizeof(f));
...
if(f[n] == INF)
   ...

但是，memset不但可能导致忘记其基于字节而造成错误，还是无类型的，造成以下的错误。
1
2
3
4
5
6
#define clear(_) memset(_, 0x3f, sizeof(_))
...
double dist[N];
//int dist[N];
...
clear(dist);

这一般是最短路里常见的，一开始以为边权为整数，后来发现有小数改成double，但没有改初始化。结果dist就变成了NaN。

fill和fill_n都是有类型的，所以不会允许无效类型的填充。

rotate

1 2	template< class ForwardIt > void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

rotate循环位移区间，使得元素n_first成为新序列中的第一个元素，复杂度$\Theta(N)$。这类似于NOIp2013初赛完善程序的第一题，可以研究一下GCC中的实现。循环右移区间a[1…n]可以写作

1	rotate(a+1, a+n, a+n+1);

merge

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2,
                OutputIt d_first );
template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

merge用于二路归并两个有序的区间，复杂度$\Theta(N+M)$。而inplace_merge用于“原地”归并有序区间[first, middle)和[middle, last)，在内存充足的情况下为$\Theta(N)$，内存不足时$O(N\log N)$。

max_element,min_element

template< class ForwardIt > 
ForwardIt max_element(ForwardIt first, ForwardIt last);
template< class ForwardIt > 
ForwardIt min_element(ForwardIt first, ForwardIt last);

分别返回区间内最大值和最小值的迭代器。

lexicographical_compare

1
2
3

template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2 );

比较两个第一个区间的字典序是否小于第二个。vector和array(C++11)可以直接使用*operator<*等，使用的就是这个函数。

随机

参见C++中的随机数

容器

不太常用的容器：deque,list

deque

支持$O(1)$push_front,pop_front,push_back,pop_back和随机访问，可以参见数列。

list

封装的双向链表，splice方法可以将一个链表接到另一个中的任意位置，复杂度为$O(1)$。

1 2	void splice( const_iterator pos, list& other ); void splice( const_iterator pos, list& other, const_iterator it );

其他函数

tgamma和lgamma

$\Gamma(n)=(n-1)!,n\in N^$，其中tgamma直接计算$\Gamma(n)$，而lgamma*计算$\ln\Gamma(n)$，可以用来估算阶乘。

__builtin_popcount(ll)

计算二进制中1的个数

__builtin_clz(ll)和__builtin_ctz(ll)

分别计算二进制中前导0和后面0的个数，前者可以直接在ST表中用来算log2

C++11

无序关联容器

unordered_(multi)set和unordered_(multi)map容器提供了哈希表，但是只为内置类型和string,bitset等提供了hash<>模板特化，其他不支持的对象需要自己写哈希函数(推荐写仿函数)以及operator==。

auto

自动推断类型，简化表达式。

auto x = 233;
__gnu_pbds::cc_hash_table<int, __gnu_pbds::null_type> h;
auto it = h.find(x);
//__gnu_pbds::cc_hash_table<int, __gnu_pbds::null_type>::point_iterator it = h.find(x);

基于范围的循环

范围可以是数组，可以是STL的序列容器，也可以是大括号的初始化列表

vector<pair<int, int>> mat[N];
//C++11允许模板中出现>>，不认为右移
for (auto v : mat[u])
	if(!vis[v.first])
	//do sth
for (bool b : {false, true})
	//do sth
const int p[] = {2, 3, 5, 7};
for (int i : p)
	cout << i << endl;

Software in OI

数学库

GNU Multiple Precision Arithmetic Library(GMP)

GMP是GNU提供的高精度库(任意精度)，包括整数(mpz)、分数(mpq)和浮点数(mpf,不完善)。需要自己编译源代码，或者使用发行版的二进制文件。

GMP支持C++的接口，提供面向对象，很方便。可以直接用流输入输出，基本运算等。

#include <gmpxx.h>
mpz_class a, b;
cin >> a >> b;
cout << a + b << endl;

前言

C++ in OI

GCC

-v:版本检查

-o:目标文件名

-Ox:优化选项

-Wall:开启所有警告

-std=xxx:指定语言标准

-g:生成调试符号

-pg:性能剖析

C++98(ANSI C++)

使用const、内联函数、typedef代替*#define*

使用template

使用构造函数代替初始化列表

使用<algorithm>中的算法

count

copy

fill

rotate

merge

max_element,min_element

lexicographical_compare

随机

容器

deque

list

其他函数

tgamma和lgamma

__builtin_popcount(ll)

__builtin_clz(ll)和__builtin_ctz(ll)

C++11

无序关联容器

auto

基于范围的循环

Software in OI

数学库

GNU Multiple Precision Arithmetic Library(GMP)

GNU MPFR Library

GCC libquadmath

GDB

代码编辑

Notepad++

Visual Studio Code

Qt Creator

Python

使用const、内联函数、typedef代替#define