C语言能力

一、基础语法能力

1. 变量和数据类型
   • 能够熟练使用基本数据类型，如整型（int）、字符型（char）、浮点型（float、double）等。例如，声明一个整型变量int a = 10;，用于存储整数数据。
   • 理解变量的作用域，包括局部变量（在函数内部声明，只在该函数内有效）和全局变量（在所有函数之外声明，可以在整个程序中访问）。例如，一个全局变量int globalVar = 20;可以在多个函数中被访问和修改。
   • 掌握数据类型的转换，包括隐式类型转换（如int自动转换为double）和显式类型转换（如(int)3.14将浮点数转换为整数）。
2. 运算符
   • 熟练使用算术运算符（+、-、*、/、%），例如计算两个整数的商和余数int quotient = a / b; int remainder = a % b;。
   • 理解逻辑运算符（&&、||、!），用于条件判断。例如，判断两个条件是否同时满足if (a > 0 && b < 10) { /* do something */ }。
   • 掌握关系运算符（>、<、>=、<=、==、!=），用于比较两个值的大小或相等性。例如，比较两个变量是否相等if (a == b) { /* do something */ }。
   • 熟悉位运算符（&、|、^、~、<<、>>），用于对二进制位进行操作。例如，将一个数的第3位清零a &= ~(1 << 2);。
3. 控制结构
   • 能够使用if、else、else if语句进行条件判断。例如，根据成绩输出等级：
     c复制

     if (score >= 90) {
         printf("A\n");
     } else if (score >= 80) {
         printf("B\n");
     } else {
         printf("C\n");
     }
     

   • 掌握循环结构，包括for循环、while循环和do - while循环。例如，使用for循环输出1到10的数字：
     c复制

     for (int i = 1; i <= 10; i++) {
         printf("%d\n", i);
     }
     

   • 理解break和continue语句的作用。break用于跳出循环，continue用于跳过当前循环的剩余部分，进入下一次循环。例如，在循环中跳过偶数：
     c复制

     for (int i = 1; i <= 10; i++) {
         if (i % 2 == 0) {
             continue;
         }
         printf("%d\n", i);
     }
     

二、函数和模块化编程能力

1. 函数定义和调用
   • 能够定义函数，包括函数的返回类型、参数列表和函数体。例如，定义一个计算两个整数和的函数：
     c复制

     int add(int a, int b) {
         return a + b;
     }
     

   • 理解函数的参数传递方式，包括值传递（传递参数的副本）和地址传递（传递参数的地址）。例如，通过地址传递修改参数的值：
     c复制

     void increment(int *p) {
         (*p)++;
     }
     int main() {
         int num = 5;
         increment(&num);
         printf("%d\n", num); // 输出6
         return 0;
     }
     

   • 掌握函数的返回值，可以返回基本数据类型、指针、结构体等。例如，返回一个指向动态分配内存的指针：
     c复制

     int* createArray(int size) {
         int* arr = (int*)malloc(size * sizeof(int));
         return arr;
     }
     

2. 模块化编程
   • 能够将程序分解为多个模块，每个模块实现特定的功能。例如，将一个大型程序分为输入模块、处理模块和输出模块。
   • 使用头文件（.h文件）来声明函数原型和全局变量，方便在多个源文件中共享。例如，创建一个math.h头文件：
     c复制

     // math.h
     int add(int a, int b);
     int subtract(int a, int b);
     

   • 在源文件中实现这些函数，并通过#include指令引入头文件。例如：
     c复制

     // math.c
     #include "math.h"
     int add(int a, int b) {
         return a + b;
     }
     int subtract(int a, int b) {
         return a - b;
     }
     

三、指针和内存管理能力

1. 指针操作
   • 理解指针的概念，指针是一个变量，存储另一个变量的地址。例如，声明一个指针int* p;，并使其指向一个整数变量p = &a;。
   • 能够通过指针间接访问和修改变量的值。例如，通过指针修改变量*p = 10;。
   • 掌握指针的运算，包括指针的加减运算（用于数组操作）和指针的比较。例如，判断两个指针是否指向同一个变量if (p == q) { /* do something */ }。
2. 动态内存分配
   • 熟练使用malloc、calloc、realloc和free函数进行动态内存分配和释放。例如，动态分配一个整数数组：
     c复制

     int* arr = (int*)malloc(10 * sizeof(int));
     if (arr == NULL) {
         printf("Memory allocation failed\n");
         return -1;
     }
     // 使用数组...
     free(arr);
     

   • 理解动态内存分配的用途，如处理不确定大小的数据集合。例如，根据用户输入动态调整数组大小：
     c复制

     int size = 5;
     int* arr = (int*)malloc(size * sizeof(int));
     // 用户请求增加数组大小
     size += 5;
     arr = (int*)realloc(arr, size * sizeof(int));
     

四、数组和字符串能力

1. 数组操作
   • 能够声明和初始化数组，包括一维数组和多维数组。例如，声明一个二维数组：
     c复制

     int matrix[3][3] = {
         {1, 2, 3},
         {4, 5, 6},
         {7, 8, 9}
     };
     

   • 掌握数组的遍历方法，如使用循环遍历数组元素。例如，计算数组元素的总和：
     c复制

     int sum = 0;
     for (int i = 0; i < 10; i++) {
         sum += arr[i];
     }
     

   • 理解数组的内存布局，数组在内存中是连续存储的。例如，通过指针访问数组元素*(arr + i)。
2. 字符串处理
   • 熟悉字符串的存储方式，字符串是以字符数组的形式存储，以空字符\0结尾。例如，声明一个字符串char str[] = "Hello";。
   • 掌握字符串处理函数，如strlen（计算字符串长度）、strcpy（复制字符串）、strcat（连接字符串）和strcmp（比较字符串）。例如，比较两个字符串是否相等：
     c复制

     char str1[] = "Hello";
     char str2[] = "Hello";
     if (strcmp(str1, str2) == 0) {
         printf("Strings are equal\n");
     }
     

   • 能够使用指针操作字符串，例如通过指针遍历字符串char* p = str; while (*p != '\0') { /* do something */ p++; }。

五、结构体和联合体能力

1. 结构体定义和使用
   • 能够定义结构体，用于存储不同类型的数据。例如，定义一个学生结构体：
     c复制

     struct Student {
         int id;
         char name[50];
         float score;
     };
     

   • 掌握结构体变量的声明和初始化。例如，声明并初始化一个学生变量：
     c复制

     struct Student s1 = {1, "Alice", 90.5};
     

   • 理解结构体指针的使用，通过结构体指针访问成员变量。例如，通过指针修改学生分数：
     c复制

     struct Student* p = &s1;
     p->score = 95.0;
     

2. 联合体定义和使用
   • 理解联合体的概念，联合体的所有成员共享同一块内存。例如，定义一个联合体：
     c复制

     union Data {
         int i;
         float f;
         char str[20];
     };
     

   • 掌握联合体的使用，根据需要存储不同类型的数据。例如，存储一个整数或浮点数：
     c复制

     union Data d;
     d.i = 10;
     printf("Integer: %d\n", d.i);
     d.f = 99.99;
     printf("Float: %f\n", d.f);
     

六、文件操作能力

1. 文件打开和关闭
   • 熟练使用fopen函数打开文件，指定文件名和模式（如读模式"r"、写模式"w"、追加模式"a"等）。例如，打开一个文件进行写入：
     c复制

     FILE* fp = fopen("example.txt", "w");
     if (fp == NULL) {
         printf("Failed to open file\n");
         return -1;
     }
     

   • 使用fclose函数关闭文件，释放文件资源。例如：
     c复制

     fclose(fp);
     

2. 文件读写操作
   • 掌握文件的读写函数，如fprintf、fscanf、fputs、fgets、fwrite和fread。例如，向文件写入字符串：
     c复制

     fprintf(fp, "Hello, World!\n");
     

   • 能够读取文件内容，例如逐行读取文件：
     c复制

     char buffer[100];
     while (fgets(buffer, sizeof(buffer), fp) != NULL) {
         printf("%s", buffer);
     }
     

   • 理解文件指针的位置操作，如fseek、ftell和rewind函数。例如，将文件指针移动到文件开头：
     c复制

     rewind(fp);
     

七、高级特性能力（可选）

1. 位域
   • 理解位域的概念，用于在结构体中紧凑地存储数据。例如，定义一个位域结构体：
     c复制

     struct BitField {
         unsigned int a : 3; // 3位
         unsigned int b : 4; // 4位
     };
     

   • 掌握位域的使用，通过位域访问和修改数据。
2. 预处理器指令
   • 熟练使用#define、#include、#ifdef、#ifndef、#else、#endif等预处理器指令。例如，定义宏：
     c复制

     #define MAX(a, b) ((a) > (b) ? (a) : (b))
     

   • 使用条件编译指令控制代码的编译，例如：
     c复制

     #ifdef DEBUG
     printf("Debug mode\n");
     #endif
     

3. 多线程编程（C11标准）
   • 了解C11标准中的线程支持，使用_Thread_local关键字声明线程局部变量。例如：
     c复制

     _Thread_local int threadVar = 0;
     

   • 熟悉线程创建和同步机制，如互斥锁等。
     掌握这些能力后，就可以使用C语言编写高效、可靠和可维护的程序，应用于系统编程、嵌入式开发、算法实现等多种领域。

最全 C_C++ 重点知识点详解

1.C/C++ 关键字

1.1 static（静态）变量

在 C 中，关键字 static 是静态变量：

• 静态变量只会初始化一次，然后在这函数被调用过程中值不变。
• 在文件内定义静态变量（函数外），作用域是当前文件，该变量可以被文件内所有函数访问，不能被其他文件函数访问。为本地的全局变量，只初始化一次。

在 C++ 中，类内数据成员可以定义为 static

• 对于非静态数据成员，每个对象有一个副本。而静态数据成员是类的成员，只存在一个副本，被所有对象共享。
• 静态成员变量没有实例化对象也可以使用，“类名：静态成员变量”
• 静态成员变量初始化在类外，但是 private 和 protected 修饰的静态成员不能类外访问。

class Stu
{
public:
	static int age;
private:
	static int height;
};
//初始化静态成员变量
int Stu::age = 19;
int Stu::height = 180;
int main()
{
	cout<<Stu::age<<endl;//输出19；
	cout<<Stu::height<<endl;//错误的，私有无法访问。
	Stu s;
	cout<<s::age<<endl;//输出19；
	cout<<s::height<<endl;//错误的，私有无法访问。
	return 0;
}

• 在类中，static 修饰的函数是静态成员函数。静态成员函数一样属于类，不属于对象，被对象共享。静态成员函数没有 this 指针，不能访问非静态的函数和变量，只能访问静态的。

与全局变量相比，静态数据成员的优势：

• 全局变量作用域是整个工程，而 static 作用域是当前文件，避免命名冲突
• 静态数据成员可以是 private 成员，而全局变量不能，实现信息隐藏

为什么静态成员变量不能在类内初始化？

因为类的声明可能会在多处引用，每次引用都会初始化一次，分配一次空间。这和静态变量只能初始化一次，只有一个副本冲突，因此静态成员变量只能类外初始化。

为什么 static 静态变量只能初始化一次？

所有变量都只初始化一次。但是静态变量在全局区（静态区），而自动变量在栈区。静态变量生命周期和程序一样，只创建初始化一次就一直存在，不会销毁。而自动变量生命周期和函数一样，函数调用就进行创建初始化，函数结束就销毁，所以每一次调用函数就初始化一次。

在头文件中定义静态变量是否可行？

不可行，在头文件中定义的一个 static 变量，对于包含该头文件的所有源文件，实质上在每个源文件内定义了一个同名的 static 变量。造成资源浪费，可能引起 bug

静态变量什么时候初始化

• 初始化只有一次，但是可以多次赋值，在主程序之前，编译器已经为其分配好了内存。
• 静态局部变量和全局变量一样，数据都存放在全局区域，所以在主程序之前，编译器已经为其分配好了内存，但在 C 和 C++ 中静态局部变量的初始化节点又有点不太一样。
• 在 C 中，初始化发生在代码执行之前，编译阶段分配好内存之后，就会进行初始化，所以我们看到在 C 语言中无法使用变量对静态局部变量进行初始化，在程序运行结束，变量所处的全局内存会被全部回收。
• 而在 C++ 中，初始化时在执行相关代码时才会进行初始化，C++ 标准定为全局或静态对象是有首次用到时才会进行构造，并通过 atexit() 来管理。在程序结束，按照构造顺序反方向进行逐个析构。所以在 C++ 中是可以使用变量对静态局部变量进行初始化的。

1.2 const 的作用

常量类型也称为 const 类型，使用 const 修饰变量或者对象

在 C 中，const 的作用为：

• 定义变量（局部或者全局）为常量

const int a = 10; //常量定义时，必须初始化

• 修饰函数的参数，函数体内不能修改这个参数的值
• 修饰函数的返回值
• const 修饰的返回值类型为指针，返回的指针不能被修改，而且只能符给被 const 修饰的指针

const char* GetString()
{
	//...
}
int main()
{
	char *str = GetString();//错误，str没被const修饰
	const char *str = GetString();//正确
}

• const 修饰的返回值类型为引用，那么函数调用表达式不能做左值（函数不能被赋值）

const int & add(int &a , int &b)
{
	//..
}
int main()
{
	add(a,b) = 4;//错误，const修饰add的返回引用，不能做左值
}

• const 修饰的返回值类型为普通变量，由于返回是普通临时变量，const 修饰没意义。

在 c++ 中，const 还有作用为：

• const 修饰类内的数据成员。表示这个数据成员在某个对象的生命周期是常量，不同对象的值可以不一样，因此 const 成员函数不能在类内初始化。
• const 修饰类内的成员函数。那么这个函数就不能修改对象的成员变量

const 的优点？

1. 进行类型检查，使编译器对处理内容有更多了解。
2. 避免意义模糊的数字出现，类似宏定义，方便对参数进行修改。
3. 保护被修饰的内容，防止被意外修改
4. 为函数重载提供参考

class A
{
	void f(int i){...} //非const对象调用
	void f(int i) const {...}//const对象调用
}

5. 节省内存
6. 提高程序效率（编译器不为普通 const 常量分配存储空间，而保存在符号表中。称为一个编译期间的常量，没有存储和读内存的操作）

什么时候使用 const？

• 修饰一般常量
• 修饰对象
• 修饰常指针

const int *p;
int const *p;
int *const p;
const int *const p;

• 修饰常引用
• 修饰函数的参数
• 修饰函数返回值
• 修饰类的成员函数
• 修饰另一文件中引用的变量

extern const int j;

const 和指针（常量指针、指针常量）

• 常量指针（const 修饰常量，const 在 * 的左边）

const int *p = &a; // const修饰int,指针的指向可以修改，但是指针指向的值不能改
int const *p;//同上
p = &b;//正确
*p = 10;//错误

• 指针常量（const 修饰指针，const 在 * 的右边）

int *const p = &a;//const修饰指针，指针的指向不可以改，但是指针指向的值可以改
*p = 10;//正确
p = &b;//错误

• const 都修饰指针和常量（指针和常量都不能修改）

const int *const p;
int const *const p;

顶层 const 和底层 const

• 顶层 const（指针常量）：指的是 const 修饰的变量本身是一个指针，指针不能变
• 底层 const（常量指针）：指的是 const 修饰的变量本身是一个常量，常量不能变

const 和 static 的作用

static

• 不考虑类的情况
• 隐藏。所有不加 static 的全局变量和函数具有全局可见性，可以在其他文件中使用，加了之后只能在该文件所在的编译模块中使用
• 默认初始化为 0，包括未初始化的全局静态变量与局部静态变量，都存在全局未初始化区
• 静态变量在函数内定义，始终存在，且只进行一次初始化，具有记忆性，其作用范围与局部变量相同，函数退出后仍然存在，但不能使用
• 考虑类的情况
• static 成员变量：只与类关联，不与类的对象关联。定义时要分配空间，不能在类声明中初始化，必须在类定义体外部初始化，初始化时不需要标示为 static；可以被非 static 成员函数任意访问。
• static 成员函数：不具有 this 指针，无法访问类对象的非 static 成员变量和非 static 成员函数；不能被声明为 const、虚函数和 volatile；可以被非 static 成员函数任意访问
  const
• 不考虑类的情况
• const 常量在定义时必须初始化，之后无法更改
• const 形参可以接收 const 和非 const 类型的实参，例如 // i 可以是 int 型或者 const int 型 void fun(const int& i){ //…}
• 考虑类的情况
• const 成员变量：不能在类定义外部初始化，只能通过构造函数初始化列表进行初始化，并且必须有构造函数；不同类对其 const 数据成员的值可以不同，所以不能在类中声明时初始化
• const 成员函数：const 对象不可以调用非 const 成员函数；非 const 对象都可以调用；不可以改变非 mutable（用该关键字声明的变量可以在 const 成员函数中被修改）数据的值
  补充一点 const 相关：const 修饰变量是也与 static 有一样的隐藏作用。只能在该文件中使用，其他文件不可以引用声明使用。 因此在头文件中声明 const 变量是没问题的，因为即使被多个文件包含，链接性都是内部的，不会出现符号冲突

1.3 switch

语句中 case 结尾是否必须加 break
一般必须在 case 结尾加 break。 因为通过 switch 确认入口点，一直往下执行，直到遇见 break。否则会执行完这个 case 后执行后面的 case，default 也会执行。 注，switch（c），c 可以是 int、long、char 等，但是不能是 float

1.4 volatile 的作用

volatile 关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改，比如：操作系统、硬件或者其它线程等。

• 编译器不再进行优化，从而可以提供对特殊地址的稳定访问。
• 系统总是重新从它所在的内存读取数据，不会利用 cache 中原有的数值。
• 用于多线程被多个任务共享的变量，或者并行设备的硬件寄存器

1.5 断言 ASSERT() 是什么？

是一个调试程序使用的宏。 定义在 <assert.h> 中，用于判断是否出现非法数据。括号内的值 为 false(0)，程序报错，终止运行。

ASSERT(n != 0);// n为0的时候程序报错
k = 10/n;

ASSERT() 在 Debug 中有，在 Release 中被忽略。 ASSERT() 是宏，assert() 是 ANSCI 标准中的函数，但是影响程序性能。

1.6 枚举变量的值计算

#include<stdio.h>
int main()
{
	enum {a,b=5,c,d=4,e};
	printf("%d %d %d %d %d",a,b,c,d,e); 
	return 0;
}

输出为 0 5 6 4 5

1.7 字符串存储方式

1. 字符串存储在栈中

char str1[] = "abc";
char str2[] = "abc";

2. 字符串存储在常量区

char *str3 = "abc";
char *str4 = "abc";

3. 字符串存储在堆中

char *str5 = （char*）malloc(4);
strcpy(str5,"abc");
char *str6 = （char*）malloc(4);
strcpy(str6,"abc");

4. 字符串是否相等

• str1 ！= str2 ，str1 和 str2 是两个字符串的首地址。
• str3 == srt4 ， str3 和 str4 是常量的地址，同样字符串在常量区只存在一份。
• str5 ！= str6 ，str5 和 str6 是指向堆的地址。
  

1.8 程序内存分区

内存高地址	栈区
	堆区
	全局 / 静态区 （.bss 段 .date 段）
	常量区
内存低地址	代码区

 1. 栈区（stack） * 临时创建的局部变量存放在栈区。 * 函数调用时，其入口参数存放在栈区。 * 函数返回时，其返回值存放在栈区。 * const 定义的局部变量存放在栈区。 2. 堆区（heap） * 堆区用于存放程序运行中被动态分布的内存段，可增可减。 * malloc 函数分布的内存，必须用 free 进行内存释放，否则会造成内存泄漏。 3. 全局区（静态区） * （c 语言中）全局区有. bss 段和. data 段组成，可读可写。 * C++ 不分 bss 和 data 4. .bss 段 * 未初始化的全局变量存放在. bss 段。 * 初始化为 0 的全局变量和初始化为 0 的静态变量存放在. bss 段。 * .bss 段不占用可执行文件空间，其内容有操作系统初始化。 5. .data 段 * 已经初始化的全局变量存放在. data 段。 * 静态变量存放在. data 段。 * .data 段占用可执行文件空间，其内容有程序初始化。 * const 定义的全局变量存放在. rodata 段。 6. 常量区 * 字符串存放在常量区。 * 常量区的内容不可以被修改。 7. 代码区 * 程序执行代码（二进制代码文件）存放在代码区。

1.9 * p++ 和 （* p）++ 的区别

• • p++ 先完成取地址，然后对指针地址进行 ++，再取值
• （* p）++，先完成取值，再对值进行 ++

1.10 new / delete 与 malloc / free 的异同

• 相同点
• 都可用于内存的动态申请和释放
• 不同点
• new / delete 是 C++ 运算符，malloc / free 是 C/C++ 语言标准库函数
• new 自动计算要分配的空间大小，malloc 需要手工计算
• malloc 和 free 返回的是 void 类型指针（必须进行类型转换），new 和 delete 返回的是具体类型指针。
• new 是类型安全的，malloc 不是。例如：

int *p = new float[2]; //编译错误
int *p = (int*)malloc(2 * sizeof(double));//编译无错误

• malloc / free 需要库文件支持，new / delete 不用
• new 是封装了 malloc，直接 free 不会报错，但是这只是释放内存，而不会析构对象

1.11 new 和 delete 是如何实现的？

• new 的实现过程是：首先调用名为 operator new 的标准库函数，分配足够大的原始为类型化的内存，以保存指定类型的一个对象；接下来运行该类型的一个构造函数，用指定初始化构造对象；最后返回指向新分配并构造后的的对象的指针
• delete 的实现过程：对指针指向的对象运行适当的析构函数；然后通过调用名为 operator delete 的标准库函数释放该对象所用内存

1.12 被 free 回收的内存是立即返还给操作系统吗？

不是的，被 free 回收的内存会首先被 ptmalloc 使用双链表保存起来，当用户下一次申请内存的时候，会尝试从这些内存中寻找合适的返回。这样就避免了频繁的系统调用，占用过多的系统资源。同时 ptmalloc 也会尝试对小块内存进行合并，避免过多的内存碎片。

1.13 C++ 中几种类型的 new

1. plain new
   言下之意就是普通的 new，就是我们常用的 new，在 C++ 中定义如下：

void* operator new(std::size_t) throw(std::bad_alloc);
void operator delete(void *) throw();

plain new 在空间分配失败的情况下，抛出异常 std::bad_alloc 而不是返回 NULL

#include <iostream>
#include <string>
using namespace std;
int main()
{
	try
	{
		char *p = new char[10e11];
		delete p;
	}
	catch (const std::bad_alloc &ex)
	{
		cout << ex.what() << endl;
	}
	return 0;
}
//执行结果：bad allocation

2. nothrow new
   nothrow new 在空间分配失败的情况下是不抛出异常，而是返回 NULL，定义如下：

void * operator new(std::size_t,const std::nothrow_t&) throw();
void operator delete(void*) throw();

#include <iostream>
#include <string>
using namespace std;
int main()
{
	char *p = new(nothrow) char[10e11];
	if (p == NULL) 
	{
		cout << "alloc failed" << endl;
	}
	delete p;
	return 0;
}
//运行结果：alloc failed

3. placement new
   这种 new 允许在一块已经分配成功的内存上重新构造对象或对象数组。placement new 不用担心内存分配失败，因为它根本不分配内存，它做的唯一一件事情就是调用对象的构造函数。定义如下：

void* operator new(size_t,void*);
void operator delete(void*,void*);

使用 placement new 需要注意两点：

• palcement new 的主要用途就是反复使用一块较大的动态分配的内存来构造不同类型的对象或者他们的数组
• placement new 构造起来的对象数组，要显式的调用他们的析构函数来销毁（析构函数并不释放对象的内存），千万不要使用 delete，这是因为 placement new 构造起来的对象或数组大小并不一定等于原来分配的内存大小，使用 delete 会造成内存泄漏或者之后释放内存时出现运行时错误。

#include <iostream>
#include <string>
using namespace std;
class ADT{
	int i;
	int j;
public:
	ADT(){
		i = 10;
		j = 100;
		cout << "ADT construct i=" << i << "j="<<j <<endl;
	}
	~ADT(){
		cout << "ADT destruct" << endl;
	}
};
int main()
{
	char *p = new(nothrow) char[sizeof ADT + 1];
	if (p == NULL) {
		cout << "alloc failed" << endl;
	}
	ADT *q = new(p) ADT;  //placement new:不必担心失败，只要p所指对象的的空间足够ADT创建即可
	//delete q;//错误!不能在此处调用delete q;
	q->ADT::~ADT();//显示调用析构函数
	delete[] p;
	return 0;
}
//输出结果：
//ADT construct i=10j=100
//ADT destruct

1.14 delete p、delete [] p、allocator 都有什么作用？

• delete p ，为消除一个对象。
• delete[] 时，数组中的元素按逆序的顺序进行销毁；
• new 在内存分配上面有一些局限性，new 的机制是将内存分配和对象构造组合在一起，同样的，delete 也是将对象析构和内存释放组合在一起的。allocator 将这两部分分开进行，allocator 申请一部分内存，不进行初始化对象，只有当需要的时候才进行初始化操作。

1.15 malloc 与 free 的实现原理？

1、 在标准 C 库中，提供了 malloc/free 函数分配释放内存，这两个函数底层是由 brk、mmap、munmap 这些系统调用实现的;
2、 brk 是将数据段 (.data) 的最高地址指针_edata 往高地址推, mmap 是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系；
3、 malloc 小于 128k 的内存，使用 brk 分配内存，将_edata 往高地址推；malloc 大于 128k 的内存，使用 mmap 分配内存，在堆和栈之间找一块空闲内存分配；brk 分配的内存需要等到高地址内存释放以后才能释放，而 mmap 分配的内存可以单独释放。当最高地址空间的空闲内存超过 128K（可由 M_TRIM_THRESHOLD 选项调节）时，执行内存紧缩操作（trim）。在上一个步骤 free 的时候，发现最高地址空闲内存超过 128K，于是内存紧缩。
4、 malloc 是从堆里面申请内存，也就是说函数返回的指针是指向堆里面的一块内存。操作系统中有一个记录空闲内存地址的链表。当操作系统收到程序的申请时，就会遍历该链表，然后就寻找第一个空间大于所申请空间的堆结点，然后就将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。

1.16 malloc、realloc、calloc 的区别

• malloc 函数

void* malloc(unsigned int num_size);
int *p = malloc(20*sizeof(int));申请20个int类型的空间；

• calloc 函数

void* calloc(size_t n,size_t size);
int *p = calloc(20, sizeof(int));

省去了人为空间计算；malloc 申请的空间的值是随机初始化的，calloc 申请的空间的值是初始化为 0 的；

• realloc 函数

void realloc(void *p, size_t new_size);

给动态分配的空间分配额外的空间，用于扩充容量。

1.17 exit() 和 return 的区别

• return 是语言级的，标志调用堆栈的返回。是从当前函数的返回，main（）中 return 的退出程序
• exit（）是函数，强行退出程序，并返回值给系统
• return 实现函数逻辑，函数的输出。exit（）只用来退出。

1.18 extern 和 export 的作用

变量的声明有两种情况：

1. 一种是需要建立存储空间的。例如：int a 在定义的时候就已经建立了存储空间。
2. 另一种是不需要建立存储空间的。 例如：extern int a 其中变量 a 是在别的文件中定义的。
3. 总之就是：把建立空间的声明成为 “定义”，把不需要建立存储空间的成为 “声明”。

• extern
• 普通变量、类。结构体
• export（C++ 中新增）
• 和 exturn 类似，但是用作模板
• 使用该关键字可实现模板函数的外部调用
• 模板实现的时候前面加上 export，别的文件包含头文件就可用该模板

extern"C" 的用法

在 C 语言的头文件中，对其外部函数只能指定为 extern 类型，C 语言中不支持 extern “C” 声明，在. c 文件中包含了 extern “C” 时会出现编译语法错误。** 所以使用 extern “C” 全部都放在于 cpp 程序相关文件或其头文件中。
C++ 中调用 C 代码：

//xx.h
extern int add(...)
//xx.c
int add(){
}
//xx.cpp
extern "C" {
#include "xx.h"
}

C 调用 C++ 函数

//xx.h
extern "C"{
int add();
}
//xx.cpp
int add(){
}
//xx.c
extern int add();

1.19 C++ 中，explicit 的作用

explicit 阻止隐式转换

• 隐式转换

String s1 = "hello";
//进行隐式转换，等价于
String s1 = String("hello");

• explicit 阻止隐式转换

class Test1
{
public：
	Test1(int n){ num = n }
private:
	int num;
}
class Test2
{
public：
	explicit Test2(int n){ num = n }
private:
	int num;
}
int main()
{
	Test1 t1 = 1; //正确，隐式转换
	Test2 t2 = 1;//错误，禁止隐式转换
	Test2 t2(1); //正确，可与显示调用
}

1.20 C++ 的异常处理

C++ 中的异常处理机制主要使用 try、throw 和 catch 三个关键字

#include <iostream>
using namespace std;
int main()
{
double m = 1, n = 0;
try {
cout << "before dividing." << endl;
if (n == 0)
throw - 1;  //抛出int型异常
else if (m == 0)
throw - 1.0;  //拋出 double 型异常
else
cout << m / n << endl;
cout << "after dividing." << endl;
}
catch (double d) {
cout << "catch (double)" << d << endl;
}
catch (...) {
cout << "catch (...)" << endl;
}
cout << "finished" << endl;
return 0;
}
//运行结果
//before dividing.
//catch (...)
//finished

代码中，对两个数进行除法计算，其中除数为 0。可以看到以上三个关键字，

• 程序的执行流程是先执行 try 包裹的语句块，如果执行过程中没有异常发生，则不会进入任何 catch 包裹的语句块，如果发生异常，则使用 throw 进行异常抛出，再由 catch 进行捕获，
• throw 可以抛出各种数据类型的信息，代码中使用的是数字，也可以自定义异常 class。catch 根据 throw 抛出的数据类型进行精确捕获（不会出现类型转换），如果匹配不到就直接报错，可以使用 catch(…) 的方式捕获任何异常（不推荐）。
• 当然，如果 catch 了异常，当前函数如果不进行处理，或者已经处理了想通知上一层的调用者，可以在 catch 里面再 throw 异常。

1.21 回调函数

• 把一段可执行的代码像参数传递那样传给其他代码，而这段代码会在某个时刻被调用执行，这就叫做回调。
• 如果代码立即被执行就称为同步回调，如果过后再执行，则称之为异步回调。
• 回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。
• 主函数和回调函数是在同一层的，而库函数在另外一层。如果库函数对我们不可见，我们修改不了库函数的实现，也就是说不能通过修改库函数让库函数调用普通函数那样实现，那我们就只能通过传入不同的回调函数
• sort()，中自定义的 cmp 就是回调函数

1.22 C++ 中，mutable 的作用

mutable 的中文意思是 “可变的，易变的”，在 C++ 中，mutable 也是为了突破 const 的限制而设置的。被 mutable 修饰的变量，将永远处于可变的状态，即使在一个 const 函数中。

class person
{
int m_A;
mutable int m_B;//特殊变量 在常函数里值也可以被修改
public:
 void add() const//在函数里不可修改this指针指向的值 常量指针
 {
m_A=10;//错误  不可修改值，this已经被修饰为常量指针
m_B=20;//正确
 }
}
int main()
{
	const person p;//修饰常对象 不可修改类成员的值
	p.m_A=10;//错误，被修饰了指针常量
	p.m_B=200;//正确，特殊变量，修饰了mutable
}

2 . 内存分配

2.1 C++ 内存分配

见 1.8

2.2 内存泄漏

内存泄露的原因

内存泄漏是指堆内存的泄漏。使用 malloc,、realloc、 new 等函数从堆中分配到块内存，使用完后，程序必须负责相应的调用 free 或 delete 释放该内存块，如果没有释放内存这块内存就不能被再次使用，我们就说这块内存泄漏了

避免内存泄露的几种方式

• 计数法：使用 new 或者 malloc 时，让该数 + 1，delete 或 free 时，该数 - 1，程序执行完打印这个计数，如果不为 0 则表示存在内存泄露
• 一定要将基类的析构函数声明为虚函数（这样子类的析构函数必须重新实现，避免忘记释放内存）
• 对象数组的释放一定要用 delete []
• 有 new 就有 delete，有 malloc 就有 free，保证它们一定成对出现

内存泄漏检测工具

• 从 Linux 下可以使用 Valgrind 工具
• Windows 下可以使用 CRT 库

2.3 栈默认的大小

• Windows 下是 2MB
• Linux 下是 8MB（ulimit-s 设置）

2.4 sizeof() 和 strlen() 的区别

int a ,b;
a = strlen("\0");
b = sizeof("\0");
// a = 0 , b = 2;

• sizeof() 是 c 关键字，计算内存大小，字节单位
• strlen() 是函数，计算字符串的长度，到 \ 0 结束
• sizeof 是编译确定的，strlen 是运行确定的

int a,b,c;
char str[20] = "0123456789";
const char *str2 = "0123456789";
a = strlen(str);
b = sizeof(str);
c = sizeof(&str);
d = strlen(str2);
e = sizeof(str2);
// a = 10 , b = 20 , c = 4(指针大小);
// d = 10 , e = 4(指针大小)

2.5 struct 结构体的数据对齐

为什么结构体的 sizeof 返回值一般大于期望？

• struct 的 sizeof 是所有成员数据对其后长度相加
• union 的 sizeof 是取最大的成员长度（所有成员共用一个内存）

struct 数据对其的目的？

• 是编译器的一种计算手段，在空间和复杂度上的平衡，在空间浪费可接收的前提下 cpu 运算最快处理
• 32 位数据传输是 4 字节（数据字长），struct 进行 4 的倍数对其。64 位数据传输是 8 字节，8 的倍数对其
• 对齐的目的是要让数据访问更高效，一般来说，数据类型的对齐要求和它的长度是一致的，比如，

  char 是 1
  short 是 2
  int 是 4
  double 是 8

• 这不是巧合，比如 short，2 对齐保证了 short 只可能出现在一个读取单元的 0, 2, 4, 6 格，而不会出现在 1, 3, 5, 7 格；
• 再比如 int，4 对齐保证了一个读取单元可以装载 2 个 int——在 0 或者 4 格。
• 从根本上杜绝了同一个数据横跨读取单元的问题。

修改默认的数据对齐

• #pragma pack(n)，编译器按照 n 字节对其
• #pragma pack( )，取消自定义对其
• __ attribute__((aligned(n))) ，让结构体成员对其在 n 字节自然边界上，如果成员大于 n，按照最大成员长度
• __ attribute__((packed))，取消编译过程的对齐，按照实际占用字节对其

C++11 中内存对其关键字

• alignof，计算出类型对齐的方式
• alignas，指定结构体的对齐方式

struct Info {
  uint8_t a;
  uint16_t b;
  uint8_t c;
};
std::cout << sizeof(Info) << std::endl;   // 6  2 + 2 + 2
std::cout << alignof(Info) << std::endl;  // 2
//alignas将内存对齐调整为4个字节。所以sizeof(Info2)的值变为了8。
struct alignas(4) Info2 {
  uint8_t a;
  uint16_t b;
  uint8_t c;
};
std::cout << sizeof(Info2) << std::endl;   // 8  4 + 4
std::cout << alignof(Info2) << std::endl;  // 4

若 alignas 小于自然对齐的最小单位，则被忽略。

2.6 堆和栈的区别

• 申请方式不同。
• 栈由系统自动分配。
• 堆是自己申请和释放的。
• 申请大小限制不同。
• 栈顶和栈底是之前预设好的，栈是向栈底扩展，大小固定，可以通过 ulimit -a 查看，由 ulimit -s 修改。
• 堆向高地址扩展，是不连续的内存区域，大小可以灵活调整。
• 申请效率不同。
• 栈由系统分配，速度快，不会有碎片。
• 堆由程序员分配，速度慢，且会有碎片。
• 栈空间默认是 4M, 堆区一般是 1G - 4G
• 速度不同
• 毫无疑问是栈快一点。
• 因为操作系统会在底层对栈提供支持，会分配专门的寄存器存放栈的地址，栈的入栈出栈操作也十分简单，并且有专门的指令执行，所以栈的效率比较高也比较快。
• 而堆的操作是由 C/C++ 函数库提供的，在分配堆内存的时候需要一定的算法寻找合适大小的内存。并且获取堆的内容需要两次访问，第一次访问指针，第二次根据指针保存的地址访问内存，因此堆比较慢。

2.7 形参和实参的区别

• 形参变量只有在被调用时才分配内存单元，在调用结束时， 即刻释放所分配的内存单元。
• 实参可以是常量、变量、表达式、函数等， 无论实参是何种类型的量，在进行函数调用时，它们都必须具有确定的值， 以便把这些值传送给形参。
• 实参和形参在数量上，类型上，顺序上应严格一致， 否则会发生 “类型不匹配” 的错误。
• 函数调用中发生的数据传送是单向的。 即只能把实参的值传送给形参，而不能把形参的值反向地传送给实参。
• 当形参和实参不是指针类型时，在该函数运行时，形参和实参是不同的变量，他们在内存中位于不同的位置，形参将实参的内容复制一份，在该函数运行结束的时候形参被释放，而实参内容不会改变。

3 . 指针

3.1 指针的优点？

指针变量和一般变量区别，一般变量是包含的是数据，而指针变量包含的是地址

• 动态分配内存，直接操作内存，效率高
• 实现动态数据结构（树、链表）
• 高效的 “复制” 数据

3.2 引用和指针

• 指针是一个变量，存储的是一个地址，引用跟原来的变量实质上是同一个东西，是原变量的别名
• 指针可以有多级，引用只有一级
• 指针可以为空，引用不能为 NULL 且在定义时必须初始化
• 指针在初始化后可以改变指向，而引用在初始化之后不可再改变
• sizeof 指针得到的是本指针的大小（4 字节），sizeof 引用得到的是引用所指向变量的大小
• 当把指针作为参数进行传递时，也是将实参的一个拷贝传递给形参，两者指向的地址相同，但不是同一个变量，在函数中改变这个变量的指向不影响实参，而引用却可以。
• 引用本质是一个指针，同样会占 4 字节内存；指针是具体变量，需要占用存储空间（具体情况还要具体分析）。
• 引用在声明时必须初始化为另一变量；指针声明和定义可以分开，可以先只声明指针变量而不初始化，等用到时再指向具体变量。

3.3 数组和指针

• 数组在内存中是连续存放的，开辟一块连续的内存空间；数组所占存储空间：sizeof（数组名）；数组大小：sizeof(数组名)/sizeof(数组元素数据类型)；
• 用运算符 sizeof 可以计算出数组的容量（字节数）。sizeof§,p 为指针得到的是一个指针变量的字节数（4），而不是 p 所指的内存容量。
• 编译器为了简化对数组的支持，实际上是利用指针实现了对数组的支持。具体来说，就是将表达式中的数组元素引用转换为指针加偏移量的引用。
• 在向函数传递参数的时候，如果实参是一个数组，那用于接受的形参为对应的指针。也就是传递过去是数组的首地址而不是整个数组，能够提高效率；
• 在使用下标的时候，两者的用法相同，都是原地址加上下标值，不过数组的原地址就是数组首元素的地址是固定的，指针的原地址就不是固定的。

数组名和指针

• 二者均可通过增减偏移量来访问数组中的元素。
• 数组名不是真正意义上的指针，可以理解为常指针，所以数组名没有自增、自减等操作。
• 当数组名当做形参传递给调用函数后，就失去了原有特性，退化成一般指针，多了自增、自减操作，但 sizeof 运算符不能再得到原数组的大小了。

3.4 指针的加法

指针加上 n，为加上 n 个指针类型的长度

unsigned char*p1 = 0x801000;
unsigned int *p2 = 0x810000;
p1+=5;//p1 = 0x801000 + 5*1 = 0x801005;
p2+=5;//p2 = 0x810000 + 5*4 = 0x810014;

3.5 空指针、野指针和悬空指针

• 空指针
  空指针不会指向任何地方，它不是任何对象或函数的地址

int *p = NULL;
int *p2 = nullptr;

• 野指针
  指的是没有被初始化过的指针

int main(void) { 
int* p; // 未初始化
std::cout<< *p << std::endl; // 未初始化就被使用
return 0;
}

• 悬空指针
  最初指向的内存已经被释放了的一种指针

int main(void) { 
  int * p = nullptr;
  int* p2 = new int;
  p = p2;
  delete p2;
}

此时 p 和 p2 就是悬空指针，指向的内存已经被释放。继续使用这两个指针，行为不可预料

野指针和悬空指针的产生和解决

• 野指针：指针变量未及时初始化 => 定义指针变量及时初始化，要么置空。
• 悬空指针：指针 free 或 delete 之后没有及时置空 => 释放操作后立即置空。
  或使用智能指针（避免悬空指针产生）

3.6 指针函数和函数指针的区别

指针函数

• 返回值为指针类型的函数

#include<stdio.h>
int* fun(int* x)//传入指针  
{
	int* tmp = x;	  //指针tmp指向x
return tmp;   //返回tmp指向的地址
}
int main()
{
int b = 2;  
int* p = &b;   //p指向b的地址
printf("%d",*fun(p));//输出p指向的地址的值
return 0;
}

函数指针

• 函数指针是 指向函数的指针 。主体是指针，指向的是一个函数的地址
• 两种方法赋值：指针名 = 函数名； 指针名 = & 函数名

#include<stdio.h>
int add(int x,int y)
{
return x + y;
}
int main()
{
	int (*fun) (int,int);//声明函数指针
fun = &add;		//fun函数指针指向add函数
//fun = add;   //同上，等价fun = &add;
printf("%d ",fun(3,5));		
printf("%d",(*fun)(4,2));
return 0;
}

3.7 传递函数参数

什么时候使用指针，什么时候使用引用

• 需要返回函数内局部变量的内存的时候用指针。使用指针传参需要开辟内存，用完要记得释放指针，不然会内存泄漏。而返回局部变量的引用是没有意义的
• 对栈空间大小比较敏感（比如递归）的时候使用引用。使用引用传递不需要创建临时变量，开销要更小
• 类对象作为参数传递的时候使用引用，这是 C++ 类对象传递的标准方式

3.8 区别指针类型

int *p[10]
int (*p)[10]
int *p(int)
int (*p)(int)

• int * p[10] 表示指针数组，强调数组概念，是一个数组变量，数组大小为 10，数组内每个元素都是指向 int 类型的指针变量。
• int (* p)[10] 表示数组指针，强调是指针，只有一个变量，是指针类型，不过指向的是一个 int 类型的数组，这个数组大小是 10。
• int * p(int) 是函数声明，函数名是 p，参数是 int 类型的，返回值是 int * 类型的。
• int (* p)(int) 是函数指针，强调是指针，该指针指向的函数具有 int 类型参数，并且返回值是 int 类型的。

3.9 int a[10]; int (* p)[10] = &a 中 a 和 & a 有什么区别？

• a 是数组名，是数组首元素地址，+1 表示地址值加上一个 int 类型的大小，如果 a 的值是 0x00000001，加 1 操作后变为 0x00000005。*(a + 1) = a[1]。
• &a 是数组的指针，其类型为 int (* )[10]（就是前面提到的数组指针），其加 1 时，系统会认为是数组首地址加上整个数组的偏移（10 个 int 型变量），值为数组 a 尾元素后一个元素的地址。
• 若 (int * )p ，此时输出 * p 时，其值为 a[0] 的值，因为被转为 int * 类型，解引用时按照 int 类型大小来读取。

3.10 值传递、指针传递、引用传递的区别和效率

• 值传递：有一个形参向函数所属的栈拷贝数据的过程，如果值传递的对象是类对象 或是大的结构体对象，将耗费一定的时间和空间。（传值）
• 指针传递：同样有一个形参向函数所属的栈拷贝数据的过程，但拷贝的数据是一个固定为 4 字节的地址。（传值，传递的是地址值）
• 引用传递：同样有上述的数据拷贝过程，但其是针对地址的，相当于为该数据所在的地址起了一个别名。（传地址）
  效率上讲，指针传递和引用传递比值传递效率高。一般主张使用引用传递，代码逻辑上更加紧凑、清晰。

4 . 预处理

为编译做准备工作，处理 #开头的指令

4.1 ifndef/define/endif 的作用

防止头文件被重复包含和编译。头文件重复包含会增大程序大小，重复编译增加编译时间

4.2 #include<> 和 #include“” 的区别

• <> 和 " " 表示编译器在搜索头文件时的顺序不同，
• <> 表示从系统目录下开始搜索，然后再搜索 PATH 环境变量所列出的目录，不搜索当前目录，
• “” 是表示从当前目录开始搜索，然后是系统目录和 PATH 环境变量所列出的目录。
  所以，系统头文件一般用 <>，用户自己定义的则可以使用 “”，加快搜索速度。

4.3 #define 的缺点

#define 只能进行字符替换

• 无法类型检查
• 由于优先级的不同，会产生潜在问题

#define MAX_NUM 100+1
int a = MAX_NUM * 10;//a=110
//等价于
int a = 100 + 1 * 10;
//正确定义为
#define MAX_NUM （100+1）
int a = MAX_NUM * 10;//a=1010

• 无法单步调试
• 导致代码膨胀

4.4 写一个标准宏 MIN

#define MIN(A,B) ( (A)<=(B)?(A):(B) )

每个括号都是必须的，如果没有结果无法预测

4.5 #define 和 typdef 的区别

• define 主要用于定义常量及书写复杂的内容；typedef 主要用于定义类型别名。
• define 替换发生在编译阶段之前，属于文本插入替换；typedef 是编译的一部分。
• define 不检查类型；typedef 会检查数据类型。
• define 不是语句，不在在最后加分号；typedef 是语句，要加分号标识结束。
• 对指针的操作不同

#define INTPTR1 int*
typedef int* INTPTR2;
INTPTR1 p1, p2;//声明一个指针变量p1和一个整型变量p2
INTPTR2 p3, p4;//声明两个指针变量p3、p4

#define INTPTR1 int*
typedef int* INTPTR2;
int a = 1;
int b = 2;
int c = 3;
const INTPTR1 p1 = &a;//const INTPTR1 p1是一个常量指针
const INTPTR2 p2 = &b;//const INTPTR2 p2是一个指针常量
INTPTR2 const p3 = &c;//INTPTR2 const p3是一个指针常量

4.6 宏定义和内联函数的区别

• 宏定义是在预处理阶段进行代码替换，内联函数是编译阶段插入代码
• 宏定义没有类型检查，内敛函数有类型检查

内联函数和普通函数的区别

• 编译器将内联函数的位置进行函数展开，避免函数调用的开销，提高效率
• 普通函数被调用，跳跃到函数入口地址，执行结束后跳转回调用地方
• 内敛函数不需要寻址，执行 N 次内联函数，代码就复制 N 次
• 函数体过大，编译器放弃内联，变的和普通函数一样
• 内联函数不能递归，编译器无法预知深度，变成普通函数

4.7 #define 和 const 区别？

• #define 只能单纯文本替换，不分配周期，寸在代码段
• const 常量在程序数据段，分配内存
• #define 没有数据类型，const 有数据类型
• #define 没法调试，const 可以调试

5 . 结构体与类

5.1 struct 和 union 的区别

• 联合体所有成员共用一块内存，结构体成员占用空间累加
• 对联合体的不用成员赋值，对其他成员重写；结构体成员互相不影响

union
{
	int i;
	char x[2];
}
int main()
{
	a.x[0] = 10;
	a.x[1] = 1;
	printf("%d",a.i);//输出为266
}

其中 a.x[0]=10=00001010 ；a.x[1] = 1 = 00000001。
输出 i 的时候，将 a.x[0] a.x[1] 看作一个整数，为 00000001 00001010，为 256+8+2 = 266

5.2 C++ 中 struct 和 class 的区别

相同点

• 两者都拥有成员函数、公有和私有部分
• 任何可以使用 class 完成的工作，同样可以使用 struct 完成
  不同点
• 两者中如果不对成员不指定公私有，struct 默认是公有的，class 则默认是私有的
• class 默认是 private 继承， 而 struct 默认是 public 继承

5.3 C++ 和 C 的 struct 区别

• C 语言中：struct 是用户自定义数据类型（UDT）；C++ 中 struct 是抽象数据类型（ADT），支持成员函数的定义，（C++ 中的 struct 能继承，能实现多态）
• C 中 struct 是没有权限的设置的，且 struct 中只能是一些变量的集合体，可以封装数据却不可以隐藏数据，而且成员不可以是函数
• C++ 中，struct 增加了访问权限，且可以和类一样有成员函数，成员默认访问说明符为 public（为了与 C 兼容）
• struct 作为类的一种特例是用来自定义数据结构的。一个结构标记声明后，在 C 中必须在结构标记前加上 struct，才能做结构类型名（除：typedef struct class{};）;C++ 中结构体标记（结构体名）可以直接作为结构体类型名使用，此外结构体 struct 在 C++ 中被当作类的一种特例

6 . 位操作

6.1 最有效的计算 2 乘 8 的方法

int a = 2 ;
a = a<<3;//a乘上2的三次方

计算乘 7 倍

int a = 2 ;
a = （a<<3）-a;

6.2 位操作求两个数的平均值

int a = 2 .b =3;
int c ;
c = (a&b) + ((a^b)>>1);

• 对于表达式 (x&y)+(xy)>>1), x&y 表示的是取出 x 与 y 二进制位数中都为 1 的所有位, xy 表示的是 x 与 y 中有一个为 1’的所有位, 右移 1 位相当于执行除以 2 运算。
• 整个表达式实际上可以分为两部分, 第一部分是都为 1 的部分, 求平均数后这部分的值保持不变; 而第二部分是 x 为 1、y 为 0 的部分, 以及 y 为 1、x 为 0 的部分, 两部分加起来再除以 2, 然后跟前面的相加就可以表示两者的平均数了

6.3 什么是大端和小端，如何判断？

• 小端存储：字数据的低字节存储在低地址中（数据存储从低字节到高字节）
• 大端存储：字数据的高字节存储在低地址中（数据存储从高字节到低字节）
  例如：32bit 的数字 0x12345678
  

代码判断

• 方式一：使用强制类型转换 - 这种法子不错

#include <iostream>
using namespace std;
int main()
{
int a = 0x12345678;
//由于int和char的长度不同，借助int型转换成char型，只会留下低地址的部分
char c = (char)(a);
if (c == 0x12)
cout << "big endian" << endl;
else if(c == 0x78)
cout << "little endian" << endl;
}

• 方式二：巧用 union 联合体

#include <iostream>
using namespace std;
//union联合体的重叠式存储，endian联合体占用内存的空间为每个成员字节长度的最大值
union endian
{
int a;
char ch;
};
int main()
{
endian value;
value.a = 0x12345678;
//a和ch共用4字节的内存空间
if (value.ch == 0x12)
cout << "big endian"<<endl;
else if (value.ch == 0x78)
cout << "little endian"<<endl;
}

7 . 编译

7.1 main 函数执行前和执行后的代码

main 函数执行前（初始化系统相关资源）

• 设置栈指针
• 初始化静态 static 变量和 global 全局变量，即. data 段的内容
• 将未初始化部分的全局变量赋初值：数值型 short，int，long 等为 0，bool 为 FALSE，指针为 NULL 等等，即. bss 段的内容
• 全局对象初始化，在 main 之前调用全局对象的构造函数，这是可能会执行前的一些代码
• 将 main 函数的参数 argc，argv 等传递给 main 函数，然后才真正运行 main 函数
• __ attribute __((constructor))

main 函数执行后

• 全局对象的析构函数会在 main 函数之后执行；
• 可以用 atexit 注册一个函数，它会在 main 之后执行;
• __ attribute__((destructor))

8 . 面向对象

8.1 final 和 override 关键字

override

override 指定了子类的这个虚函数是重写的父类的，如果你名字不小心打错了的话，编译器是不会编译通过的。

class A
{
virtual void foo();
};
class B : public A
{
virtual void f00(); //OK，这个函数是B新增的，不是继承的
virtual void f0o() override; //Error, 加了override之后，这个函数一定是继承自A的，A找不到就报错
//virtual void foo() override; //ok，是继承父类的虚函数
};

final

不希望某个类被继承，或不希望某个虚函数被重写，可以在类名和虚函数后添加 final 关键字，添加 final 关键字后被继承或重写，编译器会报错。

class Base
{
virtual void foo();
};
 
class A : public Base
{
void foo() final; // foo 被override并且是最后一个override，在其子类中不可以重写
};
class B final : A // 指明B是不可以被继承的
{
void foo() override; // Error: 在A中已经被final了
};
 
class C : B // Error: B is final
{
};

8.2 拷贝初始化和直接初始化

当用于类类型对象时，初始化的拷贝形式和直接形式有所不同：

• 直接初始化直接调用与实参匹配的构造函数
• 拷贝初始化首先使用指定构造函数创建一个临时对象，然后用拷贝构造函数将那个临时对象拷贝到正在创建的对象。

//语句1 直接初始化
string str1("I am a string");
//语句2 直接初始化，str1是已经存在的对象，直接调用拷贝构造函数对str2进行初始化
string str2(str1);
//语句3 拷贝初始化，先为字符串”I am a string“创建临时对象，再把临时对象作为参数，使用拷贝构造函数构造str3
string str3 = "I am a string";
//语句4 拷贝初始化，这里相当于隐式调用拷贝构造函数，而不是调用赋值运算符函数
string str4 = str1;

• 为了提高效率，允许编译器跳过创建临时对象这一步，直接调用构造函数构造要创建的对象，这样就完全等价于直接初始化了（语句 1 和语句 3 等价），但是需要辨别两种情况。
• 当拷贝构造函数为 private 时：语句 3 和语句 4 在编译时会报错
• 使用 explicit 修饰构造函数时：如果构造函数存在隐式转换，编译时会报错

8.3 C 和 C++ 的类型安全

类型安全很大程度上可以等价于内存安全，类型安全的代码不会试图访问自己没被授权的内存区域。有的时候也用 “类型安全” 形容某个程序，判别的标准在于该程序是否隐含类型错误。

• 想保证程序的类型安全性，
• 应尽量避免使用空类型指针 void*，
• 尽量不对两种类型指针做强制转换。

8.4 C++ 中的重载、重写（覆盖）和隐藏的区别

重载（overload）

重载是指在同一范围定义中的同名成员函数才存在重载关系。主要特点是函数名相同，参数类型和数目有所不同，不能出现参数个数和类型均相同，仅仅依靠返回值不同来区分的函数。重载和函数成员是否是虚函数无关。

class A{
...
virtual int fun();
void fun(int);
void fun(double, double);
static int fun(char);
...
}

重写（覆盖）（override）

重写指的是在派生类中覆盖基类中的同名函数，重写就是重写函数体，要求基类函数必须是虚函数且：

• 与基类的虚函数有相同的参数个数
• 与基类的虚函数有相同的参数类型
• 与基类的虚函数有相同的返回值类型

//父类
class A{
public:
virtual int fun(int a){}
}
//子类
class B : public A{
public:
//重写,一般加override可以确保是重写父类的函数
virtual int fun(int a) override{}
}

重载与重写的区别：

• 重写是父类和子类之间的垂直关系，重载是不同函数之间的水平关系
• 重写要求参数列表相同，重载则要求参数列表不同，返回值不要求

隐藏（hide）

隐藏指的是某些情况下，派生类中的函数屏蔽了基类中的同名函数，包括以下情况：

• 两个函数参数相同，但是基类函数不是虚函数。和重写的区别在于基类函数是否是虚函数。

//父类
class A{
public:
void fun(int a){
		cout << "A中的fun函数" << endl;
	}
};
//子类
class B : public A{
public:
//隐藏父类的fun函数
void fun(int a){
		cout << "B中的fun函数" << endl;
	}
};
int main(){
B b;
b.fun(2); //调用的是B中的fun函数
b.A::fun(2); //调用A中fun函数
return 0;
}

• 两个函数参数不同，无论基类函数是不是虚函数，都会被隐藏。和重载的区别在于两个函数不在同一个类中。

//父类
class A{
public:
virtual void fun(int a){
		cout << "A中的fun函数" << endl;
	}
};
//子类
class B : public A{
public:
//隐藏父类的fun函数
   virtual void fun(char* a){
	   cout << "A中的fun函数" << endl;
   }
};
int main(){
B b;
b.fun(2); //报错，调用的是B中的fun函数，参数类型不对
b.A::fun(2); //调用A中fun函数
return 0;
}

• 基类指针指向派生类对象时，基类指针可以直接调用到派生类的覆盖（重写）函数，也可以通过 :: 调用到基类被覆盖
  的虚函数；
• 而基类指针只能调用基类的被隐藏函数，无法识别派生类中的隐藏函数。

// 父类
class A {
public:
virtual void fun(int a) { // 虚函数
cout << "This is A fun " << a << endl;
}  
void add(int a, int b) {
cout << "This is A add " << a + b << endl;
}
};
// 子类
class B: public A {
public:
void fun(int a) override {  // 覆盖（重写）
cout << "this is B fun " << a << endl;
}
void add(int a) {   // 隐藏
cout << "This is B add " << a + a << endl;
}
};
int main() {
A *p = new B();
p->fun(1);  // 调用子类 fun 覆盖函数
p->A::fun(1);   // 调用父类 fun
p->add(1, 2);
// p->add(1);  // 错误，识别的是 A 类中的 add 函数，参数不匹配
// p->B::add(1);   // 错误，无法识别子类 add 函数
return 0;
}

8.5 浅拷贝和深拷贝的区别

浅拷贝
浅拷贝只是拷贝一个指针，并没有新开辟一个地址，拷贝的指针和原来的指针指向同一块地址，如果原来的指针所指向的资源释放了，那么再释放浅拷贝的指针的资源就会出现错误。
深拷贝
深拷贝不仅拷贝值，还开辟出一块新的空间用来存放新的值，即使原先的对象被析构掉，释放内存了也不会影响到深拷贝得到的值。在自己实现拷贝赋值的时候，如果有指针变量的话是需要自己实现深拷贝的。

8.6 public，protected 和 private 访问和继承权限

访问权限

public、protected、private 的访问权限范围关系：public > protected > private

继承权限

1. public 继承
   公有继承的特点是，基类的公有和保护，变派生类的公有和保护，基类私有不可访问
2. protected 继承
   保护继承的特点是，基类的公有和保护，变派生类的保护，基类私有派生类不可访问
3. private 继承
   私有继承的特点是，基类的公有和保护，变派生类的私有，基类私有派生类不可访问
   

C_C++ 中 STL

一、STL：标准模板库

C++ STL 从广义来讲包括了三类：算法，容器和迭代器。
算法包括排序，复制等常用算法，以及不同容器特定的算法。
容器就是数据的存放形式，包括序列式容器和关联式容器，序列式容器就是 list，vector 等，关联式容器就是 set，map 等。
迭代器就是在不暴露容器内部结构的情况下对容器的遍历。
迭代器是 STL 的精髓，它提供了一种方法，使它能够按照顺序访问某个容器所含的各个元素，但无需暴露该容器的内部结构。它将容器和算法分开，好让这二者独立设计。
容器，即存放数据的地方。比如 array 等。
在 STL 中，容器分为两类：序列式容器和关联式容器。
序列式容器，其中的元素不一定有序，但都可以被排序。如：vector、list、deque、stack、queue、heap、priority_queue。
关联式容器，内部结构基本上是一颗平衡二叉树。所谓关联，元素按照一定的规则存放（元素位置取决于特定的排序准则）。如：RB-tree、set、map、multiset、multimap、hashtable、hash_set、hash_map、hash_multiset、hash_multimap。
下面各选取一个作为说明。
vector：它是一个动态分配存储空间的容器。区别于 c++ 中的 array，array 分配的空间是静态的，分配之后不能被改变，而 vector 会自动重配（扩展）空间。
使用 vector 时需要注意：每次插入和移除元素的时候，都会使作用点之后的各元素 references、pointers、iterators 失效，如果插入操作引发内存重新分配，那么该容器上所有的 references、pointers、iterators 都会失效。
set：其内部元素会根据元素的键值自动被排序。区别于 map，它的键值就是实值，而 map 可以同时拥有不同的键值和实值。
算法，如排序，复制…… 以及一些容器特定的算法。这点不用过多介绍，主要看下迭代器的内容。

二、 迭代器

2.1 迭代器的种类

输入迭代器：是只读迭代器，在每个被遍历的位置上只能读取一次。例如 find 函数参数就是输入迭代器。
输出迭代器：是只写迭代器，在每个被遍历的位置上只能被写一次。
前向迭代器：兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。但它不支持 operator–，所以只能向前移动。
双向迭代器：很像前向迭代器，只是它向后移动和向前移动同样容易。
随机访问迭代器：有双向迭代器的所有功能。而且，它还提供了 “迭代器算术”，即在一步内可以向前或向后跳跃任意位置， 包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种 Iterator 的所有操作，并另外支持 it + n、it – n、it += n、 it -= n、it1 – it2 和 it[n] 等操作。

2.2 迭代器失效的问题

插入操作
对于 vector 和 string，如果容器内存被重新分配，iterators,pointers,references 失效；如果没有重新分配，那么插入点之前的 iterator 有效，插入点之后的 iterator 失效；
对于 deque，如果插入点位于除 front 和 back 的其它位置，iterators,pointers,references 失效；当我们插入元素到 front 和 back 时，deque 的迭代器失效，但 reference 和 pointers 有效；
对于 list 和 forward_list，所有的 iterator,pointer 和 refercnce 有效。
删除操作
对于 vector 和 string，删除点之前的 iterators,pointers,references 有效；off-the-end 迭代器总是失效的；
对于 deque，如果删除点位于除 front 和 back 的其它位置，iterators,pointers,references 失效；当我们插入元素到 front 和 back 时，off-the-end 失效，其他的 iterators,pointers,references 有效；
对于 list 和 forward_list，所有的 iterator,pointer 和 refercnce 有效。
对于关联容器 map 来说，如果某一个元素已经被删除，那么其对应的迭代器就失效了，不应该再被使用，否则会导致程序无定义的行为。
vector 动态增加大小时，并不是在原空间后增加新的空间，而是以原大小的两倍在另外配置一片较大的新空间，然后将内容拷贝过来，并释放原来的空间。由于操作改变了空间，所以迭代器失效。

三、vector

3.1 vector 扩容原理

空间分配的多，平摊时间复杂度低，但浪费空间也多。
使用 k = 2 增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和。也就是说，之前分配的内存空间不可能被使用。这样对于缓存并不友好。最好把增长因子设为 1 < k < 2，例如 k = 1.5 这样，在几次扩容后，就可以重用之前的内存空间。
其实 C++ 标准也没有规定要用哪一个增长因子， VS2015 中以 1.5 倍扩容，GCC 以 2 倍扩容。
总结:
1 . vector 在 push_back 以成倍增长可以在均摊后达到 O(1) 的时间复杂度，相对于增长指定大小的 O(n) 时间复杂度更好。
2 . 为了防止申请内存的浪费，现在使用较多的有 2 倍与 1.5 倍的增长方式，而 1.5 倍的增长方式可以更好的实现对内存的重复利用，因为更好。

3.2 vector 如何释放空间

由于 vector 的内存占用空间只增不减，比如你首先分配了 10,000 个字节，然后 erase 掉后面 9,999 个，留下一个有效元素，但是内存占用仍为 10,000 个。所有内存空间是在 vector 析构时候才能被系统回收。
empty() 用来检测容器是否为空的，clear() 可以清空所有元素。但是即使 clear()，vector 所占用的内存空间依然如故，无法保证内存的回收。
如果需要空间动态缩小，可以考虑使用 deque。如果 vector，可以用 swap() 来帮助你释放内存。

template <class T>
void ClearVector(vector<T>& vt) 
{
vector<TvtTemp;  // 空的vector
veTemp.swap(vt); // 将vt 与 空的vector vtTemp交换，就析构了 vt
}

3.3 vector 与 list 区别

vector 与 array 一样，拥有一段连续的内存空间，支持随机存取。因为内存空间连续，所以在中间插入和删除会造成内存块的拷贝（时间复杂度 O(n)）。另外，当连续的内存空间不足后，需要重新申请一块大内存，然后将之前的数据拷贝过去，这些都影响了 vector 的效率。
list 由双向链表实现，内存空间不连续。很好的支持删除与插入操作，但随机访问需要 O(n) 时间复杂度。
vector::iterator 支持 “+”，“+=”，“<”，“[]”，等等操作，list::iterator 不支持这些操作。list 只能用“++” 进行迭代。
对于 vector 来说，如果有大量的数据需要 push_back，应该先用 reserve() 方法设定其大小，否则会出现多次容量扩充操作，影响效率。

3.4 vector 与 deque

vector 是单向开口的连续线性空间， deque，由多个连续内存块构成，是一种双向开口的连续线性空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。deque 是 list 和 vector 的兼容，分为多个块，每一个块大小是 512 字节，块通过 map 块管理，map 块里保存每个块得首地址。因此该容器也有索引操作 operator[]，效率没 vector 高。另外，deque 比 vector 多了 push_front() 和 pop_front() 两个方法（vector 不支持），这两个方法都是对首部操作的，在两端进行此操作时与 list 的效率 差不多。
deque 没有所谓容量 (capacity) 观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。

四、 选择顺序容器的一些准则

如果我们需要随机访问一个容器则 vector 要比 list 好得多 。
如果我们已知要存储元素的个数则 vector 又是一个比 list 好的选择。
如果我们需要的不只是在容器两端插入和删除元素则 list 显然要比 vector 好
除非我们需要在容器首部插入和删除元素否则 vector 要比 deque 好。
如果只在容易的首部和尾部插入数据元素，则选择 deque.
如果只需要在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑输入时将元素读入到一个 list 容器，接着对此容器重新排序，使其适合顺序访问，然后将排序后的 list 容器复制到一个 vector 容器中。

五、 map 与 hash_map

底层数据结构不同：map 是红黑树（查找时间复杂度 log(n)），hash_map 是哈希表（查找时间复杂度 O(1)）
map 的优点在于元素可以自动按照键值排序，而 hash map 的优点在于它的各项操作的平均时间复杂度接近常数
map 属于标准的一部分，而 hash_map 则不是
5.1 什么时候用 map，什么时候用 hash_map？
这个要看具体的应用，不一定常数级别的 hash_map 一定比 log(n) 级别的 map 要好， hash_map 的 hash 函数以及解决地址冲突等都要耗时间，构造很慢。
众所周知 hash 表是以空间换时间的，因而 hash_map 的内存消耗肯定要大，一般情况下，如果记录非常大，考虑 hash_map，查找效率会高很多，如果要考虑内存消耗，则要谨慎使用 hash_map。
扩展:
map, set, multimap, and multiset 采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:
插入: O(logN)
查看: O(logN)
删除: O(logN)
hash_map, hash_set, hash_multimap, and hash_multiset 采用哈希表实现，不同操作的时间复杂度为：
插入: O(1)，最坏情况 O(N)。
查看: O(1)，最坏情况 O(N)。
删除: O(1)，最坏情况 O(N)。
5.1 红黑树
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质 1. 节点是红色或黑色。
性质 2. 根节点是黑色。
性质 3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质 4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果?
注意到性质 3 导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质 4 所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
5.2 map 底层为什么用红黑树而不是平衡二叉树（AVL）
AVL 是有下列性质的二叉树：
1 . 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。
2 . 将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF，那么平衡二叉树上的所有结点的平衡因子只可能是 -1、0 和 1。只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。
3 . 红黑树是在 AVL 树的基础上提出来的。
红黑树较 AVL 树的优点：
1 . AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的 rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
2 . 红黑树的查询性能略微逊色于 AVL 树，因为他比 avl 树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的 avl 树最多多一次比较，但是，红黑树在插入和删除上完爆 avl 树， avl 树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于 avl 树为了维持平衡的 开销要小得多
3 . 所以红黑树在查找，插入删除的性能都是 O(logn)，且性能稳定，所以 STL 里面很多结构包括 map 底层实现都是使用的红黑树。
5.3 STL 关联容器底层实现总结
有序关联容器底层实现为红黑树，增删改查时间复杂度 O(logn)。
set，multiset，map，multimap。
无序关联容器底层实现链式哈希表 ，增删改查时间复杂度 O(1)。
unordered_set，unordered_multiset，unordered_map，unordered_multimap。
5.4 map 和 unordered_map 的性能对比
map 内部是红黑树，在插入元素时会自动排序，而无序容器 unordered_map 内部是哈希表，通过哈希而不是排序来快速操作元素，使得效率更高。当你不需要排序时选择 unordered_map 的效率更高。
5.5 为何 map 和 set 的插入删除效率比其它序列容器高，而且每次 insert 之后，以前保存的 iterator 不会失效？
因为存储的是结点，不需要内存拷贝和内存移动。
因为插入操作只是结点指针换来换去，结点内存没有改变。而 iterator 就像指向结点的指针，内存没变，指向内存的指针也不会变。
5.5 为何 map 和 set 不能像 vector 一样有个 reserve 函数来预分配数据?
因为在 map 和 set 内部存储的已经不是元素本身了，而是包含元素的结点。也就是说 map 内部使用的 Alloc 并不是 map<Key, Data, Compare, Alloc声明的时候从参数中传入的 Alloc。

六、 容器内部删除一个元素

顺序容器（序列式容器，比如 vector、deque）
erase 迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效 (list 除外)，所以不能使用 erase(it++) 的方式，但是 erase 的返回值是下一个有效迭代器；

it = c.erase(it);

关联容器 (关联式容器，比如 map、set、multimap、multiset 等)
erase 迭代器只是被删除元素的迭代器失效，但是返回值是 void，所以要采用 erase(it++) 的方式删除迭代器；

c.erase(it++)

vector erase 成员函数，它删除了 itVect 迭代器指向的元素，并且返回要被删除的 itVect 之后的迭代器，迭代器相当于一个智能指针;
clear() 函数，只能清空内容，不能改变容量大小;
如果要想在删除内容的同时释放内存，那么你可以选择 deque 容器。

七、 remove 和 erase 区别

erase 一般作为一个 container 的成员函数，是真正删除的元素，是物理上的删除（迭代器访问不到了）
algorithm 中的 remove 只是简单的把要 remove 的元素移到了最后面，后面的一系列元素前移，覆盖掉要 remove 的元素，是逻辑上的删除，此时容器的 size 不变化。因为 algorithm 通过迭代器操作，不知道容器的内部结构，所以无法做到真正删除。

template <class T>
void show(std::vector<T&v)
{
for (const auto &x : v)
{
std::cout << x << " ";
}
std::cout << std::endl;
}
int main()
{
std::vector<intvec{1, 2, 3, 3, 4, 5, 5};
vec.erase(vec.begin());
show(vec);
auto pos = remove(vec.begin(), vec.end(), 4);
show(vec);
if (pos + 1 == vec.end())
{
std::cout << "move element to the end" << std::endl;
}
remove(vec.begin(), vec.end(), 3);
show(vec);
return 0;
}
/**
2 3 3 4 5 5 
2 3 3 5 5 5 
move element to the end
2 5 5 5 5 5 
* /

八、 所有容器的共同操作 (包括 string 类)

== 和 != 返回 true 或者 false，两个容器是否相等
= 赋值，将一个容器赋给另一个容器
size() 返回当前的容器的元素数量
empty() 判断容器是否为空，这个操作比 size() == 0 更有利率
max_size() 容器所能容纳的最大元素数量
clear() 删除所有元素
begin() ，rbegin()
end(), rend()
insert(it, val) 将单一或者某一个范围的元素插入容器内
erase() 将容器内的单一或者某一个范围内的元素删除
swap()

8.1 顺序容器

可序群集，每个元素位置取决于插入时机和地点，和元素值无关。如果以追加方式置入元素，那么他们的排列次序将和置入次序一致。
array：数组
vector: 以一块连续性内存来存放数据，适合随机访问，不适合插入 / 删除（在末尾插入 / 删除效率很高，在中间插入 / 删除就需要移动元素，不提供在首部插入的操作，因为效率低）
list: 以双向链接而非连续内存来存储内容，适合插入 / 删除而不适合随机访问。
forward_list：单链表
deque: (双向队列) 以连续内存存储数据，但是只能对最前端 / 末端的元素进行插入 / 删除操作

8.2 容器适配器：

stack: 栈
queue: 队列
priority queue: 优先队列

vector
vector vec; 产生空的容器
vector vec(1024): 创建一个 vector, 元素个数为 1024，对 int 和 double 这种算术类型，不给初值，默认就是 0.
vector vec(1024, 42): 创建一个 vector，元素个数为 1024, 且值均为 42
vector vec(begin,end): 复制 [begin,end) 区间内另一个数组的元素到 vector 中，begin 和 end 为指针或者迭代器
vector vec = {1, 2, 3, 4, 5}; // 像数组一样初始化，甚至可以去掉等于号。
vec.push_back()
vec.pop_back()
vec.insert(it, val)
size() 返回当前的容器的元素数量
empty() 判断容器是否为空，这个操作比 size() == 0 更有利率
max_size() 容器所能容纳的最大元素数量
capacity() 重新分配空间前所能容纳的元素最大数量，看 reserve 预留多少
reserve() 预留多少个元素

int main(int argc, char* argv[]) {
	vector<stringsen;
	sen.reserve(100);// 预留 100 个string空间，如果不预留，那么 capacity() 的输出就和 size() 一样
	vector<string>::iterator it = sen.begin();
	sen.push_back("hello");
	sen.push_back("world");
	sen.push_back("!");
	sen.insert(it, "ok");
	cout << sen.size() << endl;;		// 4
	cout << sen.max_size() << endl;		// 153391689
	cout << sen.capacity() << endl;		// 100
	it = sen.begin();	// 注意，insert() 会使插入的位置之后的所有 iterator 失效，故重新赋值
	vector<string>::iterator finish = sen.end();
	for (; it != finish; ++it)			// ok hello world !
		cout << *it << " ";				
	getchar();
}

vector<vector<char>vec(row, vector<char>(col,'#'));//二维数组初始化

list
insert(pos, elem)
push_back(elem)
pop_back()
push_front()
pop_front()
remove(val) 移除所有值为 val 的元素
remove_if(op) 移除所有造成 op(elem) 结果为 true 的元素
erase(pos)
erase(beg, end)
clear()
deque
与 vector 接口几乎一样，deque 适合在两端操作，vector 没有在首部插入 / 删除的方法。要注意，在中间插入元素会导致 references、pointers、iterators 失效（两端没关系）
queue
bool empty() const
size_type size() const
T& front() 返回指向队首元素的引用
T& back() 返回指向队尾元素的引用
void push(const T& x) 在队尾插入 x
void pop() 删除队首元素
stack
bool empty() const
size_type size() const
T& top() 返回指向栈顶元素的引用
void push(const T& x) 在栈顶插入 x
void pop() 删除栈顶元素

8.3 关联容器

已序群集，元素位置取决于特定的排序准则，如果置入元素，那么它们的位置取决于元素值，而与置入的次序无关。
自动排序造成一个重要限制：你不能直接改变元素值（只读），因为这样会打乱原本正确的顺序。因此，要改变元素值，必须先删除旧元素，再插入新元素。
set: 内部元素有序，且只出现一次
multiset: 与 set 相同，但允许重复的元素
unordered_set：无序 set，用哈希函数组织
unordered_multiset：关键字可重复的无序 set
map: 键值对，每个键只出现一次
multimap: 与 map 相同，
unordered_map：无序 map
unordered_multimap：关键字可重复的无序 map
set
Set 由一群 key 组合而成，对于任何 key 值，set 只能存一份。
C++ 中，set 元素默认按照 less-than 顺序排列，这点跟 python 不一样，python 里的 set 是无序的。

int ia[] = {3, 8, 8, 5, 3, 1, 5, 1};
vector<intvec(ia, ia+8);
set<intiset(vec.begin(), vec.end());
set<int>::iterator it = iset.begin();
for (; it != iset.end(); ++it)
cout << *it << ' ';
//输出 1 3 5 8

insert() 插入元素
set_intersection()
set_union()
set_difference()
set_symmetric_difference()
multiset
map

#include<iostream>
#include <map>
#include <string>
map<string, intwords;
words["good"] = 1;  //键 good 的值是 1
//如果一个key不在words钟，其默认值就为0
words["bad"];  // 0
//比如你想知道 words 中是否有 "python",第一种方法可以直接把 key当索引使用，
//但缺点是，若本无这个键，这样做就会添加这个键，虽然默认值为 0
if (words["python"]) {
do something;  //如果 words 中有 "python"
}
//第二种做法是用map自带的find()函数。
map<string, int>::iterator it;
it = words.find("Python");
if (it != words.end() {
do something;
std::cout << it->second;
//it->first 是 key，it->second 是 value
}
//第三种做法是利用map的count()函数
if (words.count("python")) {
do something;
}

multimap
unordered_map
unordered_multimap

8.4 算法

sort

#include <algorithm>
/* 函数sort(first, last, comp)；
first : 待排序数组起始地址；
last : 待排序数组结束地址；
comp : 排序方式，该参数是可省参数，如果省略则以升序方式排序；
*/
int vec[] = { 5, 1, 9, 4, 6, 7, 2, 0, 1 };
sort(vec, vec + 9); //就地改变，未使用 comp，默认按升序排列 

 bool comp(int a, int b) {
 return a b;  //自己写排序规则，大的放在前面
 }
int vec[] = { 5, 1, 9, 4, 6, 7, 2, 0, 1 };
sort(vec, vec + 9, comp); //使用 comp，按自己的规则降序排列

reserve
find
for_each