GavinのOI大杂烩

Gavin
  2025-11-17 00:31 2025-11-17 00:31 创建   2025-11-18 23:32:56 2025-11-18 23:32:56 更新   2.3k 字

语法 Tips

const / constexpr

const 代表其修饰的对象是一个常量，而 constexpr 则代表其修饰的对象是一个常量表达式。

常量表达式必须是在编译阶段可识别的，但这不代表它一定会在编译阶段被计算。

没被 constexpr 修饰的表达式也可能是常量表达式。

模板参数必须是常量表达式。

constexpr 包含了 const 的含义，所以以下两份代码是等价的。

1
2
constexpr const int N = 5;
constexpr int N = 5;

define、typedef 与 using

有很多选手使用 define 强开 long long。

1
#define int long long

但是它造成了许多潜在的错误，更明智的方法应该是使用更为现代的 typedef 或 using。

1
2
typedef int i;
using i = int;

template

C++ 泛型的基础。

函数模板定义一般如下所示：

1
2
template<typename T>
template<class T>

其中的 T 接收一个类型，而编译器从模板生成类或函数的过程称为“模板实例化”。

一般情况下，上面的两行代码等价。

而模板中也支持接收非类型参数，最经典的例子就是 bitset 的大小。

1
template<size_t L>

模板同形参一样，可以指定一个默认值。

模板作为模板参数

模板可以是模板参数。

在此示例中，MyClass 有两个模板参数：类型名称参数 T 和模板参数 Arr。

1
2
3
4
5
template<typename T,template<typename U,int I> class Arr>
class MyClass{
    T t;
    Arr<T,10> a;
};

也可以写成以下形式。

1
2
3
4
5
template<typename T,template<typename,int> class Arr>
class MyClass{
    T t;
    Arr<T,10> a;
};

模板特殊化

1
2
3
4
5
template<typename T,typename K>
class MyClass{};

template<typename K>
class MyClass<string,K> {};

不定参数模板

1
2
3
4
5
6
7
8
template<typename T>
void func1(T val){}

template<typename T,typename ...Args>
void func1(T val,Args... args){
    /* do something */
    func1(args...);
}

STL 容器与 iterator

容器通常分为序列式容器、关联式容器与无序（关联式）容器三种。

另有一种容器适配器，基本是对容器进行的包装。

序列式容器

vector

vector 重载了比较运算符，所有运算符均以字典序实现。

默认的 operator[] 不提供越界检查，但 at(pos) 提供。

front() 和 back() 可以直接返回首尾元素的引用。

可以用 begin() 与 end() 获取首尾的迭代器。同样地，使用 rbegin() 和 rend() 获取逆向迭代器。

每个获取迭代器的函数均有其增加一个 c 前缀的变体，用来获取只读迭代器。

resize() 会直接改变当前容器的大小，而 reserve() 仅会预先分配空间。capacity() 可以返回当前分配了多少个空间。

clear() 可以清除所有元素，但不会释放空间。可以用 shrink_to_fit() 释放所有未使用的空间。

shrink_to_fit() 是一个非强制性的请求，要求将 capacity() 减小到 size()。该请求是否被实现取决于具体实现。

swap() 让此容器与另一容器交换，该操作实际上是常数级别的。

push_back() 均摊为常数复杂度，但最坏实际上是线性的。

vector 在当前长度大于已经分配的长度时，会新分配一个的空间并且将原数据拷贝至新位置。这个操作的渐进复杂度是的，但均摊下来为。

vector 提供了 vector<bool> 的特化，但实际上并没有用处，请使用 bitset。

array

本质上就是 C-array 的封装。

值得注意是，有一个 fill() 成员方法用于填充所有元素。

std::swap() 的交换是的，并非传统的常数级复杂度。

deque

双端队列，提供了常数级别的随机访问。

与 vector 相比，没有 reserve() 和 capacity()，但仍然有 shrink_to_fit()。

deque 使用一小块连续空间存储指向每个缓冲区头尾的指针，每个缓冲区则是一块较大的连续空间，存储真正的数据。

list

双向链表，提供了线性复杂度的随机访问与常数复杂度的插入以及删除。

由于其是链表，随机访问需要使用迭代器。

因为一些 STL 算法需要随机访问迭代器，list 提供了特别的实现。这些算法有 splice()、remove()、sort()、unique()、merge() 等。

forward_list

单向链表，比 list 减小了空间开销。其余与 list 基本一致，唯一不同的是只提供单向迭代器。

关联式容器

set

set 含有键值类型对象的已排序集，搜索、移除和插入拥有对数复杂度。其内部实现通常采用红黑树。

与数学集合相同，其元素拥有唯一性，若要使用有相同元素的集合，请转到 multiset。

set 提供了 erase(start,last)，可以删除间的所有元素。

insert 函数的返回值类型为 pair<iterator,bool>，其中 iterator 是一个指向所插入元素（或者是指向等于所插入值的原本就在容器中的元素）的迭代器，而 bool 则代表元素是否插入成功，由于 set 中的元素具有唯一性质，所以如果在 set 中已有等值元素，则插入会失败，返回 false，否则插入成功，返回 true。map 中的 insert 也是如此。

set 提供了自带的 lower_bound() 与 upper_bound() 函数，而 algorithm 中的两个函数在 set 上是的。

set 没有提供自带的 nth_element()，而 algorithm 中的 nth_element() 复杂度为。

如果需要查找第大，请使用 pb_ds 或手写平衡树。

set 默认情况下使用 < 作为比较函数。若希望自定义比较，需要定义一个类，并在类中重载 () 运算符。

1
2
3
4
5
6
7
struct cmp{
    bool operator(int a,int b){
        return a>b;
    }
};

set<int,cmp> s;
map

map 是有序的键值对容器，其搜索、删除和插入操作拥有对数复杂度。

map 中的键具有唯一性，multimap 允许多个元素拥有同一键。

可以直接用 operator[] 访问 map 中的元素。但需要注意的是，若通过此方法访问的元素不存在，会通过默认构造函数（如果有的话）插入一个新元素。

因此，当访问过于频繁时，容器中会出现大量无意义元素，影响效率。所以，推荐使用 find() 来查找。

insert() 可以通过提供一个 pair 直接插入一个键值对。

count() 操作的复杂度是的。

对 map 的迭代器解引用后，得到的是 pair<Key,T> 的键值对。

无序关联式容器

todo

容器适配器

迭代器

STL 算法

运算符优先级

优先级运算符描述结合性可重载
1a::b作用域解析符→不可重载
2++后自增运算符可重载
--后自减运算符可重载
type() type{}强制类型转换可重载
()函数调用可重载
[]数组数据获取可重载
.对象型成员调用不可重载
->指针型成员调用可重载
3++前自增运算符←可重载
--前自减运算符可重载
+正号可重载
-负号可重载
!逻辑取反可重载
~按位取反可重载
(type)C 风格强制类型转换可重载
*指针取值可重载
&值取指针可重载
sizeof返回类型内存不可重载
new动态元素内存分配可重载
new []动态数组内存分配可重载
delete动态析构元素内存可重载
delete []动态析构数组内存可重载
4.*类对象成员引用→不可重载
->*类指针成员引用可重载
5*乘法可重载
/除法可重载
%取余数（模运算）可重载
6+加法可重载
-减法可重载
7<<位左移可重载
>>位右移可重载
8<=>三路比较运算符可重载
9<小于可重载
<=小于等于可重载
>大于可重载
>=大于等于可重载
10==等于可重载
!=不等于可重载
11&位与运算可重载
12^位异或运算可重载
13|位或运算可重载
14&&逻辑与运算可重载
15||逻辑或运算可重载
16? :条件运算符←不可重载
throw异常抛出不可重载
=赋值可重载
+=加赋值运算可重载
-=减赋值运算可重载
*=乘赋值运算可重载
/=除赋值运算可重载
%=模赋值运算可重载
<<=位左移赋值运算可重载
>>=位右移赋值运算可重载
&=位与赋值运算可重载
^=位异或赋值运算可重载
|=位或赋值运算可重载
17,逗号分隔符→可重载

文件操作

C++ 风格的格式化输出

算法专题

数据结构

复杂度分析

字符串

图论

Tricks

  • 标题: GavinのOI大杂烩
  • 作者: Gavin
  • 创建于 : 2025-11-17 00:31:00
  • 更新于 : 2025-11-18 23:32:56
  • 链接: https://gavin-blog.pages.dev/2025/gavinのoi大杂烩/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
GavinのOI大杂烩
  1. 语法 Tips
    1. const / constexpr
    2. define、typedef 与 using
    3. template
    4. STL 容器与 iterator
    5. STL 算法
    6. 运算符优先级
    7. 文件操作
    8. C++ 风格的格式化输出
  2. 算法专题
  3. 数据结构
  4. 复杂度分析
  5. 字符串
  6. 图论
  7. Tricks