c++ programming notes

1. 调试技巧与基本知识：

   • GCC 基本知识
     gcc 与 g++ 分别是 GNU 的 c & c++ 编译器 gcc/g++
     在执行编译工作的时候，总共需要4步：

     • preprocessing（编译预处理）

     • compilation（编译）

     #compiles and assembles files but doesn’t link them.
     $ g++ -c
     #This is useful when building large projects to separate file compilation and minimize what is re-compiled.
     

     • assembly（组装）

     • linking（链接）

     • a quick start

     #Say you have a file helloworld.C as follows :
     # #include 
     #     int main ()
     #     {
     #         printf("Hello World\n");
     #     }
     #You can compile and run it from the unix prompt as follows :
     $ g++ helloworld.c
     #This creates an executable called "a.out". You can run it by typing
     $ ./a.out
     #Since no executable name was specified to g++, a.out is chosen by default. Use the "-o" option to change the name :
     $ g++ -o helloworld helloworld.c
     #creates an executable called "helloworld". 
     #using && to execute two commands one by one
     $ g++ debug.cpp -o debug && ./debug
     #notice that you can't type "debug" cause it's not a command you must type "./debug" without g++ before it
     #creates an executable called "debug" and then run it
     

     一些必备指令：
     $ g++ debug.cpp -Wall -Wextra && ./debug | head -100

   • shell基本知识

     • 复制粘贴：如果你按下鼠标左键，沿着文本拖动鼠标（或者双击一个单词）高亮了一些文本，那么这些高亮的文本就被拷贝到了一个由 X 窗口系统（使 GUI工作的底层引擎）管理的缓冲区里面。然后按下鼠标右键，这些文本就被粘贴到光标所在的位置。

     • 文件名和命令名是大小写敏感的。

     • Linux 没有“文件扩展名”的概念，不像其它一些系统，可以用你喜欢的任何名字来给文件起名。

     • 大多数命令使用的选项，是由一个中划线加上一个字符组成，例如，“-l”，但是许多命令，包括来自于 GNU 项目的命令，也支持长选项，长选项由两个中划线加上一个字组成。

     • 注意表示法：在描述一个命令时，当有三个圆点跟在一个命令的参数后面，这意味着那个参数可以重复

     • ls (list content)

     • pwd (path work directory)

     • cd (change directory) 符号 “.” 指的是工作目录， ”..” 指的是工作目录的父目录。

       • cd .. (返回父目录)
       • cd ./ (= cd)
       • cd 更改工作目录到你的home dictionary（家目录）
       • / 根目录
         • /bin 包含系统启动和运行所必须的二进制程序
       • ~ 家目录
       • /tab/ (auto fill up filename)

     • sudo (Super User Do)

     • file filename 查看文件类型

     • less filename 查看文件

     • An AND list has the form

       #command2 is executed iff command1 returns an exit status of zero (success).
       $  && 
       

   • VS Code 基本知识
     VS Code 组织结构：全局——工作区（workspace）——文件夹（即项目）

   • wget

   • prinf()的使用

2. 数组传递：由于形式参数和实际参数是同一数组（数组名代表了数组在内存中的起始地址（是一个指针），将数组作为函数参数时，相当于把实参的数组的起始地址赋给了形参的数组的起始地址，因此这两个数组实际上就是同一个数组，详见P 120）定义的时候要加中括号，但是形式参数和实际参数都是数组名，所以调用这个语句时不用加中括号！！！
   注意二维数组传递的时候需要指定第二维的个数（原因是为了告诉函数每个指针间相差几个存储空间）

   void swap(char str[], int k, int i)
   //使用方法：swap(string, 3， 1)
   

3. 帧：系统为函数分配的一块内存空间，用于存放形式参数和函数体内定义的变量，函数运行结束时，系统收回分配给该函数的帧，因此存放在这块帧中的变量都消失了。

4. 栈(Stack)：函数定义的变量（包括形式参数）都创建在一个称为栈的独立内存区域，调用一个函数相当于从栈中分配一个新的帧，并且放在其他活动函数的帧上面，return之后，函数对应的帧被收回，帧中的变量就完全消失了，其他函数无法再引用，因此称为局部变量。

5. 变量的作用域：main函数中定义的变量也是局部的；一个程序块中定义的变量在本程序块中有效；局部程序块是指一对大括号{}之间的一段C语言程序，如果局部变量与局部程序块以外的变量重名，则前者优先于后者，回到程序块以外时，程序重新进入最初定义的变量的作用范围；变量定义出现在所有函数定义之外，称为全局变量，保存在一个独立内存区域中，永远都不会被包含局部变量的帧覆盖，在局部变量与全局变量同名时，可以使用作用域运算符::加在变量名前，用于指代全局变量；

6. 变量的存储类别：变量的存储位置

   存储类别 数据类型 变量名表
   //自动变量自动存于stack中，空间也自动被回收
   //c++ 11后不用写auto，只要写 int a, b;
   auto int a, b;
   //自动类型推断，au_a为int类型
   int a = 10;
   auto au_a = a;
   //静态变量，限定变量只能在某个区域使用，放在全局变量区
   //1.静态全局变量（通常是为了防止其他文件引用修改该变量值造成混乱）
   static int x; //全局变量x为当前源文件私有的，其他源文件中不可引用它
   //2.静态局部变量（下次函数调用可以使用上次函数调用时的值）
   //注1:未初始化的static variable都自动初始化为0，且初值是编译时赋的，运行时不会初始化
   //注2:函数调用结束后静态局部变量仍然存在，但其它函数无法引用
   //注3:静态局部变量在程序结束时消亡，先消亡静态局部变量再消亡全局变量
   static int c = 3;//函数在第二次调用及以后时该语句被忽略，继续使用上次函数调用时c的空间
   c = c + 1;
   //寄存器变量（仅限局部自动变量可放入CPU的寄存器中，加快读取速度）
   //仅代表程序员的意向，若无合适寄存器则设为自动变量
   //现在的编译器自动优化
   register int x;
   //外部变量的申明（不是定义不会分配空间，如同函数原型申明）
   /*在全局变量定义之前的语句或函数或者另一个源文件中的函数也要使用该全局变量，则在引用之前应该用extern进行外部变量申明，在一个源文件中引用的别的源文件的全局变量就叫外部变量*/
   /*使用外部变量要谨慎，因为修改该变量的值可能会影响另一个源文件中函数执行的结果！！通常用static把某全局变量申明为本文件私有的来防止被其他源文件修改*/
   extern 类型名 函数名
   

7. 驼峰命名法

8. 条件断点；函数断点

9. 宏调试:

   #define DEBUG
   #ifdef DEBUG
   #endif DEBUG
   

10. 算法复杂性：
    输入大小
    代码质量
    硬件
    算法复杂性

11. 时间复杂性：
    基本操作
    最坏和平均情况O
    最好情况\(\Omega\)
    最好情况与最坏情况相同\(\Theta\)

12. 空间复杂性：
    S(n)

13. 排序：
    冒泡排序O(n²)
    插入排序O(n²)
    希尔排序(插入的优化)
    计数排序

14. 引用传递的swap

    template 
    void swap(T &a, T &b)
    {
        T c = a;
        a = b;
        b = c;
    }
    

15. 最优化问题：
    穷举法
    贪心法：最速下降法（局部最优）；硬币找零

16. 空语句

17. 数组：
    同类，有序，元素个数必须是常量
    定义常量
    数组名存放了数组的起始地址，除字符串以外只能一个一个输入输出
    数组定义在一块连续的空间上

    a[i]
    a + i //这个指针相当于a之后a的类型所定义的第i个内存区域
    

    C/C++不检查数组越界！！

18. 随机数

    strand(time(NULL))
    

19. 数据的内部视图和外部视图

20. 指针的概念
    指针的类型决定了编译器解释地址中内容的方式
    *在语法上属于变量名，不属于类型名
    直接访问间接访问
    地址运算符 &x 返回的是变量 x 的地址，不能跟常量或表达式
    *intp 返回 intp 指向的这个变量的内容
    在对 intp 使用引用运算之前，必须先对 intp 赋值
    指针+1表示数组中指针指向元素的下一元素地址
    可用*(intarray + k)引用intarray[k]
    同类的指针变量之间可相互赋值，表示两个指针指向同一内存空间

    //NULL是一个特殊指针值，称为空指针。它的值为0。它可被用来初始化一个指针，表示不指向任何地址。
    //c++11引入了nullptr充当单独的空指针常量，与任何指针类型可以发生隐式类型转换，也可以隐式转换为bool型（值为false）但是不存在到整型的隐式类型转换
    void f(int *);
    void f(int);
    //调用f(nullptr)将会调用函数f(int *)而不会像f(NULL)一样调用f(int)
    

    数组名是一个指针常量
    void *指针变量名;为统配指针类型，可以与任何类型指针相互赋值

21. **指针与 const **：

    //指向常量的指针（为防止指向的变量被修改而设计）
    const int *p = &x;
    //注意&后面只能跟变量，而且*p不能修改，但是p可以修改如p = &y;
    //指针常量（指向的地址固定但指向的变量的值可以变）定义时必须赋初值
    int *const p = &x;
    //*p可以修改如*P = 20;，但是p不能修改
    //指向常量的指针常量
    const int *const p = &x;
    //不能修改其指向的地址，也不能通过它修改变量的值
    

22. 动态内存分配：
    对于一个指针变量p
    申请动态变量：p = new int;
    申请动态数组：p = new int[x];
    注意此处的 x 可以是变量
    申请动态变量并初始化：int *p = new int(10)
    释放动态变量：delete p;
    释放动态数组：delete [] p; （字符数组可以不加方括号）
    动态分配：在程序执行过程中需要新的存储空间时，可用动态分配的方法向系统申请新的空间，当不再使用时用显式的方法还给系统。这部分空间是从被称为堆(Heap)的内存区域分配。
    注意c++程序运行期间，动态变量不会消亡，必须用delete删除

23. 异常：
    除0；空间不够；有些异常可以捕获做处理让程序运行下去

24. 内存泄漏：
    动态变量是通过指针间接访问的。如果该指针被修改，这个区域就被丢失了。堆管理器认为你在继续使用它们，但你不知道它们在哪里，这称为内存泄露。
    当释放了内存区域，堆管理器重新收回这些区域，而指针仍然指向堆区域，但不能再使用指针指向的这些区域。
    释放内存对一些程序不重要，但对有些程序很重要。如果你的程序要运行很长时间，而且存在内存泄漏，这样程序会耗尽所有内存，直至崩溃。

25. assert宏：

    //检查new操作返回值来检验动态空间是否申请成功
    int *p;
    p = new int;
    if (!p) {
    	cout << "allocation failure\n";
    	return 1;
    }
    //用assert宏直接退出程序 #include 
    int *p;
    p = new int;
    assert(p != 0);//不加这一条后面一句语句就可能报错，如果堆空间不够了
    *p = 20;
    

26. 初始化：

    //auto与动态内存分配
    auto p1 = new auto(10); //注意这里p1前不用加*号
    //c++11 动态数组初始化
    int *p = new int[5]{1, 2, 3, 4, 5}; //若给出初值个数少于数组元素个数剩余赋值为0
    

27. 指针传递输出参数：

    void SolveQuadratic(double a, double b, double c, double *px1, double *px2);
    //传入的只有x1与x2的地址，于是x1与x2可以成为函数的输出，称为输出参数，设计函数原型时一般将输入参数放在前面，把输出参数放在后面
    SolveQuadratic(a, b, c, &x1, &x2);
    cout << x1 << x2;
    

28. 字符串作为函数的参数：
    如果只读取字符串的话应该使用指向常量的字符指针int word_cnt(const char *s)
    在函数体中可以通过++s的方法遍历字符串

29. 返回指针的函数：只需在函数名前加一个*号
    注意返回地址对应的变量不能是被调函数的局部变量，否则会消亡
    如果返回的指针是在函数体内new出来的，不要忘记在main函数中使用完后再delete掉
    char *subString(char *s, int start, int end);

30. 引用类型：（实际上是一种隐式指针，但每次不用写*号，简便了程序书写）

    coint i;
    int &j = i; //必须赋初值，将j与i的地址关联起来
    int &j1 = j; //valid
    //引用的绑定是永久的，不可修改
    //常量引用变量，只能引用，不能赋值
    const int &a = 1; //valid a实际上与一个值为1的临时变量绑定了
    int b;
    const int &a = b; //valid 但是不能通过a修改b的值
    //c++11拓展：范围for语句，让k以此等于数组a的每一个元素
    for (int k : a) cout << k; //valid
    for (int k : a) cin >> k; //invalid 这里是值传递
    for (int &k : a) cin >> k; //valid
    //引用传参
    void swap(int &a, int &b); //注意实参必须为左值表达式
    //引用传参的好处之一：节省空间
    int max(const int &a, const int &b); //给函数传入一个常量，防止修改
    //返回引用的函数（可将函数调用作为左值）
    int &index(int j)
    {return a[j];} //注意只能引用左值
    void main()
    {
        index(2) = 25; //相当于先执行&index(2) = a[2];，然后index(2) = 25;
        cout << index(2);
    }
    //如果不希望引用返回值通过引用被修改，可申明为const
    const int &index(int j);
    //注意不能返回该函数局部变量的引用
    

31. 指针数组：
    main函数的参数

    int main(int argc, char *argv[])
    //argc代表命令行中参数个数，每个实参都表示为一个字符串，组成一个储存一组字符串的指针数组*argv[]
    {
        return 0;
    }
    

32. 指向函数的指针： P 177

33. 函数指针作为函数参数：

    template
    void sort(T a[], int size, bool (*f) (T, T));//*f为一个比较函数的指针
    sort(a, 10, increaseInt);//函数名作为第三个参数
    sort(a, 10, increaseInt);//防止编译器无法确定第三个参数中T的类型
    //菜单选择P180
    //Lambda表达式
    

34. 多维数组
    按行存储
    调试方法：

    • 初始化列表
    • 输入输出重定向

35. 多级指针

36. 字符串
    结束标记
    空字符串""占用一个空间存储\0
    输入输出：

    • 可以直接cin以空格回车或Tab结束
      自学实验指导的实验七
      （注意缓冲区残留的回车键，可用cin.get处理）
    • cout
    • cin.get
    • 推荐：cin.getline(字符数组, 数组长度, 结束标记)注意cin.getline从键盘读取到数组长度-1，默认结束标记为回车，这样就可以自由输入空格啦！

37. cstring:
    strlen(s):返回s的长度，不含'\0'，故等于实际长度-1

38. 函数：
    函数声明：参数表中的每个参数说明可以是类型，也可以是类型后面再接一个参数名。如：

      ```c++
      int max(int, int);
      int max(int a, int b);
      ```
    

    函数执行过程：现场保护

39. 带默认值的函数：一旦某个参数指定了默认值，它后面所有参数都必须有默认值

    void f(int a, int b = 1, int c, int d = 2);
    //该申明是错误的
    

    最好在函数申明时指定默认值，因为参数默认值是给调用者使用的，而编译器是根据函数原型申明来确定函数调用是否合法的，故在定义时指定默认值没有意义，除非还充当了函数申明的作用
    不同源文件中的函数申明可以指定不同的默认值，但同一个源文件中只能指定一个默认值。

40. 内联函数：用于解决调用较小函数时进行函数调用的额外开销（如分配内存和回收内存）有点得不偿失的问题

    inline void function()
    {
        //definition
    }
    

    编译器会将内联函数的代码复制到调用处来避免函数调用，代价是会使代码变长。
    注意内联函数必须定义在被调用之前，因此必须放在头文件中（猜测因为可能会被其它函数调用，所以得先定义好编译器才知道复制的代码是是什么），否则编译器不知道应该插入什么代码。
    内联函数只是对编译器的建议，编译器可以根据实际情况决定处理方式

41. 重载函数：共用函数名
    编译器需要绑定：为重载函数中的每一个取不同的内部名字

42. 函数模板：

    template  //T为模板的形式参数，注意每个形参前都有关键字class或typename
    

    模板的实例化：函数模板实例化形成的函数叫模板函数
    如果模板的形参没有在函数的形参表中至少出现一次，需要显式指定模板实参，因为编译器不会自动推断返回值的类型

    template 
    T3 calc(T1 x, T2 y)
    {return x + y;}
    //调用过程：
    calc(5, a);
    //结果为'f'
    

43. 包装函数：给用户用的函数

44. 类型推断：

    auto ch = 'A'; //auto定义变量必须赋初值
    auto a = 5, b = 5.5, c = 'A'; //错误，因为同一个auto序列中 变量必须推导为同一类型
    int a, b;
    //不想用表达式值作为初值的类型推断：declaretype(表达式)
    decltype (a + b) c; //编译器不计算a + b的值，而是先推出a + b的类型再把其作为c的类型，c的初值随机
    

45. 类型别名：

    typedef long long ll;
    using REAL = double; //c++11
    //占用空间：sizeof运算符
    sizeof(int);
    sizeof('a' + 15);
    sizeof(x);
    

46. 常量：

    1. 整型常量：

       const long long n = 100; //n = 2LL;
       0123 //八进制，Octal，缩写OCT或O
       0x7fffffff //十六进制，Hexadecimal，简写为hex
       

    2. 实型常量：

       指数e尾数
       指数E尾数
       1e3.3 //invalid
       e3 //invalid
       e //invalid
       -18.234e-10 //valid
       //一般视为double，若要视为float: 1.23f 或 1.23F
       

    3. 字符常量：

       \n //换行：移到下一行开始，编码为10
       \r //回车：回到当前行开始，编码为13
       \t //Tab（水平制表符）：水平移到下一个Tab区，编码为9
       \0 //空字符
       \177 //ASCLL值为OCT177对应字符，即为decimal127对应字符Delete键编码
       \xhh //两位十六进制编码
       

    4. 布尔常量：true false

    5. 符号常量：
       通常全用用大写字母

       #define PI 3.14159 //c语言定义的符号常量称为宏，用编译预处理指令#define来定义
       #define RADIUS 3 + 5 //宏定义属于简单字符串替换，不加括号会出问题！！
       const double PI = 3.14159 /*只能在定义时被赋值，不能修改，右边表达式是任意的，而且初值可以不是编译时能确定的*/
       /*c++程序中某些值必须是编译时的常量，即常量表达式，如数组元素个数，为此引入constexpr来定义const expression*/
       constexpr int N = 10;
       //只有N申明为constexpr时编译器定义M时才会被通知N为常量，若N为const或者变量则会报错
       constexpr int M = N + 10; 
       /*普通函数调用出现在const expression中编译器会报错，因为编译器不会自动检查函数调用结果是否为编译时常量，为此引入constexpr函数，当constexpr函数出现在const expression中时，编译器会检查本次调用结果是否为常量，若是，通过编译，否则报错，注意只要求结果是否为常量，不在意常量如何得到，定义时关键字constexpr放在函数头最前面*/
       //valid
       constexpr int f1() {return 10;}
       constexpr int x = 1 + f1(); 
       //invalid
       int f1() {return 10;}
       constexpr int x = 1 + f1();
       //constexpr函数的返返回值可以不是常量，只要不用于const expression中就行，否则会报错
       /*constexpr函数中只能有一个执行实际操作的语句：唯一一条return语句，不允许有其他执行操作的语句，可以有类型别名，空语句等，编译时编译器会将函数调用替换成函数的返回值，因此必须在编译时进入函数而不发生函数调用，因此constexpr函数一定会被隐式指定为inline函数，编译时会将代码复制过来运行，因此也必须放到头文件里（其它函数可能会调用，因此必须预先定义）*/
       constexpr int f2(int n) {return (n % 2) ? n + 10 : 11;} //valid
       constexpr int f2(int n) {if (n % 2) return n + 10 else return 11;} //invalid
       

47. 尾置返回类型：返回值类型取决于调用时实际参数类型时，为了让编译器自动推导，而不用显示指定形参模板，c++11引入了新的函数申明语法：尾置返回类型

    template
    auto cal(Type1 alpha, Type2 beta)->decltype(alpha + beta)
    {return alpha + beta;}
    //以下invalid，因为编译器无法在编译时确定alpha + beta的类型（因为还未定义）
    template
    decltype(alpha + beta) cal(Type1 alpha, Type2 beta)
    {return alpha + beta;}
    

48. 排序进阶
    求单调函数反函数
    堆：红色第四章、第五章

49. toupper(ch)：小写转大写，大写不变
    #include

50. 目标代码：object code: In computing, object code or object module is the product of a compiler. Object files can in turn be linked to form an executable file or library file. An assembler is used to convert assembly code into machine code (object code). A linker links several object (and library) files to generate an executable. Assemblers can also assemble directly to machine code executable files without the object intermediary step.

51. priority queue

52. Encapsulation（封装）：the bundling of data with the methods that operate on that data, or the restricting of direct access to some of an object's components
    Publicly accessible methods are generally provided in the class to access or modify the state more abstractly. In practice sometimes methods (so-called "getters" and "setters") are provided to access the values indirectly, but, although not necessarily a violation of abstract encapsulation, they are often considered a sign-post of potentially poor object-oriented programming (OOP) design practice

53. Function prototype（函数原型）/ Function interface（函数接口）：a declaration of a function that specifies the function’s name and type signature（类型签名）(arity（变元个数）, data types of parameters (formal argument 形式参数), and return type), but omits the function body

54. Include directive: In C and C++, the #include preprocessor directive causes the compiler to replace that line with the entire text of the contents of the named source file (if included in quotes: "") or named header (if included in angle brackets: <>), note that a header doesn't need to be a source file
    Headers need not have names corresponding to files: in C++ standard headers are typically identified with words, like "vector", hence #include while in C standard headers have identifiers in the form of filenames with a ".h" extension, as in #include . A "source file" can be any file, with a name of any form, but is most commonly named with a ".h" extension and called a "header file" (sometimes ".hpp" or ".hh" to distinguish C++ headers), though files with .c, .cc, and .cpp extensions may also be include.
    In practice, what is usually done is that the angle-brackets form searches for source files in a standard system directory (or set of directories), and then searches for source files in local or project-specific paths (specified on the command line, in an environment variable, or in a Makefile or other build file), while the form with quotes does not search in a standard system directory, only searching in local or project-specific paths. In case there is no clash, the angle-brackets form can also be used to specify project-specific includes, but this is considered poor form. The fact that headers need not correspond to files is primarily an implementation technicality, and used to omit the .h extension in including C++ standard headers; in common use "header" means "header file".

55. size_t: size_t的取值range是目标平台下最大可能的数组尺寸，能增加代码可移植性。

56. int补码表示：按位取反加一

57. 对象：this指针

    //此处的this指针可省略（对象作为整体访问时要显式地使用this指针，即*this）
    void create(int n, int d) {this->num = n; this->den = d; this->ReductFraction();}
    

58. 构造：

    • 构造函数的名字与类相同，是类的成员函数

    • 定义对象时自动调用，不能指定返回类型

    • 构造函数可以（共用函数名），定义对象时根据初值选择相应的构造函数

    • 定义时必须给出实际参数表类名 对象名(实际参数表);
      除非有一个构造函数没有参数才可用类名 对象名();

    • 不带参数的构造函数称为默认构造函数，一个类通常只有一个默认构造函数

    • 编译器自动生成的构造函数没有参数，函数体为空，此时生成对象的所有数据成员初值为随机值

    • 写了构造函数就一定要有对应的实参，因为编译器不再生成空的构造函数了

    • 指定默认值可以解决不想写默认构造函数的麻烦

    • 初始化列表：

      DoubleArray::DoubleArray(int lh, int rh):low(lh), high(rh)
      {
      	storage = new double [high - low + 1];
      }
      

    • 初始化列表的好处：使数据成员的初始化和赋初值同步进行，提高了函数的效率， 否则系统会先执行每个数据成员对应类的默认构造函数，再执行整个类的默认构造函数

    • 必须用初始化列表的场合：

      • 数据成员是某个类的对象，不能直接用赋值语句赋初值
      • 类包含一个常量的数据成员

    • 初始化次序是按照定义时的次序来的

    • 拷贝构造函数：同类型变量初始化

      //虽然我们可以随便写，但是其本意是构造一个一模一样的对象
      Rational(const Rational &obj) //不能写成值传递，否则会自我无限调用而不终止
      {num = 2 * obj.num; den = obj.den;}
      Rational r3 = r1;
      

    • 默认拷贝构造函数的缺点：如果有指针的话会指向同一块空间

    • 调用拷贝构造函数

      //对象定义时
      DoubleArray array2(array1);
      DoubleArray array2 = array1;
      //函数调用时：值传递
      //函数返回时：返回值等于一个临时对象
      

59. 析构：
    ~DoubleArray(){if (storage) delete [] storage;}无参数无返回值

60. 生成默认构造函数：
    CreateAndDestroy() = default;

61. 阻止拷贝：
    BoubleArray(const DoubleArray &) = delete;

62. 委托构造函数

63. 初始化列表

64. 类内初始化

65. const与类

    • 常量函数成员
      const int size; //只能在构造函数的初始化列表中完成
    • 常量对象
      const Rational r1(1, 3); //只能用构造函数初始化不能使用赋值语句
    • 常量成员函数
      不改变数据成员的函数都必须声明为const，在函数头后加一个保留字const
      常量对象只能调用常量成员函数

66. 静态成员

    • 静态数据成员static double rate;
      类的静态成员函数拥有一块单独的存储区，只在类的范围内有效，可以是公有或私有
      定义在类的实现文件中
      double SavingAccount::rate = 0.05; //类的空间只有在定义时分配，必须单独在类的实现文件中定义，才能分配空间
      可以通过类名直接调用，如：类名::静态数据成员名;或和普通成员一样调用

    • 静态成员函数
      为类服务，而不是类的对象
      可以写在类定义中

      static void SetRate(double newRate);
      

      也可以写在类定义外面，不加static
      可以通过类名直接调用，如：类名::静态成员函数(实际参数表);或和普通成员函数一样调用
      没有有隐含的this指针，只能访问静态成员

    • 静态常量成员
      整个类共享的常量
      一般而言，类的数据成员不能再类定义时初始化：

      • 普通的数据成员在对象定义时由析构函数初始化
      • 静态数据成员在静态数据成员定义时初始化
      • 例外：静态常量数据成员必须在类定义时初始化

67. 友元：
    最好把友元函数的申明放在类定义最前面或最后面，并且在前面不添加任何访问控制说明

    • 友元（全局）函数
      friend void f();
      定义可以写在类定义里
    • 友元成员函数
      friend int B::func(double);
    • 友元类
      friend class B; //class B 中所有成员函数都可以直接访问该类私有成员

68. 运算符重载：不改变运算对象数，不改变优先级和结合性

    • 重载为全局函数（作为类的友元函数）

      //重载成友元函数，参数的个数，类型，返回类型与期望的完全相同
      //具有两个运算对象其返回一个新的对象的运算符建议重载为全局函数，如+, -, *, >
      //更加灵活，第一个运算对象不是this指针，可以进行自动类型转换
      friend Complex operater+(const Complex &c1, const Complex &c2)
      {return Complex(c1.real + c2.real, c1.imag + c2.imag);} //这里默认构造函数写在后面的public中
      friend Complex operater-(const Complex &c1, const Complex &c2)
      {return Complex(c1.real - c2.real, c1.imag - c2.imag);}
      

    • 函数调用运算符重载

    • 重载为成员函数

      //c++规定隐含参数this是运算符的第一个参数
      //必须设为公有成员函数，且不改变运算对象值的函数设为const的成员函数
      //=, [], (), ->必须重载成成员函数，这样编译器才能检查第一个运算对象是不是相应的类对象
      //++, --, 
      public:
      	Rational operater+(const Rational &r1) const
          {
              Rational tmp;
              tmp.num = num * r1.den + r1.num * den; //这里的num和den都是隐式添加了this->的
              tmp.den = den * r1.den;
              tmp.ReductFraction();
              return tmp;
          }
      	Rational operater*(const Rational &r1) const;
      //赋值运算符重载
      //c++中赋值运算构成一个表达式，返回值为左边对象本身，可以是左值
      //这样就可以实现用于类似 (a=b)=c 这样的再次对a=b进行写操作的表达式
      DoubleArray &DoubleArray::operater=(const DoubleArray &right)
      {
          if (this == &right) return *this; //防止自己复制自己，否则会把自己delete掉了
      	delete [] storage; //归还空间
          low = right.low;
          high = right.high;
          storage = new double[high - low + 1]; //重新申请空间
          for (int i = 0; i <= high - low; ++i) //复制数组元素
      		storage[i] = right.storage[i];
      	return *this;
      }
      //一般需要自定义复制构造函数的类也需要重载赋值运算符
      Rational r2 = r1; //拷贝构造函数
      r1 = r3; //赋值运算符重载函数
      //下标运算符的重载
      //返回对应数组元素的引用，可以是左值
      double &DoubleArray::operator[](int index)
      {
          if (index < low || index > high) {cout << "下标越界"; exit(-1);}
      	return storage[index - low];
      }
      //返回右值
      const double operator[](int i) const;
      //前缀++
      Rational &Rational::operator++(); //返回的是当前对象，不会消亡
      //后缀++
      //为与前缀区分，接受一个额外无用的int形参，使用后缀时，编译器自动用0作为这个参数的值
      Rational Rational::operator++(int); //返回的是一个新建的对象，函数结束后消亡，不可引用
      //尽量使用前置
      

69. 组合：
    一个类的某个数据成员是另外一个类的对象，则该对象称为对象成员
    如果类含有对象成员，新类对象初始化时也不想用默认构造函数去初始化对象成员，必须用构造函数的初始化列表去初始化成员对象。
    Complex(int r1 = 0, int r2 = 1, int i1 = 0, int i2 = 1):real(r1, r2), imag(i1, i2) {}
Complex(Rational r, Rational i):real(r), imag(i) {}

70. 继承：

71. 异常处理：
    异常抛出时，throw后操作数初始化该类型的一个临时副本，传回调用该程序的程序，当前函数终止，局部变量被析构

    • throw myerror(“something bad happened”);

      myerror是一个类，它以字符串变量为参数

    • throw int(5)
      int是一个内部类型，5是一个int类型的常数

    • // Class DivideByZeroException to be used in exception
      // handling for throwing an exception on a division by zero.
      class DivideByZeroException {
       public:
          //构造函数
           DivideByZeroException():message("attempted to divide by zero") {}
           const char *what() const {return message;} //返回一个常量字符数组（字符串）
       private:
           const char *message; //记录出现的异常情况
       };
      

72. 容器：
    容器是保存和处理一组有某种关系的同类数据的类型，迭代器是一个抽象指针

73. 栈：

    • LIFO
    • 对于n个不同的元素，给定入栈的顺序，求有多少种出栈顺序。
    • 考察最后一个出栈的元素是第几个入栈的元素
      重要观察：如果最后出栈的是a[i]，则a[i]入栈前a[1]…a[i-1]必然已经出栈，这种出栈的顺序数为f(i-1)
      剩下a[i+1]…a[n]的出栈顺序数为f(n-i)
      卡特兰数：DP复杂度O(n^2)
    • 从另一个角度思考（复杂度O(n)）
      令1表示进栈，0表示出栈，则原问题可转化为求一个2n位、含n个1、n个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数的个数。
      含n个1、n个0的2n位二进制数共有C(2n,n)个，其中不满足条件的有C(2n,n+1)个。
      原因：不满足条件的数在某一位第一次0的个数大于1的个数，从那以后全部按位取反可以得到一个n+1个0，n-1个1的数，这个数与原来的数一一对应（为什么？我已经想清楚了）
    • 栈的链表实现：
      用链表头的指针指向栈顶（不能用tail，因为删除操作必须在栈顶完成）
    • 重要的栈
      函数的调用和返回：
      在栈中记录函数调用返回的地址，一层层push进去
      递归调用栈有深度，不能调用太多次
    • 栈的应用
      DFS
      括号匹配

74. 队列：

    • FIFO

    • 队列的实现：

      • 队头位置不固定

      • 含空单元的循环队列

      • 少用一个存储单元。当顺序存储空间的容量为maxSize时，只允许最多存储maxSize-1个数据元素，此时判断空的条件为 front == rear ,判断满的条件是front == (rear+1) % maxSize;

      • 一般记录两个指针，指向队首队尾

    • 队列的应用
      云计算
      BFS
      排队系统
      滑动窗口的最大值

75. while(cin>>a)
    只要输入的值有效，那么就执行while体内的语句。
    （1）若流是有效的，即流未遇到错误，那么检测成功。
    （2）若遇到文件结束符，或遇到一个无效的输入时（例如本题输入的值不是一个整数）istream对象的状态会变为无效，条件就为假。