本文是aunt正在策划的第二代ACM模板的第1部分。由于使用了一些垃圾的网站上扒下来的未测试代码，这篇文章的内容可能很糟糕！
但是他自己写的肯定都很吼
常用函数与头文件
scanf与printf，来自<cstdio>pow、sqrt、exp、三角函数等，来自<cmath>memset、memcpy等内存、字符串操作函数来自<cstring>sort、upperbound等算法函数来自<algorithm>rand等来自<ctime>cin和cout不是很喜欢用！数据结构：<vector>、<stack>、<set>、<queue>等
include这么多，不如<bits/stdc++.h>（C++11）多方便。
“我为什么不喜欢用<bits/stdc++.h>？就是因为里面关键词太多了。”
——某队友
常见常量定义
“用你马的#define！”
—— Codeforces的出题/验题组是这么认为的。
$e$（自然常数）：const double e = exp(1.0);
$\pi$：const double pi = acos(- 1.0);
$\epsilon$（偏置值）：const double eps = 1e- 6;
$\inf$ ：const int INF = 0x3f3f3f3f;
为什么不能用#define呢？
代码可读性极差
静态检查失效，无法捕捉异常
没有静态常量的CPU处理加速
淦，#define哪来类型安全？？？
常见容器与常见用法
std标准数据结构迭代器的使用方法：for (vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)。但是为什么不用C++11起支持的for (auto &bar : foo)循环体呢？
vector – 变长数组
构造函数
迭代器
begin&end：正向迭代。rbegin&rend：反向迭代。
容量
元素访问
[n]与at(n)：访问某一个元素。front与back：返回首末端元素。
修改
push_back：在末尾新增元素，在C++11中建议使用emplace_back。pop_back：删除末尾元素；insert：在指定位置后插入元素。第二个变量可以是值，也可以是两个迭代器等等。位置必须使用迭代器。函数返回插入的第一个元素的迭代器。在C++11中建议使用emplace。erase：危险（易导致段错误） 删除指定位置的元素。函数返回下一个元素的新位置或者是数组末尾。clear：清空数组。
deque – 双向队列
构造函数：
大部分内容与vector一致（包括[]访问方式）。除了deque还可以从头部访问：
push_front与emplace_front：从头部插入元素。pop_front：从头部删除元素。
stack – 栈
构造函数：stack<int> foo;
empty：判断是否为空。size：返回大小。top：返回栈顶元素。push：压入元素。C++11推荐emplace。pop：弹出元素。
queue – 队列
构造函数：queue<int> foo;
empty：判断是否为空。size：返回大小。front：返回队首元素。back：返回队尾元素。push：压入元素。C++11推荐emplace。pop：弹出元素。
priority_queue – 优先队列
除构造函数不同，其余皆与queue完 全 一 致。常用的构造方法有：
priority_queue <int> pq; 最默认的构造方法，数字越大优先级越高。priority_queue <int, vector<int>, less<int> > pq2; 从大到小。priority_queue <int, vector<int>, greater<int> > pq3; 从小到大。priority_queue <int, vector<int>, cmp() > pq4; 自定义。
注意：比较函数需要结构体定义了比较运算符<或创造重新定义了()运算符的比较结构体。
set – 集合
注意：set元素自动排序（实质是红黑树）。
构造函数：set<int> foo;
迭代器、容量与vector一致。元素不能通过[]或at访问。
操作函数：
find：寻找指定元素，返回它的迭代器或数组末尾。如foo.find(1); 。删除时建议这么做：foo.erase(foo.find(1)); count：返回元素个数。lower_bound：返回主键大于等于参数的第一个元素的迭代器或末尾。upper_bound：返回主键大于等于参数的最后一个元素的迭代器或末尾。
map – 映射
注意：集合的元素都是pair类型，可以用指定pair两元素类型的构造函数创造，但是为什么不用统一的std函数make_pair呢？
构造函数：map<int, string> foo;
迭代器、容量：与vector一致。数组中的所有元素按主键升序排序。下面是插入元素的多种方式：
foo.insert(pair<int, string>(1, "bar")); foo.insert(map<int, string>::value_type(2, "bar2")); foo.insert(make_pair(3, "bar3")); foo[1] = "bar3";
元素访问：map每个元素有两个键值，访问方式为foo[1]- >first与foo[1]- >second。
操作函数同set。
常见库函数与常见用法
数组初始化
马的 又TLE了！
——aunt已经因为下面代码太好用导致无数次TLE……
置零：memset(a, 0, sizeof(a));
置$-1$：memset(a, - 1, sizeof(a));
置$\inf$：memset(a, 0x3f, sizeof(a));
永远记得上面的初始化时间复杂度是$O(n)$的……
结构体定义
You have no class. – C++ to C
class foo{
public:
int bar;
foo() {
bar = 0;
}
foo(int bar) : bar(bar) {
// do nothing
}
bool operator<(const foo &b) const {
return bar < b.bar;
}
}
比较函数与排序
sort、容器使用（升序）：
bool cmp(foo a, foo b) {
return a < b;
}
qsort用：
int cmp(const void *a, const void *b) {
return *(foo *)a < *(foo *)b ? -1 : 1;
}
又难用还跑的慢的函数有存在的必要吗？
据徐臣所说，加上实际考证……sort会根据数据自动选择合适的排序方式，跑的比qsort快的不知道到哪里去了……所以qsort根本没有使用的必要。
常见骚操作
读入过滤
按位读入：scanf("%1d", &foo);
字符过滤（by徐臣）：while(ch < 'a' || ch > 'z') ch = getchar();
字符过滤v2：scanf(" %c", &c);
读入外挂
早就想抄一份了！但是直接扒网上的感觉也不太放心……（未测试代码警告 ）
普通版
inline bool scan_d(int &num) {
char in;
bool IsN = false;
in = getchar();
if (in == EOF) {
return false;
}
while (in != '-' && (in < '0' || in > '9')) {
in = getchar();
}
if (in == '-') {
IsN = true;
num = 0;
} else num = in - '0';
while (in = getchar(), in >= '0' && in <= '9') {
num *= 10, num += in - '0';
}
if (IsN) num = -num;
return true;
}
inline bool scan_lf(double &num) {
char in;
double Dec = 0.1;
bool IsN = false, IsD = false;
in = getchar();
if (in == EOF) return false;
while (in != '-' && in != '.' && (in < '0' || in > '9'))
in = getchar();
if (in == '-') {
IsN = true;
num = 0;
} else if (in == '.') {
IsD = true;
num = 0;
} else num = in - '0';
if (!IsD) {
while (in = getchar(), in >= '0' && in <= '9') {
num *= 10;
num += in - '0';
}
}
if (in != '.') {
if (IsN) num = -num;
return true;
} else {
while (in = getchar(), in >= '0' && in <= '9') {
num += Dec * (in - '0');
Dec *= 0.1;
}
}
if (IsN) num = -num;
return true;
}
豪华版
namespace fastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
//fread->read
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if (p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if (pend == p1) {
IOerror = 1;
return -1;
}
//{printf("IO error!\n");system("pause");for (;;);exit(0);}
}
return *p1++;
}
inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
inline void read(int &x) {
bool sign = 0;
char ch = nc();
x = 0;
for (; blank(ch); ch = nc());
if (IOerror)return;
if (ch == '-')sign = 1, ch = nc();
for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
if (sign)x = -x;
}
inline void read(ll &x) {
bool sign = 0;
char ch = nc();
x = 0;
for (; blank(ch); ch = nc());
if (IOerror)return;
if (ch == '-')sign = 1, ch = nc();
for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
if (sign)x = -x;
}
inline void read(double &x) {
bool sign = 0;
char ch = nc();
x = 0;
for (; blank(ch); ch = nc());
if (IOerror)return;
if (ch == '-')sign = 1, ch = nc();
for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
if (ch == '.') {
double tmp = 1;
ch = nc();
for (; ch >= '0' && ch <= '9'; ch = nc())tmp /= 10.0, x += tmp * (ch - '0');
}
if (sign)x = -x;
}
inline void read(char *s) {
char ch = nc();
for (; blank(ch); ch = nc());
if (IOerror)return;
for (; !blank(ch) && !IOerror; ch = nc())*s++ = ch;
*s = 0;
}
inline void read(char &c) {
for (c = nc(); blank(c); c = nc());
if (IOerror) {
c = -1;
return;
}
}
//getchar->read
inline void read1(int &x) {
char ch;
int bo = 0;
x = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())if (ch == '-')bo = 1;
for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar());
if (bo)x = -x;
}
inline void read1(ll &x) {
char ch;
int bo = 0;
x = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())if (ch == '-')bo = 1;
for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar());
if (bo)x = -x;
}
inline void read1(double &x) {
char ch;
int bo = 0;
x = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())if (ch == '-')bo = 1;
for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar());
if (ch == '.') {
double tmp = 1;
for (ch = getchar(); ch >= '0' && ch <= '9'; tmp /= 10.0, x += tmp * (ch - '0'), ch = getchar());
}
if (bo)x = -x;
}
inline void read1(char *s) {
char ch = getchar();
for (; blank(ch); ch = getchar());
for (; !blank(ch); ch = getchar())*s++ = ch;
*s = 0;
}
inline void read1(char &c) { for (c = getchar(); blank(c); c = getchar()); }
//scanf->read
inline void read2(int &x) { scanf("%d", &x); }
inline void read2(ll &x) {
#ifdef _WIN32
scanf("%I64d",&x);
#else
#ifdef __linux
scanf("%lld",&x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
inline void read2(double &x) { scanf("%lf", &x); }
inline void read2(char *s) { scanf("%s", s); }
inline void read2(char &c) { scanf(" %c", &c); }
inline void readln2(char *s) { gets(s); }
//fwrite->write
struct Ostream_fwrite {
char *buf, *p1, *pend;
Ostream_fwrite() {
buf = new char[BUF_SIZE];
p1 = buf;
pend = buf + BUF_SIZE;
}
void out(char ch) {
if (p1 == pend) {
fwrite(buf, 1, BUF_SIZE, stdout);
p1 = buf;
}
*p1++ = ch;
}
void print(int x) {
static char s[15], *s1;
s1 = s;
if (!x)*s1++ = '0';
if (x < 0)out('-'), x = -x;
while (x)*s1++ = x % 10 + '0', x /= 10;
while (s1-- != s)out(*s1);
}
void println(int x) {
static char s[15], *s1;
s1 = s;
if (!x)*s1++ = '0';
if (x < 0)out('-'), x = -x;
while (x)*s1++ = x % 10 + '0', x /= 10;
while (s1-- != s)out(*s1);
out('\n');
}
void print(ll x) {
static char s[25], *s1;
s1 = s;
if (!x)*s1++ = '0';
if (x < 0)out('-'), x = -x;
while (x)*s1++ = x % 10 + '0', x /= 10;
while (s1-- != s)out(*s1);
}
void println(ll x) {
static char s[25], *s1;
s1 = s;
if (!x)*s1++ = '0';
if (x < 0)out('-'), x = -x;
while (x)*s1++ = x % 10 + '0', x /= 10;
while (s1-- != s)out(*s1);
out('\n');
}
void print(double x, int y) {
static ll mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL,
100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL};
if (x < -1e-12)out('-'), x = -x;
x *= mul[y];
ll x1 = (ll) floor(x);
if (x - floor(x) >= 0.5)++x1;
ll x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];
print(x2);
if (y > 0) {
out('.');
for (size_t i = 1; i < y && x3 * mul[i] < mul[y]; out('0'), ++i);
print(x3);
}
}
void println(double x, int y) {
print(x, y);
out('\n');
}
void print(char *s) { while (*s)out(*s++); }
void println(char *s) {
while (*s)out(*s++);
out('\n');
}
void flush() {
if (p1 != buf) {
fwrite(buf, 1, p1 - buf, stdout);
p1 = buf;
}
}
~Ostream_fwrite() { flush(); }
} Ostream;
inline void print(int x) { Ostream.print(x); }
inline void println(int x) { Ostream.println(x); }
inline void print(char x) { Ostream.out(x); }
inline void println(char x) {
Ostream.out(x);
Ostream.out('\n');
}
inline void print(ll x) { Ostream.print(x); }
inline void println(ll x) { Ostream.println(x); }
inline void print(double x, int y) { Ostream.print(x, y); }
inline void println(double x, int y) { Ostream.println(x, y); }
inline void print(char *s) { Ostream.print(s); }
inline void println(char *s) { Ostream.println(s); }
inline void println() { Ostream.out('\n'); }
inline void flush() { Ostream.flush(); }
//puts->write
char Out[OUT_SIZE], *o = Out;
inline void print1(int x) {
static char buf[15];
char *p1 = buf;
if (!x)*p1++ = '0';
if (x < 0)*o++ = '-', x = -x;
while (x)*p1++ = x % 10 + '0', x /= 10;
while (p1-- != buf)*o++ = *p1;
}
inline void println1(int x) {
print1(x);
*o++ = '\n';
}
inline void print1(ll x) {
static char buf[25];
char *p1 = buf;
if (!x)*p1++ = '0';
if (x < 0)*o++ = '-', x = -x;
while (x)*p1++ = x % 10 + '0', x /= 10;
while (p1-- != buf)*o++ = *p1;
}
inline void println1(ll x) {
print1(x);
*o++ = '\n';
}
inline void print1(char c) { *o++ = c; }
inline void println1(char c) {
*o++ = c;
*o++ = '\n';
}
inline void print1(char *s) { while (*s)*o++ = *s++; }
inline void println1(char *s) {
print1(s);
*o++ = '\n';
}
inline void println1() { *o++ = '\n'; }
inline void flush1() {
if (o != Out) {
if (*(o - 1) == '\n')*--o = 0;
puts(Out);
}
}
struct puts_write {
~puts_write() { flush1(); }
} _puts;
inline void print2(int x) { printf("%d", x); }
inline void println2(int x) { printf("%d\n", x); }
inline void print2(char x) { printf("%c", x); }
inline void println2(char x) { printf("%c\n", x); }
inline void print2(ll x) {
#ifdef _WIN32
printf("%I64d",x);
#else
#ifdef __linux
printf("%lld",x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
inline void println2(ll x) {
print2(x);
printf("\n");
}
inline void println2() { printf("\n"); }
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace fastIO;
