回顾 C++ 编程基础

这篇笔记适合系统性学习过 C++，希望增加编程熟练度（指减少对 Copilot、搜索引擎、文档的依赖）、复习基础概念的读者阅读。不过，本文也会循序渐进地讲解编程中的难点。

可以选取收录但没有收录的话题有很多，比如继承、多态、运算符重载等等，但笔者目前用到它们的机会比较少，可以等到用到时再回顾。本文优先回顾一些更加基础的知识（如引用）和更加常用的工具（如标准模板库 STL）。

C 语言编程基础

C++ 作为 C 语言的扩展，继承了其大部分的语法。C++ 编程过程中出现的疑问，可能是 C 编程中的遗留问题。我们讨论几个容易造成困难的概念，包括常量（const）、静态（static）和指针。

在讨论之前，请确保你首先熟悉如何通过 spiral rule 推导类型的含义。

常指针和指向常量的指针

const T * p; // 指向常量的指针，不能通过它修改被指向的东西
T const * p; // 指向常量的指针
T* const p; // 常指针，不能改变指向
T const * const p; // 指向常量的常指针
const T* const p; // 指向常量的常指针

一般的指针可以被转换为常量指针，反之不行

void writeit(int * x);
void readit(const int * x);
int x = 3;
int * p = &x;
const int * cp = p;
writeit(cp); // Error
readit(cp);

数组与指针

数组和指针都是指向存储空间的方法。“二维”的指针结构有如下的种类，可以按照 spiral rule 判定其类型：

int a[5][5]; // 2d array of ints 二维数组
int *b[5]; // array of (pointer to int) 指针数组
int ** c; // pointer to (pointer to int) 二重指针

它们的语义不相同：a 可以转换为一个指向 int 的指针 int *p = a；b 和 c 都是指向指针的指针。对于 a,b,c，编译器产生的内存布局也不同：

a: int[ a[0][1], ..., a[0][4], a[1][0], ... ,a[1][4], ..., a[4][4] ]
b: ptr[ b[0], ..., b[4] ]
         \-> int      \-> int
c: ptr 
     \-> ptr
           \-> int

归根结底，高维数组是 C 语言中让编译器和程序员更方便的记法，一个 int 高维数组就是一个指向 int 的常指针。你可以把高维数组转换为指向 T 的指针来用，但你不能把指针变成任何高维数组。注意下面的例子中声明数组参数的方式。

void use_array(int a[]){...}
void use_ptr(int *a){...}

int a[5];
int *b = a; // arr to ptr OK
int *c = new int[5];
use_array(c); // ptr to arr OK

void use_array_2d(int a[5][5]){...} // a[][5] also works (1)
void use_ptr_ptr(int **a){...}

int d[5][5];
use_array_2d(d);
use_ptr_ptr(d); // ERROR (different memory layout)
use_ptr((int*) d); // OK, same memory layout

int *e = new int[25];
use_array_2d( (int[5][5]) e ); // ERROR (compiler forbids)

C 中的高维数组完全可以被一维数组和手动计算下标来替代:

We can use arr+((i*j_dim)+j)*k_dim+k for &arr[i][j][k]
That's why we do not need to specify first dimension in (1)

静态

“静态” 关乎生命周期和作用域：

静态变量的生命周期是整个程序的开始到结束。若未初始化存储在 .bss 段，若已初始化存储在 .data 段。例如：

void f(){
  static int cnt = 5;
  cout << cnt++ << endl;
}
int main(){
  f(); f(); // prints 5, 6
}

静态全局变量和静态函数的作用域仅限于定义它的文件。

C++ 中的引用

到了 C++，编程难点增加了一个，即引用机制。

左值与右值

左值：有地址的变量
右值：没有地址的变量，如字面值、中间结果

引用

引用，默认是左值引用，是一种别名机制。它比起指针，区别或者说优势在于：

必须被初始化，不会为空，因此更加安全
不可更改：一旦和一个变量绑定后，不能更改指向的对象。

int a = 5;
int &ref_a = a;
int const &ref_a = a; // 常量引用
int &const ref_a = a; // Error: 没有"常引用"，因为引用不能更改对象
int &ref_5 = 5; // Error 左值引用不能指向右值
int const &ref_5 = 5; // 不变左值的引用可以指向右值，因为不变左值只有一种可能的取值

一般的引用可以转换为常量引用，反之不行。

右值引用

右值引用是 C++11 的新特性，它是临时对象的别名。用 && 符号引用右值。右值引用允许对临时对象进行修改，主要用于实现移动语义和避免不必要的拷贝。例如：

int &&ref_5r = 5; // ref_5r 是右值引用，绑定到字面量 5
ref_5r = 6; // 合法，右值引用可以修改所绑定的对象

右值引用不能直接绑定左值，但可以使用 std::move 将左值转换为右值。例如：

#include <utility>
int a = 5;
int &&ref_r = std::move(a); // 使用 std::move 将左值 a 转换为右值表达式，从而允许 ref_r 绑定它

左值引用绑定右值的情况前面已经见到了：int const &ref_5 = 5;

std::move 后的变量是未定义的，它的“值”被 move 的目标夺走了，可以参考下面的内容（来自这里）。

int main() {
    string strA = "Hello";
    cout << strA << endl;
    string strB = move(strA);
    cout << strA << endl; // undefined, might print blank
    cout << strB << endl;
}

C++ 11 vector 的 pushback 新函数签为 void push_back (value_type&& val);，就是利用右值引用减小拷贝的开销。

C++面向对象编程提要

面向对象编程中，如何进行初始化和清除由类设计者决定；何时进行初始化和清除由编译器决定。我们通过设计构造函数和析构函数来控制前者。我们先讨论这两者，然后讨论之前 const 和 static 修饰符在类中的新规则。

一些常见的 typo：

用默认构造函数创建对象用 A a 而非 A a()，后者是函数声明
初始化列表前应有 “:”
类的定义后应有 “;”

构造函数

在执行构造函数的函数体之前，类的成员变量要先初始化。如果成员变量在初始化列表中，则依此初始化，否则调用其默认构造函数。

默认构造函数

默认构造函数是不带任何参数、或每个形参提供默认实参的构造函数。当用户没有定义任何一个构造函数时，会被隐式定义，否则可以通过 A() = default 这种方式手动要求生成默认构造函数。

拷贝构造函数

拷贝构造函数，A(const A& src)，在下面的示例时机中调用：

A a; A b(a);
A c = a;
void f(A a) // 作为形参
A f() // 作为返回值

const A& src 可以绑定左值和右值，不过会造成拷贝的开销。

移动构造函数

移动构造函数，A(A&& src)，可以对于即将析构的临时对象，直接利用其堆内存。可以通过下面的例子测试移动构造函数：

class T{
    public:
    int *buf;
    T(): buf(new int(0)) {}
    T(T&& t): buf(t.buf) {
      cout << "Test(Test&& t) called, buf=" << hex << buf << endl;
      t.buf=nullptr;
    }
};
T getT(){
    T t;
    return t; //calls T(T&& t)
}
int main(){
    T x = getT(); //calls T(T&& t)
}

默认的编译器返回值优化会让程序不调用移动构造函数从而没有输出。可以禁用它，如用 g++ 编译的话：g++ move-sem.cpp -std=c++11 -fno-elide-constructors -o move-sem

再举一个移动来减少拷贝开销的例子：

template <class T>
swap (T& a, T& b){
  T tmp(std::move(a));
  a = std::move(b);
  b = std::move(tmp);
}

析构函数

析构函数唯一、没有返回值、没有参数。在执行析构函数的函数体之后，会自动调用成员变量的析构函数。

常量成员

常量数据成员仅允许就地初始化和初始化列表初始化，不能在构造函数函数体中赋值。

常量成员函数不能修改类的状态，它们形如 type func(...) const {...}。如果对象自己为常量变量 const A a;，则它只能调用常量成员函数，很合理吧。

静态成员

除了生命周期是程序运行开始到结束之外，静态成员变量 static int x; 和静态成员函数 static int func() 的核心特性是它们由该类的所有对象共享。静态函数成员不能访问非静态成员，因为非静态成员是取决于具体对象的。

静态变量在类定义中完成声明，但必须在类外定义及初始化，例如：

class T{
  public:
    static int count; // Declaration
    T(){count++;}
};
int T::count = 0; // Definition and Initialization

实用工具：C++ 标准库

C++ STL （Standard Template Library）在实际的编程中应用很频繁，因此创建此节作为备忘录，记录其特征和使用方法。STL 由诸多部分组成，包括容器、算法和迭代器、输入输出等。

容器

Pair 和 Tuple

template<class T1, class T2> struct pair{
  T1 first;
  T2 second;
};
auto p = std::make_pair("Foo", 1.0);
p.first; p.second;

std::tuple<int, char, std::string> get_tuple(){
   return {0, 'a', "Alpha"};
}
auto t = get_tuple();
std::get<0>(t); // same for 1,2
int e0; char e1; std::string e2;
std::tie(e0, e1, e2) = get_tuple();

序列容器

序列容器 (Sequence Container) 中的元素有顺序。vector, list 等容器属于序列容器。

关联容器

关联容器 (Associative Container) 中的元素需要按照数值大小访问。不过，以 set（无序集合）和 map（关联数组）为例，也可以迭代从而顺序访问：它们的内部，元素是按照 key 排序的，它返回的迭代器迭代的顺序是有序的。二者实现用到的数据结构都是二叉搜索树（具体而言，红黑树）。

如果在外部不需要通过迭代顺序访问元素，那么可以用 unordered_set 和 unordered_map，它们内部是用哈希表实现的。因此，它们（而非 set 和 map）与 Python 中的 Set 和 Dict 对应。尽管如此，我们仍然可以用迭代器访问它们（内部实现可能就是遍历所有桶）。

set<int> members;
members.insert(x);
auto it = members.find(p);
if(it!=members.end()) members.erase(it);
members.count(5); // 0 or 1

map<string, int> s;
s["foo"] = 1;
cout << s["bar"] << endl; // outputs 0. When key not already exists, it gets inserted, and mapped to a default value of the mapped type.
// find, count, erase is the same as set

迭代器及其算法

迭代器是检查容器内元素并遍历元素的数据类型。迭代器是容器类型的一个嵌套类（nested class）（注意与派生类 derived class / subclass 相区分）

class vector {
  class iterator {
    ... // 迭代器是嵌套类型
  }
};

int solve(vector<int>& nums){
  sort(nums.begin(), nums.end()); // 左闭右开
  vector<int>::iterator bd = upper_bound(nums.begin(), nums.end(), val);
  int r = bd - nums.begin() - 1; // 迭代器相减
  // 上面等同于 distance(nums.begin(), bd) - 1
}

注意，迭代器在容器移动或变化时会失效，如对 vector 的 insert, erase, push_back。容器方法文档中的 iterator validity 会说明方法是否会使迭代器失效。

algorithm

algorithm 标准库中包含了操纵容器的算法，非常常用的有：

std::sort，按照从小到大的顺序排序区间中的元素，默认的 comp 是 std::less，即不存在右面 less than 左边的情况。如果需要从小到大排序？
- std::sort(s.begin(), s.end(), std::greater<int>());
- std::sort(s.begin(), s.end(), [] (int a, int b){return a>b;} );
std::lower_bound，按照不小于 value 的最左边的元素。

利用 algorithm 做二分查找：

假设数组从小到大排序：

const std::vector<int> v{1, 2, 4, 5, 5, 6};
int y = 5
auto i1 = std::lower_bound(v.begin(), v.end(), y); // 找到不小于 y 的最左侧元素, i1=3。同时，i1-1 必然是小于 value 的最右侧元素。
auto i2 = std::upper_bound(v.begin(), v.end(), y); // 找到大于 y 的最左侧元素，i2=5。同时，i2-1 必然是不大于 value 的最右侧元素。

图示：

 value
  /|\
   |                   eee
 y |     eeeeeeeeeeeeee|
   | eeee|             |
   |     |             |
   +-----+-------------+---->idx
    (lower_bd)    (upper_bd)

假设数组从大到小排序：

const std::vector<int> v{6, 5, 5, 4, 2, 1};
int y = 5
auto i1 = std::lower_bound(v.begin(), v.end(), y, std::greater<int>()); // 找到不大于 y 的最左侧元素, i1=1。同时，i1-1 必然是大于 value 的最右侧元素。
auto i2 = std::upper_bound(v.begin(), v.end(), y, std::greater<int>()); // 找到小于 y 的最左侧元素，i2=3。同时，i2-1 必然是不大于 value 的最右侧元素。

图示：

 value
  /|\
   | eeee
 y |     eeeeeeeeeeeeee
   |     |             eee
   |     |             |
   +-----+-------------+---->idx
    (lower_bd)    (upper_bd)

关于文档中 ordered before 和 ordered after 的含义：
如果 comp 是 std::less，那么 ordered before 就是小于，ordered after 就是大于
如果 comp 是 std::greater，那么 ordered before 就是大于， ordered after 就是小于。