C++ in OI

前言

本文分为两个部分,分别总结我所知道的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++也可以)来检查版本;可能的输出(…表示省略):

1
2
3
4
5
6
7
...
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++98c++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*给类型别名,很多情况下可以用typedefusing(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使用vectordeque作为容器效率较低,对于OI使用静态数组更加高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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可以用多种类型的整数,而不用重载函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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赋值,可能加上类型转换,实际上是不规范的,与编译器相关。

1
2
3
4
5
6
7
8
9
10
11
12
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++规范。

1
2
3
4
5
6
7
8
9
10
11
12
13
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>中的算法

除了大家常用的sortlower_boundupper_boundminmaxswapuniquenth_elementpush_heappop_heaprandom_shufflenext_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

1
2
3
4
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 );

fillfill_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

1
2
3
4
5
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

fillfill_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

1
2
3
4
5
6
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

1
2
3
4
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 );

比较两个第一个区间的字典序是否小于第二个。vectorarray(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 );

其他函数

tgammalgamma

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

auto

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

1
2
3
4
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的序列容器,也可以是大括号的初始化列表

1
2
3
4
5
6
7
8
9
10
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++的接口,提供面向对象,很方便。可以直接用流输入输出,基本运算等。

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

但是

GNU MPFR Library

GCC libquadmath

GDB

代码编辑

Notepad++

Visual Studio Code

Qt Creator

Python