一些语言技巧

其实有些东西个人平时根本用不到，然而不了解一下的话就看不懂大佬写的题解代码（鉴定为菜导致的 \(\texttt{qwq}\)）。

类

类（class）是结构体的拓展，不仅能够拥有成员元素，还拥有成员函数。在面向对象编程（OOP）中，对象就是类的实例，也就是变量。

C++ 中 struct 关键字定义的也是类，上文中的 结构体 的定义来自 C。因为某些历史原因，C++ 保留并拓展了 struct。

定义类

类使用关键字 class 或者 struct 定义，下文以 class 举例。

class Object{
    public:
        int weight，value;
}e[MAXN];
const Object a;
Object b, B[MAXN];
Object *c;

与使用 struct 大同小异。该例定义了一个名为 Object 的类。该类拥有两个成员元素，分别为 weight,value；并在 } 后使用该类型定义了一个数组 e。

定义类的指针形同结构体。显然，以下两种定义的方式是等价的。

struct edge{int to, nxt;}e[MAXM << 1];
// ----------我是分割线----------
class graph{
    public:
    	int to, nxt;
}e[MAXM << 1];

访问说明符

本例中出现了 public，这属于访问说明符。

• public：该访问说明符之后的各个成员都可以被公开访问，简单来说就是无论 类内 还是 类外 都可以访问。
• protected：该访问说明符之后的各个成员可以被 类内、派生类或者友元的成员访问，但类外 不能访问。
• private：该访问说明符之后的各个成员 只能 被 类内 成员或者友元的成员访问，不能 被从类外或者派生类中访问。

对于 struct，它的所有成员都是默认 public。对于 class，它的所有成员都是默认 private。

对于算法竞赛来说，友元和派生类并不是必须要掌握的知识点。

友元（friend）：使用 friend 关键字修饰某个函数或者类。可以使得在 被修饰者 在不成为成员函数或者成员类的情况下，访问该类的私有（private）或者受保护（protected）成员。简单来说就是只要带有这个类的 friend 标记，就可以访问私有或受保护的成员元素。

派生类（derived class）：C++ 允许使用一个类作为 基类，并通过基类 派生 出 派生类。其中派生类（根据特定规则）继承基类中的成员变量和成员函数。可以提高代码的复用率。

派生类似 "is" 的关系。如 yb（派生类）"is" 狗狗（基类）。

对于上面 private 和 protected 的区别，可以看做派生类可以访问基类的 protected 的元素（public 同），但不能访问 private 元素。

访问与修改成员元素的值

方法形同结构体。

• 对于变量，使用 . 符号。
• 对于指针，使用 -> 符号。

成员函数

成员函数，顾名思义。就是类中所包含的函数。

class Object{
    public:
        int weight, value;
        void print(){
            cout << weight << endl;
            return;
        }
    void change_w(int);
};
void Object::change_w(int _weight){weight = _weight;}
Object var;

该类有一个打印 Object 成员元素的函数，以及更改成员元素 weight 的函数。

和函数类似，对于成员函数，也可以先声明，在定义，如第十四行（声明处）以及十七行后（定义处）。

如果想要调用 var 的 print 成员函数，可以使用 var.print() 进行调用。

在实例化变量时设定初始值

为完成这种操作，需要定义 默认构造函数(Default constructor)。

class Object{
    public:
        int weight, value;
    Object(){
        weight = 0;
        value = 0;
    }
};

该例定义了 Object 的默认构造函数，该函数能够在我们实例化 Object 类型变量时，将所有的成员元素初始化为 0。

若无显式的构造函数，则编译器认为该类有隐式的默认构造函数。换言之，若无定义任何构造函数，则编译器会自动生成一个默认构造函数，并会根据成员元素的类型进行初始化（与定义 内置类型 变量相同）。

在这种情况下，成员元素都是未初始化的，访问未初始化的变量的结果是未定义的（也就是说并不知道会返回和值）。

如果需要自定义初始化的值，可以再定义（或重载）构造函数。

一般来说，默认构造函数是不带参数的，这区别于构造函数。构造函数和默认构造函数的定义大同小异，只是参数数量上的不同。

构造函数可以被重载（当然首次被叫做定义）。需要注意的是，如果已经定义了构造函数，那么编译器便不会再生成无参数的默认构造函数。这会可能会使试图以默认方法构造变量的行为编译失败（指不填入初始化参数）。

销毁

这是不可避免的问题。每一个变量都将在作用范围结束走向销毁。

但对于已经指向了动态申请的内存的指针来说，该指针在销毁时不会自动释放所指向的内存，需要手动释放动态内存。

如果结构体的成员元素包含指针，同样会遇到这种问题。需要用到析构函数来手动释放动态内存。

析构 函数（Destructor）将会在该变量被销毁时被调用。重载的方法形同构造函数，但需要在前加 ~

默认定义的析构函数通常对于算法竞赛已经足够使用，通常我们只有在成员元素包含指针时才会重载析构函数。

class Object{
 	public:
  		int weight;
  		int value;
  		int* tmp;
  	Object(){
    	weight = 0;
    	value = 0;
  	}
    ~Object(){delete tmp;}
};

为类变量赋值

默认情况下，赋值时会按照对应成员元素赋值的规则进行。也可以使用 类名称() 或 类名称{} 作为临时变量来进行赋值。

前者只是调用了复制构造函数（copy constructor），而后者在调用复制构造函数前会调用默认构造函数。

另外默认情况下，进行的赋值都是对应元素间进行 浅拷贝，如果成员元素中有指针，则在赋值完成后，两个变量的成员指针具有相同的地址。

// A,tmp1,tmp2,tmp3 类型为 Object
tmp1 = A;
tmp2 = Object(...);
tmp3 = {...};

如需解决指针问题或更多操作，需要重载相应的构造函数。

命名空间

C++ 的 命名空间 机制可以用来解决复杂项目中名字冲突的问题。

举个例子：C++ 标准库的所有内容均定义在 std 命名空间中，如果定义了一个叫 cin 的变量，则可以通过 cin 来访问定义的 cin 变量，通过 std::cin 访问标准库的 cin 对象，而不用担心产生冲突。

其实在算法竞赛中更加实用的一种用法是对于每一个子任务都编写一套代码：

namespace IO{
	int read(){
        int t = 1, x = 0;char ch = getchar();
        while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
        while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
        return x * t;
    }
    void write(int x){
        if(x < 0){putchar('-');x = -x;}
        if(x >= 10)write(x / 10);
        putchar(x % 10 ^ 48);
    }
}
namespace solve1{ // 选择排序
    n = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();
    for(int i = 1 ; i < n ; i ++){  
        int tmp = i;  
        for(int j = i + 1 ; j <= n ; j ++)  
            if(a[j] < a[tmp])tmp = j;  
        swap(a[i], a[tmp]);  
    }
    for(int i = 1 ; i <= n ; i ++){
        if(i != 1)putchar('\n');
        write(a[i]);
    }
    putchar('\n');
}
namespace solve2{ // 冒泡排序
    n = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();    
    bool flag;  
    for(int i = 1 ; i < n ; i ++){
        flag = false;
        for(int j = 1 ; j < n ; j ++)
            if(arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]),flag = true;
        if(flag == false)break;
    }
    for(int i = 1 ; i <= n ; i ++){
        if(i != 1)putchar('\n');
        write(a[i]);
    }
    putchar('\n');    
}
namespace solve3{ // 插入排序
    n = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();
    for(int i = 2 ; i <= n ; i ++){  
        int tmp = a[i], j = i - 1;  
        while(j > 0 && a[j] > tmp)  
            a[j + 1] = a[j],j--;  
        a[j + 1] = tmp;  
    }
    for(int i = 1 ; i <= n ; i ++){
        if(i != 1)putchar('\n');
        write(a[i]);
    }
    putchar('\n');
}
namespace solve4{ // 快速排序
    void sort(int l, int r){
        int i = l, j = r;
        int base = a[l + r >> 1];
        do{
            while(a[i] < base)i++;
            While(a[j] > base)j--;
            if(i <= j)
                swap(a[i], a[j]),i++,j--;
        }while(i <= j)
        if(l < j)sort(1, j);
        if(i < r)sort(i, r);
    }
    n = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();
    sort(1, n);
    for(int i = 1 ; i <= n ; i ++){
        if(i != 1)putchar('\n');
        write(a[i]);
    }
    putchar('\n');
}

声明

下面的代码声明了一个名字叫 IO 的命名空间：

namespace IO{
	int read(){
        int t = 1, x = 0;char ch = getchar();
        while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
        while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
        return x * t;
    }
    void write(int x){
        if(x < 0){putchar('-');x = -x;}
        if(x >= 10)write(x / 10);
        putchar(x % 10 ^ 48);
    }
}

声明之后，在这个命名空间外部，你可以通过 IO::read() 来访问命名空间 IO 内部的 read 函数。

命名空间的声明是可以嵌套的，因此下面这段代码也是允许的：

namespace A{
    namespace B{
    void f(){ ... }
    }  // namespace B
    void f(){
      B::f();  // 实际访问的是 A::B::f()，由于当前位于命名空间 A 内，所以可以省略前面的 A::
    }
}  // namespace A
void f(){ // 这里定义的是全局命名空间的 f 函数，与 A::f 和 A::B::f 都不会产生冲突
  A::f();A::B::f();
}

using 指令

声明了命名空间之后，如果在命名空间外部访问命名空间内部的成员，需要在成员名前面加上 命名空间::。

有没有什么比较方便的方法能让我们直接通过成员名访问命名空间内的成员呢？答案是肯定的。我们可以使用 using 指令。

using 指令有如下两种形式：

1. using 命名空间::成员名;：这条指令可以让我们省略某个成员名前的命名空间，直接通过成员名访问成员，相当于将这个成员导入了当前的作用域。
2. using namespace 命名空间;：这条指令可以直接通过成员名访问命名空间中的 任何 成员，相当于将这个命名空间的所有成员导入了当前的作用域。

因此，如果执行了 using namespace std;，就会将 std 中的所有名字引入到全局命名空间当中。这样，我们就可以以 cin 代 std::cin，以 cout 代 std::cout。

由于 using namespace std; 会将 std 中的 所有名字 引入，因此如果声明了与 std 重名的变量或函数，就可能会因为命名冲突而导致编译错误。

有了 using 指令，代码可以有这两种等价写法：

#include <iostream>
using std::cin;
using std::cout;
using std::endl;
int main(){
    int x, y;
    cin >> x >> y;
    cout << x + y << endl;
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    int x, y;
    cin >> x >> y;
    cout << x + y << endl;
    return 0;
}

应用

在一些具有多个子任务的问题中，我们可以对每个子任务各开一个命名空间，在其中定义我们解决该子任务所需要的变量与函数，这样各个子任务间互不干扰，会在一定程度上方便调试，也会改善程序的可读性。

重载运算符

重载运算符是通过对运算符的重新定义，使得其支持特定数据类型的运算操作。重载运算符是重载函数的特殊情况。

C++ 自带的运算符，最初只定义了一些基本类型的运算规则。当我们要在用户自定义的数据类型上使用这些运算符时，就需要定义运算符在这些特定类型上的运算方式。

C++ 允许编写者为名称相同的函数或者运算符指定不同的定义。这称为 重载（overload）。

如果同名函数的参数种类、数量中的一者或多者两两不相同，则这些同名函数被看做是不同的。

需要注意的是：如果两个同名函数的区别仅仅是返回值的类型不同则无法进行重载，此时编译器会拒绝编译！

如果在调用时不会出现混淆（指调用某些同名函数时，无法根据所填参数种类和数量唯一地判断出被调用函数。常发生在具有默认参数的函数中），则编译器会根据调用时所填参数判断应调用函数。

而上述过程被称作重载解析。

重载运算符，可以部分程度上代替函数，简化代码。

下面给出重载运算符的例子。

class Vector{
    public:
        int x, y;
        Vector() : x(0), y(0){}
        Vector(int _x, int _y) : x(_x), y(_y){}
        int operator*(const Vector& other){return x * other.x + y * other.y;}
        Vector operator+(const Vector&);
        Vector operator-(const Vector&);
};
Vector Vector::operator+(const Vector& other){
    return Vector(x + other.x, y + other.y);
}
Vector Vector::operator-(const Vector& other){
    return Vector(x - other.x, y - other.y);
}

该例定义了一个向量类，并重载了 * + - 运算符，并分别代表向量内积，向量加，向量减。

对于自定义的类，如果重载了某些运算符（一般来说只需要重载 < 这个比较运算符），便可以使用相应的 STL 容器或算法，如 sort()。

可以被重载的运算符有这些：

= +-* / = % += -= *= /= %= <> == != <= >= & | !^~ &= |= ^=
    //----------
    << <<= >> >>= ++--&& || [](),
    ->*->new delete new[] delete[]

限制

重载运算符存在如下限制：

• 只能对现有的运算符进行重载，不能自行定义新的运算符。
• 以下运算符不能被重载：::（作用域解析），.（成员访问），.*（通过成员指针的成员访问），?:（三目运算符）。
• 重载后的运算符，其运算优先级，运算操作数，结合方向不得改变。
• 对 &&（逻辑与）和 ||（逻辑或）的重载失去短路求值。

实现

重载运算符分为两种情况，重载为成员函数或非成员函数。

当重载为成员函数时，因为隐含一个指向当前成员的 this 指针作为参数，此时函数的参数个数与运算操作数相比少一个。

而当重载为非成员函数时，函数的参数个数与运算操作数相同。

下面将给出几个重载运算符的示例。

函数调用运算符

函数调用运算符 () 只能重载为成员函数。通过对一个类重载 () 运算符，可以使该类的对象能像函数一样调用。

重载 () 运算符的一个常见应用是，将重载了 () 运算符的结构体作为自定义比较函数传入优先队列等 STL 容器中。

一个很经典的例子就是莫队算法中的奇偶化排序：

struct query{
    int left, right, id;
    bool operator<(const query &x)const{
        if(left / len != x.left / len)return left < x.left;
        if(left / len & 1)return right < x.right;
        return right > x.right;
    }
}q[MAXQ];

自增自减运算符

自增自减运算符分为两类，前置和后置。为了能将两类运算符区别开来，对于后置自增自减运算符，重载的时候需要添加一个类型为 int 的空置形参。

另外一点是，内置的自增自减运算符中，前置的运算符返回的是引用，而后置的运算符返回的是值。虽然重载后的运算符不必遵循这一限制，不过在语义上，仍然期望重载的运算符与内置的运算符在返回值的类型上保持一致。

因此，对于类型 T，典型的重载自增运算符的定义如下：

比较运算符

在 std::sort 和一些 STL 容器中，需要用到 < 运算符。在使用自定义类型时，我们需要手动重载。

还是以讲函数调用运算符时举的例子说起，如果我们重载比较运算符，实现代码是这样的：

struct node{
    int a, b;
    bool friend operator<(node &a, node &b){
       	if(a.a == b.a)return a.b > b.b;
        else return a.a > b.a;
    }
}

事实上，只要有了 < 运算符，则其他五个比较运算符的重载也可以很容易实现。

bool operator<(const T& lhs, const T& rhs){return rhs > lhs;}
bool operator>(const T& lhs, const T& rhs){return rhs < lhs;}
bool operator<=(const T& lhs, const T& rhs){return !(lhs > rhs);}
bool operator>=(const T& lhs, const T& rhs){return !(lhs < rhs);}
bool operator==(const T& lhs, const T& rhs){return !(lhs < rhs)&& !(lhs > rhs);}
bool operator!=(const T& lhs, const T& rhs){return !(lhs == rhs);}