C++11 std骚操作

bits库

<bits/stdc++.h>包括了C++的所有标准库。

<bits/extc++.h>史诗般的外挂,包含了__gnu_pbds的所有内容,包括gp_hash_tablerope等。打死我都不要自己写数据结构了!

类型推导

编译器根据右边的表达式自动判断返回类型。

然而这玩意随便用用就能自损一千,特别好用的地方就是声明迭代器循环变量。

基于范围的for循环

不用写那么多东西,太爽了!但是记得要将循环变量用引用声明,否则随随便便就能TLE。

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int main() {
  vi v = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9};
  for (auto &i : v) {
    cout << i;
  }
  return 0;
}

运行结果:

1145141919

容器去重

<algorithm>里有一个unique函数,会将升序排序的容器中所有的除了第一次出现的元素全部扔掉。

用法:先排序,然后调用unique(start, end);

#include <bits/stdc++.h>
using namespace std;

#define trav(a, A) for (auto &a : A)
#define all(A) A.begin(), A.end()
typedef vector<int> vi;

int main() {
  vi v = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9};
  sort(all(v));
  auto last = unique(all(v));
  v.erase(last, v.end());
  trav(it, v) {
    cout << it << " ";
  }
  return 0;
}

输出结果:

1 4 5 9

bitset

初始化:bitset<length> foo; 构造函数可以用一个数或01字符串做参数。

对象函数:

  • []运算符或test(pos)访问某一位。
  • all()判断是否全为1。
  • any()none()判断是否有1。
  • count()返回所有1的个数
  • set()reset()flip()改变某一位的值。若无参数传入,则对所有的位执行同样的操作。
  • to_string()to_ulong()变成01字符串和整数。

hash

C++11启支持对string类、bitsetvector<bool>的hashing,使用方法如下:

#include <bits/stdc++.h>
using namespace std;

int main() {
  string str1 = "That's good.";
  string str2 = "That's goood.";
  hash<string> h;
  
  cout << h(str1) << endl << h(str2);
  return 0;
}

运行结果:

2177240917276858684
14580988214652125085

模板1-头文件与std库

本文是aunt正在策划的第二代ACM模板的第1部分。由于使用了一些垃圾的网站上扒下来的未测试代码,这篇文章的内容可能很糟糕!

但是他自己写的肯定都很吼

常用函数与头文件

  • scanfprintf,来自<cstdio>
  • powsqrtexp、三角函数等,来自<cmath>
  • memsetmemcpy等内存、字符串操作函数来自<cstring>
  • sortupperbound等算法函数来自<algorithm>
  • rand等来自<ctime>
  • cincout不是很喜欢用!
  • 数据结构:<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 – 变长数组

  • 构造函数
    • vector<int> foo;
  • 迭代器
    • begin&end:正向迭代。
    • rbegin&rend:反向迭代。
  • 容量
    • size:返回大小。
    • empty:判断是否为空。
  • 元素访问
    • [n]at(n):访问某一个元素。
    • frontback:返回首末端元素。
  • 修改
    • push_back:在末尾新增元素,在C++11中建议使用emplace_back
    • pop_back:删除末尾元素;
    • insert:在指定位置后插入元素。第二个变量可以是值,也可以是两个迭代器等等。位置必须使用迭代器。函数返回插入的第一个元素的迭代器。在C++11中建议使用emplace
    • erase危险(易导致段错误) 删除指定位置的元素。函数返回下一个元素的新位置或者是数组末尾。
    • clear:清空数组。

deque – 双向队列

  • 构造函数:
  • 大部分内容与vector一致(包括[]访问方式)。除了deque还可以从头部访问:
    • push_frontemplace_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]->firstfoo[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;