C++ template files for competitive programming.
-
支持
gcc
,clang
,MSVC
等不同编译器,C++11
之后可以使用。 -
FOR
宏定义?u64
缩写?编程老手都认识?No
!本模板库中,不会使用这些花里胡哨的缩写,也不会假定使用者是老手。本模板,让任何码风的人都不会感到不适应。各个模板之间,尽量减少依赖关系,代码界限分明,在复制粘贴、提交代码时十分清晰便捷。
在最新版本的
TEST
文件夹里,提供了本地运行代码,以及在若干oj
题目上提交时的代码。 -
模板往往以类的形式存在,通过成员方法来进行操作;在遇到需要同时建立多个树状数组、多个线段树等问题时,可以轻松解决。
-
可以在当前模板的基础上进行再次封装,例如可持久化并查集就是在可持久化线段树的基础上封装而成的。
-
这可以说是最重要的一点,很多写算法模板库的人,写出来的模板非常狭隘,稍微一换场景就会损失效率。比如设计平衡树,结果直接默认写成
map
,那在遇到要以set
处理的问题时,显然就要白白添加一个没用的value_type
,这是本模板库不能接受的。本模板库一定会写成既可以拓展为set
也可以拓展为map
且均为最佳效率的形式。
-
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
+下划线+下划线分割单词 形式参数命名为:下划线分割单词 -
必要时使用
explicit
修饰单参数构造;必要时使用const
;必要时使用constexpr
修饰编译期方法。 -
C
的函数不使用std
前缀。 -
对不保证隐式类型转换成功的场景,使用显式类型转换。
如果代码出现 bug
或者设计问题,欢迎指出
- 目前支持的编译器有
clang
/gcc
/MSVC
。 - 包含
LeetcodeIO.h
头文件; - 在包含头文件之前,加一行
#define OY_LOCAL
作为本地的标志;(也可以在编译参数里加-DOY_LOCAL
) - 在运行目录下放入
in.txt
和out.txt
作为输入输出文件;如果找不到运行目录,可以随便输出一个字符串,看看out.txt
生成到了哪里。 Solution
类的使用:需要在第二行注册要运行的成员方法名;- 自定义
Class
类的使用:需要在第一行注册类名+构造函数的所有参数类型;需要在第二行注册类名+所有要用到的成员方法名
使用时可以参考两张 png
图片示例。
-
本模板库的数据结构,拥有极其优秀的运行速度。例如:
截止
2023.09.02
,最快的线段树 https://www.luogu.com.cn/problem/P3373截止
2023.09.02
,最快的二维树状数组 https://loj.ac/p/133,https://loj.ac/p/134,https://loj.ac/p/135截止
2023.08.30
,最快的笛卡尔树 https://www.luogu.com.cn/problem/P5854截止
2023.08.30
,最快的李超线段树 https://www.luogu.com.cn/problem/P4097截止
2023.09.01
,最快的二维ST
表 http://acm.hdu.edu.cn/showproblem.php?pid=2888此外,一些数据结构单论速度也是最快,但因为最终用时大于一些别的算法(如离线处理)因而未列入。
-
本模板库非常重视模板的便利程度,对于语言版本较新的使用者,通常来说,可以通过
lambda
定义运算符,作为树/表中的运算符。对于语言版本较旧的使用者,可以通过定义一个结构体,并重载其括号运算符,达到同样的效果。为了防止定义各种千奇百怪运算符的使用者在使用模板时,因为无法描述出模板的类而困扰,所以特意编写了
make_
系列函数。如同std::make_pair
以及std::make_tuple
一般,只需要填写少量参数即可创建出复杂类型的模板。 -
本模板现已放宽对语言环境的要求,
gcc
和clang
在C++11
之后均可使用;MSVC
在C++14
之后均可使用(暂无C++11
测试环境)。 -
为了使各种数据结构避免受到环境下内存分配速度的影响,所以数据结构大多使用了内存池,只要看到有
s_buffer
的存在,即表示有内存池。 -
内存池往往作为类的静态变量存在,整个程序运行期间都不会发生分配和回收动作。由于
C++
中,平凡类型的全局变量、静态变量初始化不消耗运行时,所以当你的数据结构的结点类型为平凡类型时,即使开再大的内存池也不会产生一丁点的运行时间。反之,如果你给结点设置了构造、析构,或者给某个成员变量设置了初始值,那么内存池的初始化就会占用时间。
-
本模板库提供了
FlatTree
,LinkTree
,以及VectorTree
作为树的存储类。此外,如果你有自己的特有的存树方式,库里还有CustomTree
可以存储自定义树,使得我的各种树模板可以应用于你特有的树的存储形式上。 -
本模板库非常重视模板的便利程度。树中的各种回调函数,都可以使用匿名函数;只有涉及到泛型入参时,需要在全局定义模板函数。
为了防止定义各种千奇百怪运算符的使用者在使用模板时,因为无法描述出模板的类而困扰,所以特意编写了
make_
系列函数。如同std::make_pair
以及std::make_tuple
一般,只需要填写少量参数即可创建出复杂类型的模板。 -
本模板现已放宽对语言环境的要求,
gcc
和clang
在C++11
之后均可使用;MSVC
在C++14
之后均可使用(暂无C++11
测试环境)。 -
为了使各种模板避免受到环境下内存分配速度的影响,所以模板大多使用了内存池,只要看到有
s_buffer
的存在,即表示有内存池。 -
内存池往往作为类的静态变量存在,整个程序运行期间都不会发生分配和回收动作。由于
C++
中,平凡类型的全局变量、静态变量初始化不消耗运行时,所以当你的数据结构的结点类型为平凡类型时,即使开再大的内存池也不会产生一丁点的运行时间。反之,如果你给结点设置了构造、析构,或者给某个成员变量设置了初始值,那么内存池的初始化就会占用时间。
-
本模板库一般提供一个可以加边、运行主算法的
Graph
模板;部分文件包含一个Solver
和一个Graph
。前者仅仅进行逻辑运算,而不包含图本身的数据;后者保存了图的点、边数据,并提供方便的接口。简单起见,使用者可以只使用
Graph
及其接口。 -
本模板库非常重视模板的便利程度。树中的各种回调函数,都可以使用匿名函数;只有涉及到泛型入参时,需要在全局定义模板函数。
-
本模板现已放宽对语言环境的要求,
gcc
和clang
在C++11
之后均可使用;MSVC
在C++14
之后均可使用(暂无C++11
测试环境)。 -
为了使各种模板避免受到环境下内存分配速度的影响,所以模板大多使用了内存池,只要看到有
s_buffer
的存在,即表示有内存池。 -
内存池往往作为类的静态变量存在,整个程序运行期间都不会发生分配和回收动作。由于
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]
即可。例如,如果想对大小为
500000
的区间进行最值维护,则需要约10000000
个结点。当MAX_NODE = 10000000
时,ST
表因为MAX_NODE
过大而无法通过codeforces
编译,则需要做如下修改:第
46
行修改为static node *s_buffer;
第
134
行修改为typename Table<Node, MAX_NODE>::node *Table<Node, MAX_NODE>::s_buffer = new typename Table<Node, MAX_NODE>::node[MAX_NODE];
此时即可通过
codeforces
编译。 -
在各种数据结构里,填写的
MAX_NODE
是否越大越好?如果有多个样例,是否每次构造一个数据结构对象就会触发$O(MAXNODE)$ 的初始化导致超时?以下回答针对你的结点类型为平凡类型的情况(无构造函数,无初始值)。
MAX_NODE
相关联的是结点内存池的大小,所以并不会出现每次构造一个数据结构对象,就导致内存池初始化的情况。MAX_NODE
并非越大越好,当MAX_NODE
过大时,编译可能会失败。只要编译能通过,那么在此范围内MAX_NODE
多大都没关系,也不会有任何的时间开销。 -
既然不会反复初始化内存池,那么多组数据之间是否会产生影响?
不会。内存池里的结点只会被使用一次,上一组的数据使用的结点不会在下一组数据里被复用。