竞赛中的 C++ 补充语法

学过结构体后，已经可以把点的坐标、选手的成绩、边的端点等数据放在一起。继续阅读算法代码时，还会遇到成员函数、构造函数、lambda 表达式，以及去重、集合和映射等 STL 用法。它们主要解决两个问题：怎样把相关的数据与操作组织清楚，以及怎样更简洁地表达算法。

一、从结构体到类

1. 结构体也可以包含函数

一个点除了保存横纵坐标，还可以提供计算平方长度的操作。设坐标绝对值不超过 $10^9$，平方长度最多为 $2\times 10^{18}$，需要使用 long long。

struct Point
{
    int x, y;

    long long len2() const
    {
        return 1LL * x * x + 1LL * y * y;
    }
};

其中，$x, y$ 是数据成员，len2 是成员函数。创建一个对象后，可以通过点号访问它们：

Point p{3, 4};
cout << p.x << ' ' << p.len2() << '\n';

输出为 $3$ 和 $25$。调用 p.len2() 时，函数体里的 $x, y$ 指的是对象 $p$ 的坐标；另一个对象调用同一成员函数时，使用的是另一个对象的数据。

成员函数末尾的 const 表示该函数不能通过当前对象修改普通数据成员。因此，只读对象也可以调用它。它与“返回值是常量”无关。

2. 类、对象与访问权限

类定义一种类型，对象是这种类型的具体实例。上面的 Point 就是类类型，$p$ 就是对象。C++ 的结构体同样属于类类型，并不是只有使用 class 才能编写成员函数。

对于这里讨论的用法，struct 与 class 的主要区别是默认访问权限：前者的成员默认公开，后者默认私有；继承时的默认权限也分别是公开和私有。两者都支持成员函数、构造函数和运算符重载。

访问说明符	含义
public	类外可以访问
private	普通类外代码不能直接访问
protected	与派生类访问有关

例如，将点改写为下面的形式，公开成员的用法仍然相同：

class Point
{
  public:
    int x, y;
};

若删掉公开访问说明符，普通类外代码就不能直接读写 $x, y$。访问权限限制的是代码如何使用成员，不会自动改变算法的时间复杂度。

3. 构造函数负责初始化

构造函数在对象创建时执行，函数名与类名相同，没有返回类型。下面仍使用结构体，说明构造函数并不专属于 class：

struct Point
{
    int x, y;

    Point() : x(0), y(0)
    {
    }

    Point(int a, int b) : x(a), y(b)
    {
    }
};

冒号后面是成员初始化列表，表示用 $a, b$ 初始化 $x, y$。两种构造函数分别对应无参数和有参数的创建方式：

Point p;
Point q(3, 4);
Point r{5, 6};

此时 $p$ 为原点，$q$ 的坐标为 $(3, 4)$，$r$ 的坐标为 $(5, 6)$。这里的花括号创建会调用匹配的构造函数；第一小节没有自定义构造函数的点使用的是聚合初始化。

如果只定义了带两个参数的构造函数，编译器不会再自动补出无参构造函数。此时直接创建无参数对象，或者创建需要默认初始化每个元素的对象数组，都会遇到编译错误。

成员实际按照在类中的声明顺序初始化，而不是按照初始化列表的书写顺序。将两处顺序写成一致，可以减少误解。没有自定义构造过程时，也可以直接给数据成员写默认值，例如将坐标声明为初值均为 $0$ 的两个整数。

二、什么是 OOP？

面向对象程序设计（Object-Oriented Programming，OOP）把相关的数据和操作组织到对象中。竞赛里最直接的用途是封装数据结构：对象保存自己的状态，外部通过约定的操作使用它。

1. 用一个栈理解封装

栈维护一个序列，只能在末尾加入或删除元素。用数组实现时，需要同时维护存储数组和栈顶位置。如果在主程序中到处修改栈顶位置，就容易出现“位置已经改变，元素却没有写入”的错误。

下面的完整程序将它们放进同一个类中。示例约定同时保存的元素不超过 $100000$ 个，且只在非空时读取或弹出栈顶。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

class Stack
{
  private:
    int a[N];
    int tt;

  public:
    Stack() : tt(0)
    {
    }

    void push(int x)
    {
        a[++tt] = x;
    }

    void pop()
    {
        --tt;
    }

    int top() const
    {
        return a[tt];
    }

    bool empty() const
    {
        return tt == 0;
    }
};

Stack s, t;

int main()
{
    s.push(3);
    s.push(7);
    t.push(5);
    cout << s.top() << ' ' << t.top() << '\n';
    s.pop();
    cout << s.top() << '\n';
    return 0;
}

程序先输出 $7$ 和 $5$，再输出 $3$。对象 $s, t$ 分别拥有自己的数组和栈顶位置，修改其中一个不会改变另一个。这里使用全局对象，避免将较大的数组对象放入函数的局部栈空间。

栈的不变量是：$tt$ 等于当前元素数量，有效元素位于 $a[1]$ 至 $a[tt]$。压栈时先增加数量并写入元素，弹栈时减少数量。将这两种操作集中在成员函数中，便于检查不变量是否始终成立。

封装不会自动检查边界。超过容量时压栈、在空栈上弹栈或读取栈顶，都违反了本例的使用约定。各操作的时间复杂度仍为 $O(1)$，每个对象占用 $O(N)$ 空间。

实际解题时，单个栈可以直接使用全局数组，也可以使用标准库的栈；需要多份独立状态或反复复用一组操作时，封装会更有价值。成员函数的意义在于让状态与操作对应清楚。

也就是说，在数组容量和操作相同的前提下，这里的封装不会改善时间与空间复杂度，主要作用是组织代码。

2. 继承与多态

OOP 常见的三个概念是封装、继承和多态。

概念	基本含义
封装	把相关数据与操作组织在一起，并约定访问方式
继承	在已有类的基础上定义派生类
多态	同一接口可以对应不同实现

公开继承的声明形如：

struct State
{
    int x, y;
};

struct Node : public State
{
    int d;
};

派生类 Node 的对象包含基类的坐标信息，并增加距离成员 $d$。但在普通搜索题里，直接用一个结构体保存 $x, y, d$ 通常更清楚，没必要仅为少写两个成员引入继承。这里描述的是类型之间的继承关系，不是树上两个节点之间的父子关系。

函数重载、运算符重载和模板可以在编译期根据类型选择实现。通过基类引用或指针调用虚函数，则可以根据对象实际类型在运行时选择实现；相关代码通常会出现 virtual 和 override。只在两个类里写同名函数，不会自动得到这种运行时分派。

基础算法的数组、图、堆和动态规划状态通常不需要复杂的继承体系。

3. 虚函数与重写检查

virtual 用于声明虚函数。通过基类引用或指针调用虚函数时，可以执行对象实际类型对应的实现。override 写在派生类成员函数的声明中，要求编译器检查它确实重写了基类的某个虚函数；如果函数名、参数或末尾的常量限定等不匹配，编译器会报错。

下面用“查询状态的代价”演示这种调用方式：

struct State
{
    virtual int cost() const
    {
        return 0;
    }
};

struct Node : public State
{
    int d;

    Node(int x) : d(x)
    {
    }

    int cost() const override
    {
        return d;
    }
};

void print_cost(const State &s)
{
    cout << s.cost() << '\n';
}

函数参数写的是基类引用，但它可以引用派生类对象：

State s;
Node t(7);
print_cost(s);
print_cost(t);

两次调用分别输出 $0$ 和 $7$。第二次调用时，基类引用实际绑定到 $t$，所以执行派生类中的代价函数。

如果同时去掉基类中的 virtual 和派生类中的 override，通过这个基类引用调用的将是基类版本，两次都输出 $0$。如果只去掉前者而保留后者，则编译器会报错，因为派生类函数没有重写基类虚函数。反过来，只省略 override 不会取消已经形成的重写关系，但会失去这项明确的编译检查。

本例直接创建对象并通过引用调用，不涉及动态分配。竞赛中读懂这两个关键字即可，普通的状态记录不必为此加入虚函数。

三、运算符重载

对整数排序时，小于号的含义已经确定。对于自定义记录，需要明确比较哪些字段。既可以向排序函数传入比较函数，也可以在类型中定义小于运算符。

设每条记录包含分数 $s$ 和编号 $id$，要求分数高的在前，分数相同则编号小的在前：

struct Node
{
    int s, id;

    bool operator<(const Node &b) const
    {
        if (s != b.s)
        {
            return s > b.s;
        }
        return id < b.id;
    }
};

表达式 $a<b$ 会调用左侧对象的比较函数，将右侧对象作为参数 $b$。这里的小于号定义的是记录的排列顺序，因此分数越大，反而越应该“排在前面”。

参数中的引用避免复制右侧记录，参数前的 const 表示不通过该参数修改右侧记录；函数末尾的 const 表示不通过当前对象修改左侧记录。

若已有包含 $n$ 条记录的数组 $a$，有效下标从 $1$ 开始，就可以直接排序：

sort(a + 1, a + n + 1);

比较规则必须满足严格弱序。实际编写时至少要检查：记录不能排在自身前面；如果 $a$ 排在 $b$ 前、$b$ 排在 $c$ 前，那么 $a$ 应排在 $c$ 前；比较意义下的等价关系也应具有传递性。按固定字段依次比较通常容易满足这些要求。将最后的严格小于改成小于等于，会让一条记录与自身比较时返回真，从而破坏规则。

小于运算符也会影响默认的有序集合和优先队列。默认优先队列取出的是按该顺序最大的元素，不一定是排序后最前面的元素；使用时应单独检查堆顶应当是谁。同一类型在不同地方需要不同顺序时，使用独立比较函数或 lambda 通常更合适。

四、联合体：多个成员共用存储

联合体使用 union 定义。它与普通结构体的关键区别是：非静态数据成员共用存储，同一时刻至多有一个活跃成员。其空间足以容纳最大的成员，并满足对齐要求，不能简单按各成员大小相加。

union Value
{
    int x;
    double y;
};

Value v;
v.x = 7;
cout << v.x << '\n';
v.y = 2.5;
cout << v.y << '\n';

写入 $v.y$ 后，不能再把 $v.x$ 当作之前保存的整数来读取。这也不是把整数自动转换成浮点数；需要数值转换时，应直接使用语言提供的类型转换。

本课程只要求了解基本概念，不安排必须使用联合体的题目。若若干字段需要同时保存，仍应使用普通结构体。

五、引用、类型推导与简洁遍历

1. 引用决定是在操作原对象还是副本

引用是已有对象的别名。读取一个较大的对象时，常使用只读引用参数；需要修改实参时，使用普通引用参数。

void add(int &x)
{
    ++x;
}

int get_len(const string &s)
{
    return static_cast<int>(s.size());
}

调用第一个函数会修改传入的整数；第二个函数不会复制整段字符串，也不能通过参数修改字符串。此例假设字符串长度可用 int 表示，显式转换只处理长度类型的边界。

引用所指对象必须仍然存在。不能返回局部普通变量的引用；容器扩容或删除元素后，原来的引用也可能失效。引用减少复制的前提是被引用对象保持有效。

2. 类型别名与类型推导

类型别名给已有类型起一个短名称，并不会创建新的整数类型：

using ll = long long;
using pii = pair<int, int>;

auto 则根据初始化表达式推导变量类型。推导在编译期完成，变量之后不能随意改变类型。

int n = 100000;
auto x = n;
auto y = 1LL * n * n;

其中 $x$ 是 int，$y$ 是 long long。类型推导不会修复表达式中的整数溢出：如果乘法两侧都是普通整数，乘法会先按原类型计算，之后才谈得上保存结果。

对于迭代器或较长的容器元素类型，使用类型推导可以减少重复。对于需要明确数值范围的答案变量，直接写出整数类型往往更清楚。

3. 范围循环的三种常见写法

vector<int> a = {1, 2, 3};

for (auto x : a)
{
    ++x;
}

for (auto &x : a)
{
    ++x;
}

for (const auto &x : a)
{
    cout << x << ' ';
}

第一段循环修改的是每次复制出来的整数，原容器不变。第二段通过引用修改原元素，容器变成 $2, 3, 4$。第三段只读访问，输出这三个数。

形式	是否复制普通元素	是否可以通过循环变量修改原元素
auto	是	否
auto&	否	是，前提是元素本身可修改
const auto&	否	否

范围循环遍历整个对象。对于容量为 $N$、但仅使用前 $n$ 个位置的原生数组，范围循环仍会访问全部 $N$ 个位置，此时应保留下标循环。也不要一边范围遍历一个动态数组，一边向同一个动态数组追加元素。

六、lambda：把短函数写在使用位置

1. 排序时直接写比较规则

lambda 表达式可以在当前位置创建一个可调用对象。对只有一次使用、逻辑很短的比较规则，可以直接写在排序调用中。

下面假设 $a[1]$ 至 $a[n]$ 已保存前文的分数与编号记录：

sort(a + 1, a + n + 1,
     [](const Node &x, const Node &y)
     {
         if (x.s != y.s)
         {
             return x.s > y.s;
         }
         return x.id < y.id;
     });

方括号是捕获列表，圆括号是参数列表，花括号是函数体。本例不需要使用外部局部变量，所以捕获列表为空。返回值类型可以从返回语句推导为布尔类型。

这与单独编写比较函数表达的是同一条排序规则，也同样必须满足严格弱序。lambda 改变了代码的组织位置，不会让错误的比较关系变得正确。

2. 捕获外部局部变量

二分答案中的判断函数往往要使用当前题目的参数。短小的判断逻辑可以写成局部 lambda。下面只演示捕获差别：

int k = 3;
auto f = [k](int x)
{
    return x >= k;
};
auto g = [&k](int x)
{
    return x >= k;
};
k = 5;
cout << f(4) << ' ' << g(4) << '\n';

输出为 $1$ 和 $0$。按值捕获保存创建 lambda 时的值，因此 $f$ 使用 $3$；按引用捕获访问原变量，因此 $g$ 使用修改后的 $5$。

捕获形式	含义
空捕获列表	不捕获外部局部变量
按值捕获某个变量	保存该变量在创建时的副本
按引用捕获某个变量	通过引用使用原变量
[=]	默认按值捕获所需的外部局部变量
[&]	默认按引用捕获所需的外部局部变量

全局变量不需要捕获。按引用捕获的 lambda 不能在被引用的局部变量销毁后继续访问它。只在当前函数内立即使用的短函数比较容易保证这一点；需要长期保存的函数对象则应单独检查生命周期。

七、STL 中的去重、集合与映射

STL 提供了常用的容器与算法。对于“整理出不同的数”“动态维护已经出现的数”“统计每个数的次数”等问题，可以根据所需操作选择不同工具。

1. 先认识迭代器与左闭右开区间

迭代器表示容器中的位置。对于普通数组，指针就可以充当迭代器；对于容器，通常用起始和结束成员函数获得迭代器。

vector<int> a = {3, 5, 8};
for (auto it = a.begin(); it != a.end(); ++it)
{
    cout << *it << ' ';
}

起始迭代器指向第一个元素，结束迭代器表示最后一个元素之后的位置，不指向可读取的元素。解引用 *it 可以访问当前位置的元素，递增迭代器则移到下一个位置。空容器的起始迭代器与结束迭代器相等。

许多算法使用左闭右开区间 $[first, last)$。例如，原生数组中下标 $1$ 至 $n$ 对应起点 $a+1$、终点 $a+n+1$。结束位置不参与处理，空区间则满足起点等于终点。

2. 去重：排序后使用 unique

unique 位于头文件 <algorithm>，它把每一段连续相等的元素压缩为一个，将保留的元素移动到区间前部，并返回新的逻辑结束位置。它不会自动缩短容器，也不会删除不相邻的重复值。

例如，序列 $1, 1, 2, 1, 1$ 直接去重后，有效前缀为 $1, 2, 1$，最后的 $1$ 仍然保留。若目标是得到全部不同的数，通常先排序，让相同值连续出现。

对于下标从 $1$ 开始的原生数组，可以这样写：

int a[] = {0, 3, 1, 3, 2, 1, 2};
int n = 6;
sort(a + 1, a + n + 1);
int m = unique(a + 1, a + n + 1) - (a + 1);
for (int i = 1; i <= m; ++i)
{
    cout << a[i] << ' ';
}

排序后得到 $1, 1, 2, 2, 3, 3$，去重后的有效前缀为 $1, 2, 3$，所以 $m=3$。返回位置减去处理区间的起点，才是保留元素的数量；起点是 $a+1$，因此不能只减 $a$。

原数组的容量没有变化。新逻辑结束位置之后的元素不属于去重结果，不应继续按原来的 $n$ 个元素输出，也不能依赖它们恰好保留什么值。排序需要 $O(n\log n)$ 时间，去重本身需要 $O(n)$ 时间。

对于动态数组，还需要删除逻辑结束位置之后的元素，使容器长度与结果一致：

vector<int> a = {3, 1, 3, 2, 1, 2};
sort(a.begin(), a.end());
auto it = unique(a.begin(), a.end());
a.erase(it, a.end());
cout << a.size() << '\n';

此时容器内容为 $1, 2, 3$，长度为 $3$。最后两步也常合并为：

a.erase(unique(a.begin(), a.end()), a.end());

这种写法仍要求相同值已经相邻，合并代码不会替代排序。排序加去重适合一次性整理数据、提取不同坐标和离散化；若题目要求保留首次出现顺序，就不能直接排序原序列。

3. set：动态维护有序且不重复的元素

set 位于头文件 <set>。默认的整数集合按从小到大的顺序保存元素，同一个整数重复插入只保留一份。

set<int> s;
s.insert(5);
s.insert(2);
s.insert(5);
cout << s.size() << '\n';
for (int x : s)
{
    cout << x << ' ';
}
cout << '\n';

程序先输出 $2$，再输出 $2, 5$。遍历顺序由集合的比较规则决定，与插入顺序无关。这里的动态维护表示可以交替执行插入、删除与查找，不必每次修改后重新排序。

操作	含义
s.insert(x)	插入元素，已有相同值时不增加副本
s.count(x)	判断是否存在，结果为 $0$ 或 $1$
s.find(x)	返回对应迭代器，不存在则返回结束迭代器
s.erase(x)	按值删除，返回删除数量 $0$ 或 $1$
s.size()	返回当前不同元素的数量
s.empty()	判断是否为空

设当前有 $k$ 个元素，普通单元素插入、查找和按值删除的时间复杂度为 $O(\log k)$，这里按 $k\ge 2$ 表述；小规模时为常数开销。集合对“重复”的判断依据比较关系：两个元素互相都不排在对方前面，就被视为等价。使用自定义记录时，比较函数遗漏字段可能让不同记录被当作同一个键。

有序集合还可以寻找数值边界：

set<int> s = {2, 5, 8};
auto it = s.lower_bound(4);
if (it != s.end())
{
    cout << *it << '\n';
}
auto jt = s.upper_bound(5);
if (jt != s.end())
{
    cout << *jt << '\n';
}

前者寻找第一个不小于 $4$ 的元素，得到 $5$；后者寻找第一个大于 $5$ 的元素，得到 $8$。如果没有满足条件的元素，就返回结束迭代器，读取前必须检查。两个成员函数都具有对数时间复杂度。

查找严格小于 $x$ 的最大值时，可以先求集合的下界；只有结果不等于起始迭代器时，才能向前移动一次。读取最小值前也要先判断集合非空。

集合不支持按下标访问，迭代器不能直接加减任意整数，也不能用两个迭代器相减求排名。查找边界时优先使用集合自己的成员函数；对集合使用通用二分查找算法，虽然比较次数是对数级，迭代器移动仍可能达到线性次数。

集合中的元素不能通过迭代器直接修改，因为修改可能破坏排序关系。需要改值时，先删除旧值，再插入新值。若题目只需要一次性排序去重，数组加去重算法已经足够；需要在线判断是否出现、插入删除或寻找前驱后继时，再考虑集合。

4. map：保存键与值的对应关系

map 位于头文件 <map>，每个键对应一个值。它可以用于保存“数值对应出现次数”“名字对应编号”等关系。键不重复，默认按键从小到大排列；值可以重复，也不会决定遍历顺序。

下面统计一组整数的出现次数：

int a[] = {3, 1, 3, 2, 1, 3};
map<int, int> cnt;
for (int x : a)
{
    ++cnt[x];
}
for (const auto &p : cnt)
{
    cout << p.first << ' ' << p.second << '\n';
}

输出为：

1 2
2 1
3 3

遍历得到的每个元素是一个键值对，p.first 表示键，p.second 表示对应值。这里按只读引用遍历，直接访问这两个成员即可。

当键 $x$ 不存在时，下标访问 $cnt[x]$ 会插入新键，并将对应整数初始化为 $0$，然后才执行后续操作，所以递增可以直接用于计数。当键已存在时，下标访问的是原来的值。

这种自动插入也容易造成误用：仅想查询一个数出现了几次时，下标访问可能使映射增加新元素。只读查询应使用查找函数：

map<int, int> cnt;
cnt[3] = 2;
int x = 7;
auto it = cnt.find(x);
if (it != cnt.end())
{
    cout << it->second << '\n';
}
else
{
    cout << 0 << '\n';
}
cout << cnt.size() << '\n';

程序先输出 $0$，再输出 $1$，因为查询不存在的键没有改变映射大小。箭头访问 it->second 表示读取迭代器所指键值对的第二项。

操作	含义
$cnt[x]$	访问对应值，不存在时插入默认值
cnt.find(x)	查找键，不存在时返回结束迭代器
cnt.count(x)	判断键是否存在，结果为 $0$ 或 $1$
cnt.erase(x)	删除这个键及其对应值
cnt.size()	返回键的数量，不是所有计数的总和

映射本身只维护键是否存在，并不知道某个值被用作“出现次数”。因此，cnt.count(x) 不是读取 $x$ 出现的次数；即使把 $cnt[x]$ 减为 $0$，这个键也不会自动消失。若需要只保留正计数的键，应在减到零后显式删除。

若需要修改遍历到的值，可以使用普通引用遍历并修改第二项；键本身不能通过迭代器修改。按键查找、插入、下标访问和按键删除均为对数时间复杂度。对于 $n$ 个整数，上面的统计与输出总时间为 $O(n\log n)$，保存不同键的空间为 $O(n)$。

5. 根据问题选择工具

需求	常用选择	需要注意
一次性得到所有不同值	排序加 unique	更新有效长度，会改变原有顺序
动态维护是否出现，并按值查找边界	set	重复插入不会增加数量
为每个不同键保存计数、编号等信息	map	下标查询可能插入新键
数值范围很小且需要频繁计数	普通计数数组	先确认下标范围与内存允许

例如，若所有数都在 $0$ 至 $10^5$ 之间，数组可以直接按值计数，单次操作为 $O(1)$；若数值很大但不同值数量较少，可以用映射只保存实际出现的键。容器的选择应由数据范围和所需操作决定。

八、把这些语法放进一道排序题

给出 $n$ 条记录，每条记录包含成绩和耗时，编号按输入顺序从 $1$ 开始。要求成绩高的在前，成绩相同则耗时少的在前，两者都相同则编号小的在前。设 $1\le n\le 10^5$，成绩与耗时均为不超过 $10^9$ 的非负整数。

这道题需要把一条记录的三个字段一起保存，并明确三层比较规则。结构体负责组织数据，lambda 表达式负责本次排序规则，输出时直接访问记录的成员。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

struct Node
{
    int s, t, id;
};

int n;
Node a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &a[i].s, &a[i].t);
        a[i].id = i;
    }
    sort(a + 1, a + n + 1,
         [](const Node &x, const Node &y)
         {
             if (x.s != y.s)
             {
                 return x.s > y.s;
             }
             if (x.t != y.t)
             {
                 return x.t < y.t;
             }
             return x.id < y.id;
         });
    for (int i = 1; i <= n; ++i)
    {
        printf("%d %d %d\n", a[i].id, a[i].s, a[i].t);
    }
    return 0;
}

例如，输入为：

4
90 20
100 30
90 10
90 10

输出为：

2 100 30
3 90 10
4 90 10
1 90 20

编号 $2$ 的成绩最高，先输出。其余三条中，编号 $3, 4$ 的耗时更少；两者成绩与耗时都相同，再按编号区分。编号作为最后一个关键字，因此这道题不依赖排序算法保持相同元素的原顺序。

每次比较只检查固定数量的字段，耗时为 $O(1)$，总时间复杂度为 $O(n\log n)$。数组容量为 $N$，程序保存记录的空间为 $O(N)$。