STL 与奇技淫巧——考场上的好帮手

vector

vector 方法

• CommonAnts在讨论区中提到 reserve() 函数可以进行缩容，但经查阅 cppreference，此函数只进行扩容而不缩容，只有 shrink_to_fit() 函数会尝试缩容。
• 在 O2 优化下，vector::clear() 对于 trivial 类型（如 int、long long、double 等）为 $O(1)$，对于非 trivial 类型（如 string、vector、结构体等）为 $O(n)$。下面 deque 相同。

迭代器

for(auto it=v.begin();it!=v.end();it++){
    cout<< *it <<"\n";
}

queue

queue 方法

stack

stack 方法

priority_queue

priority_queue 方法

重载运算符

struct Node{
    int x,y,k;

    bool operator<(const Node &other)const{
        return k>other.k;
    }
};

priority_queue<Node> q;

deque

deque 方法

set & multiset

set & multiset 方法

重载运算符

struct Node{
    int x,y,k;

    bool operator<(const Node &other)const{
        return k<other.k;
    }
};

set<Node> q;

迭代器

map

map 方法

重载运算符

struct Node{
    int x,y,k;

    bool operator<(const Node &other)const{
        return k<other.k;
    }
};

map<Node,int> q;

迭代器

unordered_set & unordered_map

unordered_set & unordered_map 方法

自定义哈希

struct Node{
    int x,y,k;
};

struct Node{
    int x,y,k;

    bool operator==(const Node &other)const{
        return x==other.x && y==other.y;
    }
};

struct Node{
    int x,y,k;

    bool operator==(const Node &other)const{
        return x==other.x && y==other.y;
    }
};
struct Hash{
    size_t operator()(const Node &a)const{
        return ((size_t)a.x*1145141u) ^ ((size_t)a.y * 1315423911u);
    }
};
unordered_set<Node,Hash> s;

struct Node{
    int x,y,k;

    bool operator==(const Node &other)const{
        return x==other.x && y==other.y;
    }

    size_t operator()(const Node &a)const{
        return ((size_t)a.x*1145141u) ^ ((size_t)a.y * 1315423911u);
    }
};
unordered_set<Node,Node> s;

bitset

bitset 方法

string

string 方法

STL 函数（包含 GNU）

• sort(st,ed)：对 $[st,ed)$ 进行排序，复杂度 $O(n \log n)$，可以通过重载小于运算符或者传入比较函数自定义排序方式（以下两种方式效果相同）：
  CPP

  bool cmp(int a,int b){return a>b;}
  sort(s+1,s+n+1,cmp);
  

  CPP

  struct Node{
      int a;
      bool operator<(const Node &other)const{
          return a>other.a;
      }
  }s[MN];
  sort(s+1,s+n+1);
  

• lower_bound(st,ed,val)：在有序区间 $[st,ed)$ 中查询第一个 $\geq val$ 的位置，并返回迭代器，复杂度 $O(\log n)$。
• upper_bound(st,ed,val)：同上，不过查询第一个 $> val$ 的位置。
• unique(st,ed)：除去 $[st,ed)$ 的相邻相同项，一般配合 sort() 达到去重效果，复杂度 $O(n)$。
• reverse(st,ed)：翻转 $[st,ed)$ 的内容，复杂度 $O(n)$。
• fill(st,ed,val)：将 $[st,ed)$ 填充为 $val$，复杂度 $O(n)$。
• find(st,ed,val)：返回 $[st,ed)$ 中第一个等于 $val$ 的指针，复杂度 $O(n)$。
• memcpy(target,original,sz)：将以 $original$ 起始 $sz$ 字节的内容复制到 $target$，复杂度 $O(sz)$。
• __lg(x)：返回 $\lfloor \log_2x \rfloor$，与 log2(x) 作用相同，复杂度 $O(1)$。
• __gcd(x,y)：返回 $\gcd(x,y)$，复杂度 $O(\log n)$。
• max(A)/min(A)：返回 $A$ 中的最大值，$|A| \geq 2$，复杂度 $O(|A|)$。下面的代码就可以返回 $5$：
  CPP

  int mx=max({1,1,4,5,1,4});
  

• hypot(x,y)：返回 $\sqrt{x^2+y^2}$，可以简便求出欧几里得距离，复杂度 $O(1)$，精度问题导致常数较大。
• abs(x)/fabs(x)：返回整型/浮点型的 $|x|$，复杂度 $O(1)$。
• floor(x)/ceil(x)：返回浮点型的 $\lfloor x \rfloor$ 或 $\lceil x \rceil$，复杂度 $O(1)$。
• advance(it,num)：将迭代器 $it$ 前进 $num$ 位，复杂度在随机访问迭代器（vector 和 deque）时为 $O(1)$，其他迭代器为 $O(num)$。
• prev(it),next(it)：返回迭代器 $it$ 的前驱/后继。
• stoi(string)：将 string 转化为整数。
• __gnu_cxx::power(x,k)：在 bits/extc++.h 库中，是自带的快速幂，类似 std::sort()，可以通过重载乘法运算符或提供乘法函数来自定义，复杂度 $O(\log n)$。

时间/随机化函数

clock 函数

time 函数

chrono 类

• chrono::steady_clock::now().time_since_epoch().count();

rand 函数

mt19937

uniform_int_distribution

mt19937 wdnmd(time(0));
int rnd=uniform_int_distribution<int>(1,50)(wdnmd);

uniform_real_distribution

mt19937 wdnmd(time(0));
double rnd=uniform_real_distribution<double>(1,50)(wdnmd);

__builtin 函数

位运算相关

安全检查

inline 关键字

1. 省去函数调用开销。
   • 不需要压栈、跳转、返回等操作，可以小幅度降低常数。
2. 可能使编译器进行更多优化。
   • 常量折叠、循环展开。

inline 能用么

怎么让编译器更听话

• inline __attribute__((always_inline))：要求编译器进行内联。在递归等特殊函数时仍可能被拒绝。
• __attribute__((noinline))：要求编译器不进行内联。

由于 CCF 使用的 GCC 版本过于老旧，你可能会碰到这种情况，触发条件比较诡异，比较吃运气，祝大家不碰到这种事情。

常见的卡常操作

• 关闭同步流：关闭同步流可以极大降低 cin 与 cout 的常数：
  CPP

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  

• 使用 \n 换行：将 endl 替换为 \n，可以极大降低 cout 的常数。
• 对于树之类的稀疏图，使用链式前向星而不是 vector 存图。
• 使用快读快写。
• 在快读快写的基础上，将 getchar() 和 putchar() 改为 getchar_unlocked() 和 putchar_unlocked()，约有 $0.5$ 倍的性能提升，Windows 下无法使用。
• 在 Windows 下可以使用 _getchar_nolock() 与 _putchar_nolock()。
• 在常量取模时，使用 unsigned long long 代替 long long 会有约 $1$ 倍的性能提升。
• 选用常数更小/复杂度更低的处理方式，例如将线段树改成树状数组，递归式线段树改为非递归式线段树，欧拉序 LCA 改为 DFS 序 LCA，map 改为 unordered_map 等。
• pb_ds 库的哈希表对比 unordered_map 常数上有提升，可自行查阅相关文章。

常见的其他操作

• linux 下，可以使用 time ./file_name 查看程序运行时间。
• linux 下，可以使用 size ./file_name 查看程序占用内存。
• linux 下，没有使用文件读写时，可以在命令后加上 <input_file_name 和 >output_file_name 实现自定义文件输入输出，例如下面就是一个读入 game.in，输出到 game.out 的，显示程序 game 运行时间的命令：
  CPP

  time ./game <game.in >game.out
  

• linux 下，ccf 的标准编译指令为：g++ file_name.cpp -o file_name -std=c++14 -O2 -static。
• 结尾添加以下参数可以避免很多问题：-fsanitize=address,undefined -Wall -Wextra -Wshadow。
• linux 下，可以使用以下命令取消栈空间限制：ulimit -s unlimited。如果你想要指定栈空间大小，可以使用：ulimit -s sz，其中 $sz$ 单位为 KB。
• linux 下，可以使用 diff 命令比较文件差异（-Bb 可以忽略行末空格与回车）；Windows 下，可以使用 fc 命令比较文件差异。
• 拒绝在任何情况下使用 vector<bool>，史山实现，极易出错。

特别鸣谢

修改记录