CP-template

C++ template files for competitive programming.

1.模板库特点：

兼容性高。

支持 gcc ，clang ，MSVC 等不同编译器，C++11 之后可以使用。
使用方便。

FOR 宏定义？ i64 缩写？编程老手都认识？ No ！本模板库中，不会使用这些花里胡哨的缩写，也不会假定使用者是老手。本模板，让任何码风的人都不会感到不适应。

各个模板之间，尽量减少依赖关系，代码界限分明，在复制粘贴、提交代码时十分清晰便捷。

在最新版本的 TEST 文件夹里，提供了本地运行代码，以及在若干 oj 题目上提交时的代码。
封装性好。

模板往往以类的形式存在，通过成员方法来进行操作；在遇到需要同时建立多个树状数组、多个线段树等问题时，可以轻松适应。
拓展性好。

可以在当前模板的基础上进行再次封装，例如 SqrtTree 就是在 CatTree 的基础上封装而成的。
零成本抽象。

这可以说是最重要的一点，很多写算法模板库的人，写出来的模板非常狭隘，稍微一换场景就会损失效率。比如设计平衡树，结果直接默认写成 map ，那在遇到要以 set 处理的问题时，显然就要白白添加一个没用的 value_type ，这是本模板库不能接受的。本模板库一定会写成既可以拓展为 set 也可以拓展为 map 且均为最佳效率的形式。

2.设计原则：

C++ style, not C style 。

代码格式化:

{ BasedOnStyle: LLVM, UseTab: Never, IndentWidth: 4, TabWidth: 4, BreakBeforeBraces: Attach, AllowShortIfStatementsOnASingleLine: true, IndentCaseLabels: true, ColumnLimit: 0, AccessModifierOffset: -4, NamespaceIndentation: All, FixNamespaceComments: false ,AllowShortCaseLabelsOnASingleLine: true,AllowShortLoopsOnASingleLine: true,AllowShortBlocksOnASingleLine: true}

文件宏命名为：双下划线 + OY + 双下划线 + 模板名全称大写 + 双下划线模板参数命名为：大写每个单词首字母；类命名为：大写每个单词首字母；类外的编译期常量命名为：全大写+下划线分割；类内的编译期常量命名为：全小写+下划线分割；成员变量命名为：m +下划线分割单词成员函数命名为：下划线分割单词静态变量命名为： s +下划线+下划线分割单词形式参数命名为：下划线分割单词
对不保证隐式类型转换成功的场景，使用显式类型转换。

如果代码出现 bug 或者设计问题，欢迎指出

3.优秀的执行效率：

本模板库的数据结构，拥有极其优秀的运行速度。例如：

截止 2024.04.14，最快的 K 短路 https://www.luogu.com.cn/problem/P2483

截止 2024.04.14，最快的虚树 https://www.luogu.com.cn/problem/P2495

截止 2024.04.14，最快的区间排序线段树 https://www.luogu.com.cn/problem/P2824

截止 2024.04.14，最快的带懒更新的可并堆 https://www.luogu.com.cn/problem/P3261

截止 2024.04.14，最快的树上线性基 https://www.luogu.com.cn/problem/P3292

截止 2024.04.14，最快的带懒更新的线段树 https://www.luogu.com.cn/problem/P3373

截止 2024.04.14，最快的类树状数组结构 https://www.luogu.com.cn/problem/P3374

截止 2024.04.14，最快的最近公共祖先在线查询 https://www.luogu.com.cn/problem/P3379

截止 2024.04.14，最快的回滚并查集 https://www.luogu.com.cn/problem/P3402

截止 2024.04.14，最快的乘法逆元 https://www.luogu.com.cn/problem/P3811

截止 2024.04.14，最快的静态区间最值查询 https://www.luogu.com.cn/problem/P3865

截止 2024.04.14，最快的李超线段树 https://www.luogu.com.cn/problem/P4097

截止 2024.04.14，最快的 FMT/FWT https://www.luogu.com.cn/problem/P4717

截止 2024.04.14，最快的 2-SAT https://www.luogu.com.cn/problem/P4782

截止 2024.04.14，最快的类欧几里得算法 https://www.luogu.com.cn/problem/P5170

截止 2024.04.14，最快的回滚 KMP https://www.luogu.com.cn/problem/P5287

截止 2024.04.14，最快的线性基线段树 https://www.luogu.com.cn/problem/P5607

截止 2024.04.14，最快的 Stoer-Wagner算法 https://www.luogu.com.cn/problem/P5632

截止 2024.04.14，最快的动态树 https://www.luogu.com.cn/problem/P5649

截止 2024.04.14，最快的子序列自动机 https://www.luogu.com.cn/problem/P5826

截止 2024.04.14，最快的笛卡尔树 https://www.luogu.com.cn/problem/P5854

截止 2024.04.14，最快的势能线段树 https://www.luogu.com.cn/problem/P6242

截止 2024.04.14，最快的点双连通分量 https://www.luogu.com.cn/problem/P8435

截止 2024.04.14，最快的边双连通分量 https://www.luogu.com.cn/problem/P8436

截止 2024.04.14，最快的最小树形图算法 https://www.luogu.com.cn/problem/U210116

截止 2024.04.14，最快的 GCD 卷积 https://www.luogu.com.cn/problem/U151263

截止 2024.04.14，最快的树状数组 https://www.luogu.com.cn/problem/U187320

截止 2024.04.14，最快的势能线段树 https://uoj.ac/problem/170

截止 2024.04.14，最快的二维树状数组 https://loj.ac/p/133，https://loj.ac/p/134，https://loj.ac/p/135

截止 2024.04.14，最快的二维 ST 表 http://acm.hdu.edu.cn/showproblem.php?pid=2888

由于这样的例子实在太多，故只选最具有代表性的模板列出。

4.力扣输入输出模板使用方法：

目前支持的编译器有 clang / gcc / MSVC 。
包含 LeetcodeIO.h 头文件；
在包含头文件之前，加一行 #define OY_LOCAL 作为本地的标志；（也可以在编译参数里加 -DOY_LOCAL）
在运行目录下放入 in.txt 和 out.txt 作为输入输出文件；如果找不到运行目录，可以随便输出一个字符串，看看 out.txt 生成到了哪里。
Solution 类的使用：需要在第二行注册要运行的成员方法名；
自定义 Class 类的使用：需要在第一行注册类名+构造函数的所有参数类型；需要在第二行注册类名+所有要用到的成员方法名

使用时可以参考两张 png 图片示例。

5.FAQ

我的编程环境非常老旧，看到你的模板库代码花里胡哨的，能运行起来吗？

本模板库现已放宽对语言环境的要求，绝大多数模板， gcc 和 clang 在 C++11 之后均可使用； MSVC 在 C++14 之后均可使用（暂无 C++11 测试环境）。只要你的 C++ 语言标准在 C++11 之后，均可以使用我的模板库。
在很多模板里，看到 MAX_NODE 参数，这是什么意思？

在平衡树、堆、动态开点线段树中，往往需要动态增加结点；往往这些数据结构的不同实例对象还可以互相合并。此时有两种设计方案：用指针表示结点；用数组下标表示结点。如果使用前者方案，指针是全局的概念，所以不同实例对象可以成功合并；但是结点的大小较大，占用空间较多。如果使用后者方案，数组下标是一个针对某个数组的概念，如果两个平衡树的结点是从两个不同的数组里分配的，那么就没有办法进行合并。

经过权衡，采用后者方案：用数组下标表示结点。这就要求存在一个全局的数组，从这个数组里向不同的实例对象分配结点；在合并时，每个结点里保存的左孩子、右孩子等下标可以保持原有的意义，而不至于无意义。

只要看到类内有 s_buffer 的存在，即表示有内存池。
在各种数据结构里，填写的 MAX_NODE 是否越大越好？如果是多组测试，是否每组测试重新构造一个数据结构对象就会触发 $O(MAXNODE)$ 的初始化导致超时？

以下回答针对你的结点类型为平凡类型的情况（无构造函数，无初始值）。

MAX_NODE 相关联的是结点内存池的大小，所以并不会出现每次构造一个数据结构对象，就导致内存池初始化的情况。

MAX_NODE 并非越大越好，当 MAX_NODE 过大时，编译可能会失败。只要编译能通过，那么在此范围内 MAX_NODE 多大都没关系，也不会有任何的时间开销。
我用整数做平衡树结点键值跑得非常快；换成 std::string 做平衡树结点键值，为什么程序突然变得很慢？甚至在很小的样例上都很慢？

由于模板库内使用静态变量做内存池，静态变量某种意义上就是全局变量，所以在程序启动时就会对所有的结点进行初始化。而 std::string 对象即使是空的，也存在初始化代价；如果 MAX_NODE 过大，就会占用很长时间。

一般来说，推荐使用平凡类型作为结点的成员变量。由于 C++ 中，平凡类型的全局变量、静态变量初始化不消耗运行时，所以当你的数据结构的结点类型为平凡类型时，即使开再大的内存池也不会产生一丁点的运行时间。反之，如果你给结点设置了构造、析构，或者给某个成员变量设置了初始值，那么内存池的初始化就会占用时间。
为什么在 oj (主要指 codeforces ) 提交平衡树代码时，提示如下？
```
Can't compile file:
Compiled file is too large
```
首先需要知道，我的平衡树模板通过类似于 MAX_NODE 这样的模板参数控制一个模板最大的数组空间。这种方式产生的静态数组，并非是在运行期在堆上申请的，而是在编译时直接占用程序体积。

而一些平台，例如 codeforces 对生成的程序大小有限制，有时候 MAX_NODE 过大，会生成超出大小限制的程序而无法通过编译。此时问题很好解决，将 s_buffer 从结点数组类型修改为结点指针类型，然后将类外的 s_buffer 初始化改写为 s_buffer = new 【结点类型】[MAX_NODE] 即可。

例如，如果想声明一个普通平衡树，且最多可能插入二百万个元素，则需要声明如下类： OY::AVLMultiset<int, std::less<int>, 2000000> 。当 MAX_NODE = 2000000 时，平衡树因为 MAX_NODE 过大而无法通过 codeforces 编译，则需要做如下修改：

第 195 行修改为
```
static node *s_buf;
```
第 507 行修改为
```
typename Tree<NodeWrapper, MAX_NODE>::node *Tree<NodeWrapper, MAX_NODE>::s_buf = new typename Tree<NodeWrapper, MAX_NODE>::node[MAX_NODE + 1]{};
```
此时即可通过 codeforces 编译。
既然不会反复初始化内存池，那么多组数据之间是否会产生影响？

不会。内存池里的结点只会被使用一次，上一组的数据使用的结点不会在下一组数据里被复用。
线段树只能有求和的功能吗？

本模板库非常重视模板的泛化程度，所以各种数据结构均支持通过传递运算符实现自由的操作。例如，对于线段树来说，可以传递 lambda 定义运算符来重载树中的信息聚合运算；或者通过定义一个结构体，并重载其括号运算符，达到同样的效果。其他的容器也往往如此。
线段树模板参数一大堆，填写起来老是报错？连类型名字都不能完整写出来该怎么办？

为了防止定义各种千奇百怪运算符的使用者在使用模板时，因为无法描述出模板的完整类型名称而困扰，所以特意编写了 make_ 系列函数。如同 std::make_pair 以及 std::make_tuple 一般，只需要填写少量参数即可创建出复杂类型的模板。例如， make_SegTree 可以用来创建线段树；只要打出 make_SegTree 之后跟随 IDE 的智能提示进行相应的填写即可。
用 make_SegTree 可以创建一颗线段树；但是如果我要在 std::vector 里存放十颗线段树，我还是得把类型全称写出来，可是我写不出来，怎么办？

既然用 make_SegTree 可以创建出一颗线段树，那么可以用 using NickName = decltype(make_SegTree<...>(...)); 来捕获这棵树的类型，并给它起个别名。接下来即可用 std::vector<NickName> 的方式存储十颗线段树。
为什么我用 make_STTable<int>(10, std::min<int>) 创建一个最小值表没问题，用 make_STTable<int>(10, std::max<int>) 创建一个最大值表没问题，但是我同时把两句代码写出来，表就出错了？

本模板库的容器，以类型作为两种容器的区别特征；而 std::min<int> 和 std::max<int> 的类型相同，所以会把两个容器视为同一种容器。换句话说，后一个容器传入的函数指针会把前一个容器的函数指针覆盖掉，导致功能紊乱。

一般而言，本模板库不推荐使用函数指针作为操作符的容器；使用匿名函数作为操作符的容器，运行效率更高，也减少了出错的概率。

old-yan / cp-template Goto Github PK

cp-template's Introduction

CP-template

1.模板库特点：

兼容性高。

使用方便。

封装性好。

拓展性好。

零成本抽象。

2.设计原则：

3.优秀的执行效率：

4.力扣输入输出模板使用方法：

5.FAQ

cp-template's People

Contributors

Stargazers

Watchers

Forkers

cp-template's Issues

Recommend Projects

Recommend Topics

Recommend Org