C++面试准备

C++

C 数据类型/取值范围/精度

计算机的所有指令和数据都保存在计算机的存储部件——内存里，内存保存数据速度快，数据可被随机访问，但掉电即失。内存中的存储单元是一个线性的地址表，是按 字节(Byte) 进行编址的，即每个字节的存储单元都对应着一个唯一的地址。在程序设计语言中，通常用字节数来衡量变量或数据类型所占内存空间的大小。

1个字节等于8个二进制位，也称作比特，1 Byte = 8 bit，即可表示的整数范围为0 ～ 255，0 ～ )，bit 是 binary digit 二进制数的缩写。位是衡量物理存储器容量的最小单位。

1KB = 1024byte = 2的10次方 byte，转化为16进制为0x400。同时换一种说法，1KB可以表示1024个地址，0x400个地址，而且表示地址的范围是0x00~0x3FF。（记住）

2KB = 2的11次方byte, 转化为16进制为0x800，表示的地址范围为0x00~7FF。其中0x400~0x7FF表示的是第二KB的范围。

4KB = 2的12次方byte，0x1000，表示的地址范围0x000~0xFFF。（特殊要记住）

1MB = 1024KB = 2的20次方byte，0x100000。表示的地址范围为0x00000~0xFFFFF。（特殊要记住）

1GB= 2的30次方byte，0x40000000。表示的地址范围为0x00000~0x3FFFFFFF。

那么对于一个任意给定的地址范围（必然是1KB的整数倍）怎么反推字节数呢？
例如,0x000000~0x1FFFFF。
第一种解法，记住1M是5个F，多一位是2倍，所以是2M。
第二种解法,记住FFF是4KB，1FF是512, 512X4KB=2048KB也就是2M
20180621： 0x3000 表示地址0x0000-0x2FFF  12K

Type	Storage size	Value range	Precision
char	1 Byte	-128 to 127 or 0 to 255
unsigned char	1 Byte	0 to 255
signed char	1 Byte	-128 to 127
int	4 Bytes	-2,147,483,648 to 2,147,483,647
unsigned int	4 Bytes	0 to 4,294,967,295
short	2 Bytes	-32,768 to 32,767
unsigned short	2 Bytes	0 to 65,535
long	4 Bytes	-2,147,483,648 to 2,147,483,647
unsigned long	4 Bytes	0 to 4,294,967,295
float	4 Bytes	1.2E-38 to 3.4E+38	6 decimal places
double	8 Bytes	2.3E-308 to 1.7E+308	15 decimal places
long double	10	3.4E-4932 to 1.1E+4932	19 decimal places

char

char 占 1 个字节 Byte，即 8 个bit。能表示的范围在 [$0$ ～ $2^8-1$]，即 0 ～ 255，

int

默认的int为有符号整型，占 4 个字节 Byte，即 4x8=32 个bit。能表示的整数范围在 [$-2^{31}$ ～ $2^{31}-1$]，即 -2,147,483,648 ～ 2,147,483,647

unsigned int

无符号整型，占 4 个字节，32位，能表示整数范围在 [$0$ ～ $2^{32}-1$]，即 0 ～ 4,294,967,295

float 和 double

通常，浮点数是将实数分为阶码和尾数两部分来表示。例如，实数 $N$ 可以表示为：
\[ N = S * r^j \]

$S$ 为尾数(正负均可)，一般规定用纯小数形式：实数的小数部分
$j$ 为阶码(正负均可，但必须是整数)：实数的指数部分
$r$ 是基数，对于二进制而言 $r = 2$ ，即 $N = S * 2^j$ 。例如：10.0111 = 0.100111 x $2^{10}$

浮点数再计算机中的存储格式如下图：

阶码所占的位数决定实数的表示范围；尾数所占的位数决定实数的精度，尾数的符号决定实数的正负。

取值范围

float 和 double 的范围是由指数的位数来决定的。float的指数位有8位，而double的指数位有11位，分布如下：

float: 1bit（符号位）+ 8bits （指数位）+ 23bits（尾数位）
double: 1bit（符号位）+ 11bits（指数位）+ 52bits（尾数位）

于是，float 的指数范围为 -127~128，而 double 的指数范围为 -1023~1024，并且指数位是按补码的形式来划分的。其中负指数决定了浮点数所能表达的绝对值最小的数；而正指数决定了浮点数所能表达的绝对值最大的数，也即决定了浮点数的取值范围。

float的范围为: $-2^{128}$ ～ $+2^{128}$ ，即 -3.40E+38 ~ +3.40E+38
double的范围为: $-2^{1024}$ ～ $+2^{1024}$，即-1.79E+308 ~ +1.79E+308

精度

float 和 double 的精度是由尾数的位数来决定的。浮点数在内存中是按科学计数法来存储的，其整数部分始终是一个隐含着的“1”，由于它是不变的，故不能对精度造成影响。

float：$2^{23}$ = 8388608，共七位，意味着最多能有7位有效数字，但绝对能保证的为6位，也即float的精度为6~7位有效数字
double：$2^{52}$ = 4503599627370496，一共16位，同理，double的精度为15~16位。

C++中的基本数据类型及派生类型

1）整型 int

2）浮点型单精度float，双精度double

3）字符型 char

4）逻辑型 bool

5）控制型 void

基本类型的字长及其取值范围可以放大和缩小，改变后的类型就叫做基本类型的派生类型。派生类型声明符由基本类型关键字char、int、float、double前面加上类型修饰符组成。

类型修饰符包括：

>short 短类型，缩短字长

>long 长类型，加长字长

>signed 有符号类型，取值范围包括正负值

>unsigned 无符号类型，取值范围只包括正值

typdef 和 define区别

#define是预处理命令，在预处理是执行简单的替换，不做正确性的检查

typedef是在编译时处理的，它是在自己的作用域内给已经存在的类型一个别名

typedef (int*) pINT;

#define pINT2 int*

效果相同？实则不同！实践中见差别：pINT a,b;的效果同int a; int b;表示定义了两个整型指针变量。而pINT2 a,b;的效果同int *a, b;表示定义了一个整型指针变量a和整型变量b。

define 和 const 的区别

#define定义的常量没有类型，所给出的是一个立即数；const定义的常量有类型名字，存放在静态区域
处理阶段不同，#define定义的宏变量在预处理时进行替换，可能有多个拷贝，const所定义的变量在编译时确定其值，只有一个拷贝。
#define定义的常量是不可以用指针去指向，const定义的常量可以用指针去指向该常量的地址
#define可以定义简单的函数，const不可以定义函数

const 作用

修饰变量，说明该变量不可以被改变
修饰指针，分为指向常量的指针和指针常量
常量引用，经常用于形参类型，即避免了拷贝，又避免了函数对值的修改
修饰成员函数，说明该成员函数内不能修改成员变量

// 类
class A
{
private:
    const int a;                // 常对象成员，只能在初始化列表赋值

public:
    // 构造函数
    A() : a(0) { };
    A(int x) : a(x) { };        // 初始化列表

    // const可用于对重载函数的区分
    int getValue();             // 普通成员函数
    int getValue() const;       // 常成员函数，不得修改类中的任何数据成员的值
};

void function()
{
    // 对象
    A b;                        // 普通对象，可以调用全部成员函数、更新常成员变量
    const A a;                  // 常对象，只能调用常成员函数
    const A *p = &a;            // 常指针
    const A &q = a;             // 常引用

    // 指针
    char greeting[] = "Hello";
    char* p1 = greeting;                // 指针变量，指向字符数组变量
    const char* p2 = greeting;          // 指针变量，指向字符数组常量
    char* const p3 = greeting;          // 常指针，指向字符数组变量
    const char* const p4 = greeting;    // 常指针，指向字符数组常量
}

// 函数
void function1(const int Var);           // 传递过来的参数在函数内不可变
void function2(const char* Var);         // 参数指针所指内容为常量
void function3(char* const Var);         // 参数指针为常指针
void function4(const int& Var);          // 引用参数在函数内为常量

// 函数返回值
const int function5();      // 返回一个常数
const int* function6();     // 返回一个指向常量的指针变量，使用：const int *p = function6();
int* const function7();     // 返回一个指向变量的常指针，使用：int* const p = function7();

static

函数体内： static 修饰的局部变量作用范围为该函数体，不同于auto变量，其内存只被分配一次，因此其值在下次调用的时候维持了上次的值
模块内：static修饰全局变量或全局函数，可以被模块内的所有函数访问，但是不能被模块外的其他函数访问，使用范围限制在声明它的模块内
类中：修饰成员变量，表示该变量属于整个类所有，对类的所有对象只有一份拷贝
类中：修饰成员函数，表示该函数属于整个类所有，不接受this指针，只能访问类中的static成员变量

注意和const的区别！！！const强调值不能被修改，而static强调唯一的拷贝，对所有类的对象

this 指针

this 指针是一个隐含于每一个非静态成员函数中的特殊指针。它指向调用该成员函数的那个对象。
当对一个对象调用成员函数时，编译程序先将对象的地址赋给 this 指针，然后调用成员函数，每次成员函数存取数据成员时，都隐式使用 this 指针。
当一个成员函数被调用时，自动向它传递一个隐含的参数，该参数是一个指向这个成员函数所在的对象的指针。
this 指针被隐含地声明为: ClassName *const this，这意味着不能给 this 指针赋值；在 ClassName 类的 const成员函数中，this 指针的类型为：const ClassName* const，这说明不能对 this 指针所指向的这种对象是不可修改的（即不能对这种对象的数据成员进行赋值操作）；
this 并不是一个常规变量，而是个右值，所以不能取得 this 的地址（不能 &this）。
在以下场景中，经常需要显式引用this指针：

为实现对象的链式引用；
为避免对同一对象进行赋值操作；
在实现一些数据结构时，如 list。

inline 内联函数

相当于把内联函数里面的内容写在调用内联函数处；
相当于不用执行进入函数的步骤，直接执行函数体；
相当于宏，却比宏多了类型检查，真正具有函数特性；
编译器一般不内联包含循环、递归、switch 等复杂操作的内联函数；
在类声明中定义的函数，除了虚函数的其他函数都会自动隐式地当成内联函数。

// 声明1（加 inline，建议使用）
inline int functionName(int first, int second,...);

// 声明2（不加 inline）
int functionName(int first, int second,...);

// 定义
inline int functionName(int first, int second,...) {/****/};

// 类内定义，隐式内联
class A {
    int doA() { return 0; }         // 隐式内联
}

// 类外定义，需要显式内联
class A {
    int doA();
}
inline int A::doA() { return 0; }   // 需要显式内联

编译器对 inline 函数的处理步骤

将 inline 函数体复制到 inline 函数调用点处；
为所用 inline 函数中的局部变量分配内存空间；
将 inline 函数的的输入参数和返回值映射到调用方法的局部变量空间中；
如果 inline 函数有多个返回点，将其转变为 inline 函数代码块末尾的分支（使用 GOTO）。

优缺点

1. 优点

内联函数同宏函数一样将在被调用处进行代码展开，省去了参数压栈、栈帧开辟与回收，结果返回等，从而提高程序运行速度。
内联函数相比宏函数来说，在代码展开时，会做安全检查或自动类型转换（同普通函数），而宏定义则不会。
在类中声明同时定义的成员函数，自动转化为内联函数，因此内联函数可以访问类的成员变量，宏定义则不能。
内联函数在运行时可调试，而宏定义不可以。

2. 缺点

代码膨胀。内联是以代码膨胀（复制）为代价，消除函数调用带来的开销。如果执行函数体内代码的时间，相比于函数调用的开销较大，那么效率的收获会很少。另一方面，每一处内联函数的调用都要复制代码，将使程序的总代码量增大，消耗更多的内存空间。
inline 函数无法随着函数库升级而升级。inline函数的改变需要重新编译，不像 non-inline 可以直接链接。
是否内联，程序员不可控。内联函数只是对编译器的建议，是否对函数内联，决定权在于编译器。

虚函数（virtual）可以是内联函数（inline）吗？

虚函数可以是内联函数，内联是可以修饰虚函数的，但是当虚函数表现多态性的时候不能内联。
内联是在编译器建议编译器内联，而虚函数的多态性在运行期，编译器无法知道运行期调用哪个代码，因此虚函数表现为多态性时（运行期）不可以内联。
inline virtual 唯一可以内联的时候是：编译器知道所调用的对象是哪个类（如 Base::who()），这只有在编译器具有实际对象而不是对象的指针或引用时才会发生。

volatile

1	volatile int i = 10;

volatile 关键字是一种类型修饰符，volatile是“易变的”、“不稳定”的意思。它用来解决变量在“共享”环境下容易出现读取错误的问题。变量如果加了volatile修饰，则会从内存中重新装载内容，而不是直接从寄存器中拷贝内容，即告诉编译器不应对这样的对象进行优化。
const 可以是 volatile （如只读的状态寄存器）
指针可以是 volatile

（可以暂时先不看）
在本次线程内，当读取一个变量时，为了提高读取速度，编译器进行优化时有时会先把变量读取到一个寄存器中；以后，再读取变量值时，就直接从寄存器中读取；当变量值在本线程里改变时，会同时把变量的新值copy到该寄存器中，以保持一致。当变量因别的线程值发生改变，上面寄存器的值不会相应改变，从而造成应用程序读取的值和实际的变量值不一致。

volatile可以避免优化、强制内存读取的顺序，但是volatile并没有线程同步的语义，C++标准并不能保证它在多线程情况的正确性。C++11开始有一个很好用的库，那就是atomic类模板，在<atomic>头文件中，多个线程对atomic对象进行访问是安全的，并且提供不同种类的线程同步。它默认使用的是最强的同步，所以我们就使用默认的就好。

explicit

explicit用来防止由构造函数定义的隐式转换。

隐式转换：可以用单个实参来调用的构造函数定义了从形参类型到该类类型的一个隐式转换。

class things
{
    public:
        things(const std::string&name =""):
              m_name(name),height(0),weight(10){}
        int CompareTo(const things & other);
        std::string m_name;
        int height;
        int weight;
};

这里things的构造函数可以只用一个实参完成初始化。所以可以进行一个隐式转换，像下面这样：

things a;
................//在这里被初始化并使用。
std::string nm ="book_1";
//由于可以隐式转换，所以可以下面这样使用
int result = a.CompareTo(nm);

这段程序使用一个string类型对象作为实参传给things的CompareTo函数。这个函数本来是需要一个tings对象作为实参。现在编译器使用string nm来构造并初始化一个things对象，新生成的临时的things对象被传递给CompareTo函数，并在离开这段函数后被析构。

正确使用

class things
{
    public:
        explicit things(const std::string&name =""):
              m_name(name),height(0),weight(0){}
        int CompareTo(const things & other);
        std::string m_name;
        int height;
        int weight;
};

// 这时你仍然可以通过显式使用构造函数完成上面的类型转换：
things a;
................//在这里被初始化并使用。
std::string nm ="book_1";
//显示使用构造函数
int result = a.CompareTo(things(nm));

1

auto 和 decltype

auto类型说明符：让编译器通过初始值来推算变量的类型，auto定义的变量必须有初始值。
decltype 类型指示符：从表达式的类型推断出要定义的变量的类型

1
2
3

auto i = 0  			// i 为 int类型

decltype(f()) sum = x 	// sum的类型，是函数f()的返回值类型

assert()

断言，是宏，而非函数。assert 宏的原型定义在 <assert.h>（C）、<cassert>（C++）中，其作用是如果它的条件返回错误，则终止程序执行。可以通过定义 NDEBUG 来关闭 assert，但是需要在源代码的开头，include <assert.h> 之前。

assert() 使用

#define NDEBUG          // 加上这行，则 assert 不可用
#include <assert.h>

assert( p != NULL );    // assert 不可用

sizeof()

sizeof()是操作符，而非函数。

sizeof 对数组，得到整个数组所占空间大小。
sizeof 对指针，得到指针本身所占空间大小。

1
2
3

char a[] = "abcdef";	
cout << strlen(a) << endl;	// 6 统计数组长度，不包括\0
cout << sizeof(a) << endl;  // 7 统计数组长度，包括\0，到第一个\0就结束

#pragma pack(n)

设定结构体、联合以及类成员变量以 n 字节方式对齐

#pragma pack(n) 使用

#pragma pack(push)  // 保存对齐状态
#pragma pack(4)     // 设定为 4 字节对齐

struct test
{
    char m1;
    double m4;
    int m3;
};

#pragma pack(pop)   // 恢复对齐状态

位域

1	Bit mode: 2; // mode 占 2 位

类可以将其（非静态）数据成员定义为位域（bit-field），在一个位域中含有一定数量的二进制位。当一个程序需要向其他程序或硬件设备传递二进制数据时，通常会用到位域。

位域在内存中的布局是与机器有关的
位域的类型必须是整型或枚举类型，带符号类型中的位域的行为将因具体实现而定
取地址运算符（&）不能作用于位域，任何指针都无法指向类的位域

extern “C”

被 extern 限定的函数或变量是 extern 类型的
被 extern "C" 修饰的变量和函数是按照 C 语言方式编译和链接的

extern “C”的主要作用就是为了能够正确实现C++代码调用其他C语言代码。加上extern “C”后，会指示编译器这部分代码按C语言的进行编译，而不是C++的。

extern “C” 使用

#ifdef __cplusplus
extern "C" {
#endif

void *memset(void *, int, size_t);

#ifdef __cplusplus
}
#endif

C++ 中 struct 和 class

总的来说，struct 更适合看成是一个数据结构的实现体，class 更适合看成是一个对象的实现体。

区别

最本质的一个区别就是默认的访问控制

默认的继承访问权限。struct 是 public 的，class 是 private 的。
struct 作为数据结构的实现体，它默认的数据访问控制是 public 的，而 class 作为对象的实现体，它默认的成员变量访问控制是 private 的。

结构体 struct 和共同体 union（联合）的区别

结构体：将不同类型的数据组合成一个整体，是自定义类型。

共同体：不同类型的几个变量共同占用一段内存

1）结构体中的每个成员都有自己独立的地址，它们是同时存在的；

共同体中的所有成员占用同一段内存，它们不能同时存在。

2）sizeof(struct)是内存对齐后所有成员长度的总和，sizeof(union)是内存对齐后最长数据成员的长度。

#include <stdio.h>
#include <string.h>
 
union Data
{
   int i;
   float f;
   char  str[20];	
};
 
int main( )
{
   union Data data;        
 
   data.i = 10;
   printf( "data.i : %d\n", data.i);
   
   data.f = 220.5;
   printf( "data.f : %f\n", data.f);
   
   strcpy( data.str, "C Programming");
   printf( "data.str : %s\n", data.str);
 
   return 0;
}

/* 所有的成员都能完好输出，因为同一时间只用到一个成员。
data.i : 10
data.f : 220.500000
data.str : C Programming
*/

结构体为什么要内存对齐呢？

1 . 平台原因（移植原因）：不是所有的硬件平台都能访问任意地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。内存对齐，是为了让内存存取更有效率而采用的一种编译阶段优化内存存取的手段。

2 . 硬件原因：经过内存对齐之后，CPU的内存访问速度大大提升。

内存对齐规则

内存对齐是指首地址对齐，而不是说每个变量大小对齐
结构体内存对齐要求结构体内每一个成员变量都是内存对齐的
结构体第一个成员的 偏移量（offset）为0，以后每个成员相对于结构体首地址的 offset 都是该成员大小与有效对齐值中较小那个的整数倍，如有需要编译器会在成员之间加上填充字节。
结构体的总大小为有效对齐值的整数倍，如有需要编译器会在最末一个成员之后加上填充字节。

//32位系统
#include<stdio.h>
struct
{
    int i;    
    char c1;  
    char c2;  
}x1;

struct{
    char c1;  
    int i;    
    char c2;  
}x2;

struct{
    char c1;  
    char c2; 
    int i;    
}x3;

int main()
{
    printf("%d\n",sizeof(x1));  // 输出8
    printf("%d\n",sizeof(x2));  // 输出12
    printf("%d\n",sizeof(x3));  // 输出8
    return 0;
}

以上测试都是再Linux环境下进行，linux下默认#pragma pack(4)，且结构体中最长的数据类型为4个字节，所以有效对齐单位为4字节，下面根据上面所说的规则以 x2 来分析其内存布局：
首先使用规则1，对成员变量进行对齐：

1
2
3

sizeof(c1) = 1 <= 4(有效对齐位)，按照1字节对齐，占用第0单元；
sizeof(i) = 4 <= 4(有效对齐位)，相对于结构体首地址的偏移要为4的倍数，占用第4，5，6，7单元；
sizeof(c2) = 1 <= 4(有效对齐位)，相对于结构体首地址的偏移要为1的倍数，占用第8单元；

然后使用规则2，对结构体整体进行对齐：

x2 中变量 i 占用内存最大占4字节，而有效对齐单位也为4字节，两者较小值就是4字节。因此整体也是按照4字节对齐。由规则1得到 x2 占9个字节，此处再按照规则2进行整体的4字节对齐，所以整个结构体占用12个字节。

根据上面的分析，不难得出上面例子三个结构体的内存布局如下：

定义和声明的区别

声明是告诉编译器变量的类型和名字，不会为变量分配空间
定义需要分配空间，同一个变量可以被声明多次，但是只能被定义一次

C和C++的区别

（1）C是面向过程的语言，是一个结构化的语言，考虑如何通过一个过程对输入进行处理得到输出；C++是面向对象的语言，主要特征是“封装、继承和多态”。封装隐藏了实现细节，使得代码模块化；派生类可以继承父类的数据和方法，扩展了已经存在的模块，实现了代码重用；多态则是“一个接口，多种实现”，通过派生类重写父类的虚函数，实现了接口的重用。
（2）C和C++动态管理内存的方法不一样，C是使用malloc/free，而C++除此之外还有new/delete关键字。
（3）C++支持函数重载，C不支持函数重载
（4）C++中有引用，C中不存在引用的概念

C++中指针和引用的区别

1）指针是一个新的变量，存储了另一个变量的地址，我们可以通过访问这个地址来修改另一个变量；
引用只是一个别名，还是变量本身，对引用的任何操作就是对变量本身进行操作，以达到修改变量的目的
2）引用只有一级，而指针可以有多级
3）指针传参的时候，还是值传递，指针本身的值不可以修改，需要通过解引用才能对指向的对象进行操作。引用传参的时候，传进来的就是变量本身，因此变量可以被修改

引用作为函数参数以及返回值的好处

对比值传递，引用传参的好处：

1）在函数内部可以对此参数进行修改

2）提高函数调用和运行的效率（所以没有了传值和生成副本的时间和空间消耗）

如果函数的参数实质就是形参，不过这个形参的作用域只是在函数体内部，也就是说实参和形参是两个不同的东西，要想形参代替实参，肯定有一个值的传递。函数调用时，值的传递机制是通过“形参=实参”来对形参赋值达到传值目的，产生了一个实参的副本。即使函数内部有对参数的修改，也只是针对形参，也就是那个副本，实参不会有任何更改。函数一旦结束，形参生命也宣告终结，做出的修改一样没对任何变量产生影响。

用引用作为返回值最大的好处就是在内存中不产生被返回值的副本。

但是有以下的限制：

1）不能返回局部变量的引用。因为函数返回以后局部变量就会被销毁

2）不能返回函数内部new分配的内存的引用。虽然不存在局部变量的被动销毁问题，可对于这种情况（返回函数内部new分配内存的引用），又面临其它尴尬局面。例如，被函数返回的引用只是作为一个临时变量出现，而没有被赋予一个实际的变量，那么这个引用所指向的空间（由new分配）就无法释放，造成memory leak

3）可以返回类成员的引用，但是最好是const。因为如果其他对象可以获得该属性的非常量的引用，那么对该属性的单纯赋值就会破坏业务规则的完整性。

左值引用

常规引用，一般表示对象的身份。

右值引用

右值引用就是必须绑定到右值（一个临时对象、将要销毁的对象）的引用，一般表示对象的值。

右值引用可实现转移语义（Move Sementics）和精确传递（Perfect Forwarding），它的主要目的有两个方面：

消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率。
能够更简洁明确地定义泛型函数。

引用折叠

X& &、X& &&、X&& & 可折叠成 X&
X&& && 可折叠成 X&&

：：范围解析运算符

全局作用域符（::name）：用于类型名称（类、类成员、成员函数、变量等）前，表示作用域为全局命名空间
类作用域符（class::name）：用于表示指定类型的作用域范围是具体某个类的
命名空间作用域符（namespace::name）:用于表示指定类型的作用域范围是具体某个命名空间的

:: 使用

int count = 0;        // 全局（::）的 count

class A {
public:
    static int count; // 类 A 的 count（A::count）
};

int main() {
    ::count = 1;      // 设置全局的 count 的值为 1

    A::count = 2;     // 设置类 A 的 count 为 2

    int count = 0;    // 局部的 count
    count = 3;        // 设置局部的 count 的值为 3

    return 0;
}

———-

继承中的特点

有public, protected, private三种继承方式，它们相应地改变了基类成员的访问属性。

1.public 继承：基类 public 成员，protected 成员，private 成员的访问属性在派生类中分别变成：public, protected, private
2.protected 继承：基类 public 成员，protected 成员，private 成员的访问属性在派生类中分别变成：protected, protected, private
3.private 继承：基类 public 成员，protected 成员，private 成员的访问属性在派生类中分别变成：private, private, private

但无论哪种继承方式，上面两点都没有改变：

1.private 成员只能被本类成员（类内）和友元访问，不能被派生类访问；
2.protected 成员可以被派生类访问。

重载overload，覆盖（重写）override，隐藏（重定义）overwrite，这三者之间的区别

1）overload，函数名相同，参数列表（参数的类型，个数，顺序不同）不同，这就是函数重载，返回值类型可以不同。
特征：相同范围（同一个类中）、函数名字相同、参数不同、virtual关键字可有可无
2）override，派生类覆盖基类的虚函数，实现接口的重用，返回值类型必须相同
特征：不同范围（基类和派生类）、函数名字相同、参数相同、基类中必须有virtual关键字（必须是虚函数）
3）overwrite，派生类屏蔽了其同名的基类函数，返回值类型可以不同
特征：不同范围（基类和派生类）、函数名字相同、参数不同或者参数相同且无virtual关键字

**多态，虚函数，纯虚函数

多态：不同对象接收相同的消息产生不同的动作。多态包括编译时多态和运行时多态

运行时多态：通过继承和虚函数来体现的。
编译时多态：运算符重载上。

封装可以隐藏实现细节，使得代码模块化；继承可以扩展已存在的代码模块（类）；它们的目的都是为了——代码重用。多态也有代码重用的功能，还有解决项目中紧耦合的问题，提高程序的可扩展性。
C++实现多态的机制很简单，在继承体系下，将父类的某个函数给成虚函数（即加上virtual关键字），在派生类中对这个虚函数进行重写，利用父类的指针或引用调用虚函数。通过指向派生类的基类指针或引用，访问派生类中同名覆盖成员函数。对于虚函数调用来说，每一个对象内部都有一个虚表指针，在构造子类对象时，执行构造函数中进行虚表的创建和虚表指针的初始化，该虚表指针被初始化为本类的虚表。所以在程序中，不管你的对象类型如何转换，但该对象内部的虚表指针是固定的，所以呢，才能实现动态的对象函数调用，这就是C++多态性实现的原理。

需要注意的几点总结（基类有虚函数）：
1、每一个类都有虚表，单继承的子类拥有一张虚表，子类对象拥有一个虚表指针；若子类是多重继承（同时继承多个基类），则子类维护多张虚函数表（针对不同基类构建不同虚表），该子类的对象也将包含多个虚表指针。

2、虚表可以继承，如果子类没有重写虚函数，那么子类虚表中仍然会有该函数的地址，只不过这个地址指向的是基类的虚函数实现。如果基类3个虚函数，那么基类的虚表中就有三项（虚函数地址），派生类也会有虚表，至少有三项，如果重写了相应的虚函数，那么虚表中的地址就会改变，指向自身的虚函数实现。如果派生类有自己的虚函数，那么虚表中就会添加该项。

3、派生类的虚表中虚函数地址的排列顺序和基类的虚表中虚函数地址排列顺序相同。

第一：编译器在发现Father 类中有虚函数时，会自动为每个含有虚函数的类生成一份虚函数表，也叫做虚表，该表是一个一维数组，虚表里保存了虚函数的入口地址。

第二：编译器会在每个对象的前四个字节中保存一个虚表指针，即（vptr),指向对象所属类的虚表。在程序运行时的合适时机，根据对象的类型去初始化vptr，从而让vptr指向正确的虚表，从而在调用虚函数时，能找到正确的函数。

第三：所谓的合适时机，在派生类定义对象时，程序运行会自动调用构造函数，在构造函数中创建虚表并对虚表初始化。在构造子类对象时，会先调用父类的构造函数，此时，编译器只“看到了”父类，并为父类对象初始化虚表指针，令它指向父类的虚表；当调用子类的构造函数时，为子类对象初始化虚表指针，令它指向子类的虚表。

虚函数与纯虚函数

虚函数：在基类中用virtual的成员函数。允许在派生类中对基类的虚函数重新定义。
基类的虚函数可以有函数体，基类也可以实例化。
虚函数要有函数体，否则编译过不去。
虚函数在子类中可以不覆盖。
构造函数不能是虚函数。

纯虚函数：纯虚函数是只有声明没有实现的虚函数，是对子类的约束，是接口继承。包含纯虚函数的类是抽象类，它不能被实例化，只有实现了这个纯虚函数的子类才能生成对象。

纯虚函数后面有 = 0；
抽象类不可以实例化。但可以定义指针。
如果派生类如果不是先基类的纯虚函数，则仍然是抽象类。
抽象类可以包含虚函数。

类里如果声明了虚函数，这个函数是实现的，哪怕是空实现，它的作用就是为了能让这个函数在它的子类里面可以被覆盖，这样的话，编译器就可以使用后期绑定来达到多态了。纯虚函数只是一个接口，是个函数的声明而已，它要留到子类里去实现。

虚函数是怎么实现的

每一个含有虚函数的类都至少有有一个与之对应的虚函数表，其中存放着该类所有虚函数对应的函数指针（地址）

类的示例对象不包含虚函数表，只有虚指针

派生类会生成一个兼容基类的虚函数表。

构造函数为什么一般不定义为虚函数？而析构函数一般写成虚函数的原因？

1、构造函数不能声明为虚函数

因为创建一个对象时需要确定对象的类型，而虚函数是在运行时确定其类型的。而在构造一个对象时，由于对象还未创建成功，编译器无法知道对象的实际类型，是类本身还是类的派生类等等
虚函数的调用需要虚函数表指针，而该指针存放在对象的内存空间中；若构造函数声明为虚函数，那么由于对象还未创建，还没有内存空间，更没有虚函数表地址用来调用虚函数及构造函数了

2、析构函数最好声明为虚函数

首先析构函数可以为虚函数，当析构一个指向派生类的基类指针时，最好将基类的析构函数声明为虚函数，否则可以存在内存泄露的问题。
如果析构函数不被声明成虚函数，则编译器实施静态绑定，在删除指向派生类的基类指针时，只会调用基类的析构函数而不调用派生类析构函数，这样就会造成派生类对象析构不完全。

构造函数中是否可以调用虚函数

１.　从语法上讲，调用完全没有问题。

２.　但是从效果上看，往往不能达到需要的目的。

Effective 的解释是：

派生类对象构造期间进入基类的构造函数时，对象类型变成了基类类型，而不是派生类类型。

同样，进入基类析构函数时，对象也是基类类型。

所以，虚函数始终仅仅调用基类的虚函数（如果是基类调用虚函数），不能达到多态的效果，所以放在构造函数中是没有意义的，而且往往不能达到本来想要的效果。

在构造函数中调用

#include<iostream>
using namespace std;

class Base
{
public:
    Base()
    {
       Fuction();
    }

    virtual void Fuction()
    {
        cout << "Base::Fuction" << endl;
    }
};

class A : public Base
{
public:
    A()
    {
      Fuction();
    }

    virtual void Fuction()
    {
        cout << "A::Fuction" << endl;
    }
};

// 这样定义一个A的对象，会输出什么？
int main()
{
    A a;
}
/*
输出： 
Base::Fuction 
A::Fuction
*/

在析构函数中调用

#include <iostream>
using namespace std;

class A{
public:
    virtual void show(){
        cout<<"in A"<<endl;
    }
    virtual ~A(){show();}
};

class B:public A{
public:
    void show(){
        cout<<"in B"<<endl;
    }
};

int main(){
    A a;
    B b;
}

/*
输出： 
in A 
in A
*/

虚函数指针、虚函数表

虚函数指针：在含有虚函数类的对象中，指向虚函数表，在运行时确定。
虚函数表：在程序只读数据段（.rodata section，见：目标文件存储结构），存放虚函数指针，如果派生类实现了基类的某个虚函数，则在虚表中覆盖原本基类的那个虚函数指针，在编译时根据类的声明创建。

继承中，子类构造函数和析构函数调用顺序

子类析构时，要调用父类的析构函数吗？

构造函数：先调用父类构造函数，然后调用子类。

析构函数：先调用子类析构，然后调用父类。

并且析构函数要是virtual的，否则如果用父类的指针指向子类对象的时候，析构函数静态绑定，不会调用子类的析构。

不用显式调用，会自动调用

虚继承

虚继承用于解决多继承条件下的菱形继承问题（浪费存储空间、存在二义性）。

底层实现原理与编译器相关，一般通过虚基类指针和虚基类表实现，每个虚继承的子类都有一个虚基类指针（占用一个指针的存储空间，4字节）和虚基类表（不占用类对象的存储空间）（需要强调的是，虚基类依旧会在子类里面存在拷贝，只是仅仅最多存在一份而已，并不是不在子类里面了）；当虚继承的子类被当做父类继承时，虚基类指针也会被继承。

实际上，vbptr 指的是虚基类表指针（virtual base table pointer），该指针指向了一个虚基类表（virtual table），虚表中记录了虚基类与本类的偏移地址；通过偏移地址，这样就找到了虚基类成员，而虚继承也不用像普通多继承那样维持着公共基类（虚基类）的两份同样的拷贝，节省了存储空间。

虚继承与虚函数的联系与区别

相同之处：都利用了虚指针（均占用类的存储空间）和虚表（均不占用类的存储空间）
不同之处：
虚继承
- 虚基类依旧存在继承类中，只占用存储空间
- 虚基类表存储的是虚基类相对直接继承类的偏移
虚函数
- 虚函数不占用存储空间
- 虚函数表存储的是虚函数地址

模板类、成员模板、虚函数

模板类中可以使用虚函数
一个类（无论是普通类还是类模板）的成员模板（本身是模板的成员函数）不能是虚函数

抽象类、接口类、聚合类

抽象类：含有纯虚函数的类
接口类：仅含有纯虚函数的抽象类
聚合类：用户可以直接访问其成员，并且具有特殊的初始化语法形式。满足如下特点：
所有成员都是 public
没有定义任何构造函数
没有类内初始化
没有基类，也没有 virtual 函数

friend 友元类和友元函数

能访问私有成员
破坏封装性
友元关系不可传递
友元关系的单向性
友元声明的形式及数量不受限制

友元函数和友元类

友元提供了不同类的成员函数之间、类的成员函数和一般函数之间进行数据共享的机制。

通过友元，一个不同函数或者另一个类中的成员函数可以访问类中的私有成员和保护成员。

友元的正确使用能提高程序的运行效率，但同时也破坏了类的封装性和数据的隐藏性，导致程序可维护性变差。

1）友元函数

友元函数是可以访问类的私有成员的非成员函数。它是定义在类外的普通函数，不属于任何类，但是需要在类的定义中加以声明。

friend 类型函数名(形式参数);

一个函数可以是多个类的友元函数，只需要在各个类中分别声明。

2）友元类

友元类的所有成员函数都是另一个类的友元函数，都可以访问另一个类中的隐藏信息（包括私有成员和保护成员）。

friend class 类名;

使用友元类时注意：

友元关系不能被继承。
友元关系是单向的，不具有交换性。若类B是类A的友元，类A不一定是类B的友元，要看在类中是否有相应的声明。
友元关系不具有传递性。若类B是类A的友元，类C是B的友元，类C不一定是类A的友元，同样要看类中是否有相应的申明

**C++的内存管理

在C++中，内存被分成五个区：栈、堆、自由存储区、静态存储区、常量区

栈：存放函数的参数和局部变量，编译器自动分配和释放
堆：new关键字动态分配的内存，由程序员手动进行释放，否则程序结束后，由操作系统自动进行回收
自由存储区：由malloc分配的内存，和堆十分相似，由对应的free进行释放
全局/静态存储区：存放全局变量和静态变量
常量区：存放常量，不允许被修改

栈和堆的区别

	堆	栈
管理方式	堆中资源由程序员控制（容易产生memory leak）	栈资源由编译器自动管理，无需手工控制
内存管理机制	系统有一个记录空闲内存地址的链表，当系统收到程序申请时，遍历该链表，寻找第一个空间大于申请空间的堆结点，删除空闲结点链表中的该结点，并将该结点空间分配给程序（大多数系统会在这块内存空间首地址记录本次分配的大小，这样delete才能正确释放本内存空间，另外系统会将多余的部分重新放入空闲链表中）	只要栈的剩余空间大于所申请空间，系统为程序提供内存，否则报异常提示栈出。（这一块理解一下链表和队列的区别，不连续空间和连续空间的区别，应该就比较好理解这两种机制的区别了）
空间大小	堆是不连续的内存区域（因为系统是用链表来存储空闲内存地址，自然不是连续的），堆大小受限于计算机系统中有效的虚拟内存（32bit 系统理论上是4G），所以堆的空间比较灵活，比较大	栈是一块连续的内存区域，大小是操作系统预定好的，windows下栈大小是2M（也有是1M，在编译时确定，VC中可设置）。
碎片问题	对于堆，频繁的new/delete会造成大量碎片，使程序效率降低	对于栈，它是一个先进后出的队列，进出一一对应，不会产生碎片。（看到这里我突然明白了为什么面试官在问我堆和栈的区别之前先问了我栈和队列的区别）
生长方向	堆向上，向高地址方向增长。	栈向下，向低地址方向增长。
分配方式	堆都是动态分配（没有静态分配的堆）	栈有静态分配和动态分配，静态分配由编译器完成（如局部变量分配），动态分配由alloca函数分配，但栈的动态分配的资源由编译器进行释放，无需程序员实现。
分配效率	堆由C/C++函数库提供，机制很复杂。所以堆的效率比栈低很多。	栈是极其系统提供的数据结构，计算机在底层对栈提供支持，分配专门寄存器存放栈地址，栈操作有专门指令。

C++中内存泄漏的几种情况

内存泄漏是指己动态分配的堆内存由于某种原因程序未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果。

类的构造函数和析构函数中new和delete没有配套
在释放对象数组时没有使用delete[]，使用了delete
没有将基类的析构函数定义为虚函数，当基类指针指向子类对象时，如果基类的析构函数不是virtual，那么子类的析构函数将不会被调用，子类的资源没有正确释放，因此造成内存泄露
没有正确的清楚嵌套的对象指针

栈溢出的原因以及解决方法

栈溢出是指函数中的局部变量造成的溢出（注：函数中形参和函数中的局部变量存放在栈上）

栈的大小通常是1M-2M，所以栈溢出包含两种情况，一是分配的的大小超过栈的最大值，二是分配的大小没有超过最大值，但是接收的buf比原buf小。

1）函数调用层次过深,每调用一次,函数的参数、局部变量等信息就压一次栈

2）局部变量体积太大。

解决办法大致说来也有两种：

1> 增加栈内存的数目；如果是不超过栈大小但是分配值小的，就增大分配的大小

2> 使用堆内存；具体实现由很多种方法可以直接把数组定义改成指针,然后动态申请内存;也可以把局部变量变成全局变量，一个偷懒的办法是直接在定义前边加个static，呵呵，直接变成静态变量(实质就是全局变量)

什么是野指针

野指针不是NULL指针，是未初始化或者未清零的指针，它指向的内存地址不是程序员所期望的，可能指向了受限的内存。

成因：

指针变量没有被初始化
指针指向的内存被释放了，但是指针没有置NULL
指针超过了变量了的作用范围，比如b[10]，指针b+11

new、delete、malloc、free之间的关系

new/delete，malloc/free都是动态分配内存的方式

new / new[]：完成两件事，先底层调用 malloc 分配了内存，然后调用构造函数（创建对象）
delete/delete[]：也完成两件事，先调用析构函数（清理资源），然后底层调用 free 释放空间
new 在申请内存时会自动计算所需字节数，而 malloc 则需我们自己输入申请内存空间的字节数

既然有了malloc/free，C++中为什么还需要new/delete呢？

（1）库函数是依赖于库的，一定程度上独立于语言的。编译器不关心库函数的作用，只保证编译，调用函数参数和返回值符合语法，生成call函数的代码。
（2）运算符是语言自身的特性，有固定的语义，编译器知道意味着什么，由编译器解释语义，生成相应的代码。

malloc/free是库函数，new/delete是C++运算符。对于非内部数据类型而言，光用malloc/free无法满足动态对象的要求。new/delete是运算符，编译器保证调用构造和析构函数对对象进行初始化/析构。但是库函数malloc/free是库函数，不会执行构造/析构。

delete和delete[]的区别

delete只会调用一次析构函数，而delete[]会调用每个成员的析构函数
用new分配的内存用delete释放，用new[]分配的内存用delete[]释放

delete this 合法吗？

合法，但：

必须保证 this 对象是通过 new（不是 new[]、不是 placement new、不是栈上、不是全局、不是其他对象成员）分配的
必须保证调用 delete this 的成员函数是最后一个调用 this 的成员函数
必须保证成员函数的 delete this后面没有调用 this 了
必须保证 delete this 后没有人使用了

——

STL库用过吗？常见的STL容器有哪些？算法用过几个？

STL包括两部分内容：容器和算法

1. 容器即存放数据的地方，比如 array, vector，分为两类，序列式容器 和关联式容

序列式容器，其中的元素不一定有序，但是都可以被排序，比如vector,list,queue,stack，heap, priority-queue, slist
关联式容器，内部结构是一个平衡二叉树，每个元素都有一个键值和一个实值，比如map, set, hashtable, hash_set

2. 算法 有排序，复制等，以及各个容器特定的算法

3. 迭代器 是STL的精髓，迭代器提供了一种方法，使得它能够按照顺序访问某个容器所含的各个元素，但无需暴露该容器的内部结构，它将容器和算法分开，让二者独立设计。

vector 实现机制

C++中vector和list的区别

vector和数组类似，拥有一段连续的内存空间。vector申请的是一段连续的内存，当插入新的元素内存不够时，通常以2倍重新申请更大的一块内存，将原来的元素拷贝过去，释放旧空间。因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。

list 是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n); 但由于链表的特点，能高效地进行插入和删除。

vector 拥有一段连续的内存空间，能很好的支持随机存取，因此vector::iterator支持“+”，“+=”，“<”等操作符。

list 的内存空间可以是不连续，它不支持随机访问，因此list::iterator则不支持“+”、“+=”、“<”等

vector::iterator和list::iterator都重载了“++”运算符。

总之，如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector;

如果需要大量的插入和删除，而不关心随机存取，则应使用list。

C++常见容器的时间复杂度

map ，set，multimap，multiset ：这4种容器是采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:

插入：$O(logN)$
查找：$O(logN)$
删除：$O(logN)$

hash_map，hash_set，hash_multimap，hash_multiset：这4种容器采用哈希表实现。

插入：O(1)，最坏情况 O(N)
查找：O(1)，最坏情况 O(N)
删除：O(1)，最坏情况 O(N)

标准库提供的8个关联容器

map 和 set 的原理

map和set的底层实现主要通过红黑树来实现

红黑树是一种特殊的二叉查找树

1）每个节点或者是黑色，或者是红色

2）根节点是黑色

3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

4）如果一个节点是红色的，则它的子节点必须是黑色的

5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

特性4）5）决定了没有一条路径会比其他路径长出2倍，因此红黑树是接近平衡的二叉树。

map 和 unordered_map 区别

map是STL中的一个关联容器，提供键值对的数据管理。底层通过红黑树来实现，实际上是二叉排序树和非严格意义上的二叉平衡树。所以在map内部所有的数据都是有序的，且map的查询、插入、删除操作的时间复杂度都是O(logN)。

unordered_map和map类似，都是存储key-value对，可以通过key快速索引到value，不同的是unordered_map不会根据key进行排序。unordered_map底层是一个防冗余的哈希表，存储时根据key的hash值判断元素是否相同，即unoredered_map内部是无序的。

C++包含的新特性

列表初始化。在引入C++11之前，仅仅有数组能使用初始化列表，C++11则其它容比如vertor、map、string都可以使用列表初始化
类型指示符 auto，decltype
auto：让编译器通过初始值来推算变量的类型
decltype：从表达式的类型推断出要定义变量的类型
使用基于范围的for循环

string str("some string");
// 每行输出str中的一个字符
for (auto c : str)
	cout << c << endl;

lambda表达式

智能指针

智能指针是将基本类型指针封装为类对象指针（这个类肯定是个模板，以适应不同基本类型的需求），并在析构函数里编写delete语句删除指针指向的内存空间。

智能指针是一个类，这个类的构造函数中传入一个普通指针，析构函数中释放传入的指针。智能指针的类都是栈上的对象，所以当函数（或程序）结束时会自动被释放。

智能指针就是一种栈上创建的对象，函数退出时会调用其析构函数，这个析构函数里面往往就是一堆计数之类的条件判断，如果达到某个条件，就把真正指针指向的空间给释放了。

注意事项：不能将指针直接赋值给一个智能指针，一个是类，一个是指针。

常用的智能指针

C++ 标准库（STL）中，头文件：#include <memory>

C++ 98

1	std::auto_ptr<std::string> ps (new std::string(str));

C++ 11

Class shared_ptr 实现共享式拥有（shared ownership）概念。多个智能指针指向相同对象，该对象和其相关资源会在 “最后一个 reference 被销毁” 时被释放。为了在结构较复杂的情景中执行上述工作，标准库提供 weak_ptr、bad_weak_ptr 和 enable_shared_from_this 等辅助类。
Class unique_ptr 实现独占式拥有（exclusive ownership）或严格拥有（strict ownership）概念，保证同一时间内只有一个智能指针可以指向该对象。你可以移交拥有权。它对于避免内存泄漏（resource leak）——如 new 后忘记 delete ——特别有用。

shared_ptr

多个智能指针可以共享同一个对象，对象的最末一个拥有着有责任销毁对象，并清理与该对象相关的所有资源。

支持定制型删除器（custom deleter），可防范 Cross-DLL 问题（对象在动态链接库（DLL）中被 new 创建，却在另一个 DLL 内被 delete 销毁）、自动解除互斥锁

weak_ptr

weak_ptr 允许你共享但不拥有某对象，一旦最末一个拥有该对象的智能指针失去了所有权，任何 weak_ptr 都会自动成空（empty）。因此，在 default 和 copy 构造函数之外，weak_ptr 只提供 “接受一个 shared_ptr” 的构造函数。

可打破环状引用（cycles of references，两个其实已经没有被使用的对象彼此互指，使之看似还在 “被使用” 的状态）的问题

unique_ptr

unique_ptr 是 C++11 才开始提供的类型，是一种在异常时可以帮助避免资源泄漏的智能指针。采用独占式拥有，意味着可以确保一个对象和其相应的资源同一时间只被一个 pointer 拥有。一旦拥有着被销毁或编程 empty，或开始拥有另一个对象，先前拥有的那个对象就会被销毁，其任何相应资源亦会被释放。

unique_ptr 用于取代 auto_ptr

auto_ptr

被 c++11 弃用，原因是缺乏语言特性如 “针对构造和赋值” 的 std::move 语义，以及其他瑕疵。

auto_ptr 与 unique_ptr 比较

auto_ptr 可以赋值拷贝，复制拷贝后所有权转移；unqiue_ptr 无拷贝赋值语义，但实现了move 语义；
auto_ptr 对象不能管理数组（析构调用 delete），unique_ptr 可以管理数组（析构调用 delete[] ）；

智能指针的作用

C++程序设计中使用堆内存是非常频繁的操作，堆内存的申请和释放都由程序员自己管理。程序员自己管理堆内存可以提高了程序的效率，但是整体来说堆内存的管理是麻烦的，C++11中引入了智能指针的概念，方便管理堆内存。使用普通指针，容易造成堆内存泄露（忘记释放），二次释放，野指针，程序发生异常时内存泄露等问题等，使用智能指针能更好的管理堆内存。

强制类型转换运算符

类型转化机制可以分为隐式类型转换和显示类型转化（强制类型转换）

(new-type) expression

new-type (expression)

隐式类型转换比较常见，在混合类型表达式中经常发生；四种强制类型转换操作符：

static_cast、dynamic_cast、const_cast、reinterpret_cast

1）static_cast ：编译时期的静态类型检查

static_cast < type-id > ( expression )

该运算符把expression转换成type-id类型，在编译时使用类型信息执行转换，在转换时执行必要的检测（指针越界、类型检查），其操作数相对是安全的

2）dynamic_cast：运行时的检查

用于在集成体系中进行安全的向下转换downcast，即基类指针/引用->派生类指针/引用

dynamic_cast是4个转换中唯一的RTTI操作符，提供运行时类型检查。

dynamic_cast如果不能转换返回NULL

dynamic_cast转为引用类型的时候转型失败会抛bad_cast

源类中必须要有虚函数，保证多态，才能使用dynamic_cast(expression)

3）const_cast

去除const常量属性，使其可以修改 ; volatile属性的转换

4）reinterpret_cast

通常为了将一种数据类型转换成另一种数据类型

C++文件编译与执行的四个阶段

1）预处理：根据文件中的预处理指令来修改源文件的内容

2）编译：编译成汇编代码

3）汇编：把汇编代码翻译成目标机器指令

4）链接：链接目标代码生成可执行程序

gcc编译的四个步骤, 以最简单的hello.c为例子

一步到位：gcc hello.c

这条命令隐含执行了
（1）预处理
（2）编译
（3）汇编
（4）链接
这里未指定输出文件，默认输出为a.out
gcc编译C源码有四个步骤：
预处理 —-> 编译 —-> 汇编 —-> 链接
现在我们就用gcc的命令选项来逐个剖析gcc过程。

1）预处理(Pre-processing)

在该阶段，编译器将C源代码中的包含的头文件如stdio.h添加进来
参数：”-E”
用法：gcc -E hello.c -o hello.i
作用：将hello.c预处理输出hello.i文件。

2）编译(Compiling)

第二步进行的是编译阶段，在这个阶段中，gcc首先要检查代码的规范性、是否有语法错误等，以确定代码的实际要做的工作，在检查无误后，gcc把代码翻译成汇编语言。
参数：”-S”
用法：gcc –S hello.i –o hello.s
作用：将预处理输出文件hello.i汇编成hello.s文件。

3）汇编(Assembling)

汇编阶段是把编译阶段生成的”.s”文件转成二进制目标代码“.o”文件
参数：“-c”
用法：gcc –c hello.s –o hello.o
作用：将汇编输出文件hello.s编译输出hello.o文件。

4）链接(Link)

在成功编译之后，就进入了链接阶段。
用法：gcc hello.o –o hello
作用：将编译输出文件hello.o链接成最终可执行文件hello。
运行该可执行文件，出现正确的结果如下。
>>> ./hello
Hello World!

gcc 和 g++的区别

简单来说，gcc与g++都是GNU(组织)的一个编译器。需要注意以下几点：

gcc与g++都可以编译c代码与c++代码。但是：后缀为.c的，gcc把它当做C程序，而g++当做是C++程序；后缀为.cpp的，两者都会认为是C++程序。
编译阶段，g++会调用gcc，对于c++代码，两者是等价的，但是因为gcc命令不能自动和C＋＋程序使用的库联接，所以通常用g++来完成链接。
编译可以用gcc/g++，而链接可以用g++或者gcc -lstdc++。因为gcc命令不能自动和C＋＋程序使用的库联接（当然可以选择手动链接，使用命令如下），所以通常使用g++来完成联接。但在编译阶段，g++会自动调用gcc，二者等价。

1	gcc main.cpp -lstdc++

——

拷贝构造函数

拷贝构造函数是一种特殊的构造函数，函数的名称必须和类名称一致，它的唯一的一个参数是本类型的一个引用变量，该参数是const类型，不可变的。例如：类X的拷贝构造函数的形式为X(X& x)。

#include <iostream>
using namespace std;

class CExample {
private:
    int a;
public:
    CExample(int b)
    { a=b;}
    
    CExample(const CExample& C) // 自定义的拷贝构造函数
    {
        a=C.a;
    }
    void Show ()
    {
        cout<<a<<endl;
    }
};

int main()
{
    CExample A(100);
    CExample B=A;
    B.Show ();
    return 0;
}

调用拷贝构造函数（三种情况）

当用一个已初始化过了的自定义类类型对象去初始化另一个新构造的对象的时候，拷贝构造函数就会被自动调用。也就是说，当类的对象需要拷贝时，拷贝构造函数将会被调用。以下情况都会调用拷贝构造函数：
（1）一个对象以值传递的方式传入函数体
（2）一个对象以值传递的方式从函数返回
（3）一个对象需要通过另外一个对象进行初始化。

如果在类中没有显式地声明一个拷贝构造函数，那么，编译器将会自动生成一个默认的拷贝构造函数，该构造函数完成对象之间的浅拷贝。

举例：

#include <iostream>
#include <string>
using namespace std;
class A{
	private:
		int data;
	public:
		A(int i){ data = i;} 	//自定义的构造函数
		A(A && a);  			//拷贝构造函数 
		int getdata(){return data;} 
};
//拷贝构造函数 
A::A(A && a){
	data = a.data;
	cout <<"拷贝构造函数执行完毕"<<endl;
}
//参数是对象，值传递，调用拷贝构造函数
int getdata1(A a){
	return a.getdata();
}
//参数是引用，引用传递，不调用拷贝构造函数 
int getdata2(A &a){
	return a.getdata();
} 
//返回值是对象类型，会调用拷贝构造函数
 A getA1(){
 	A a(0);
 	return a;
 } 
 //返回值是引用类型，会调用拷贝构造函数，因为函数体内生成的对象是临时的，离开函数就消失
 A& getA2(){
 	A a(0);
 	return a;
 } 
 int main(){
    A a1(1);  
    A b1(a1);           		//用a1初始化b1，调用拷贝构造函数  
    A c1=a1;            		//用a1初始化c1，调用拷贝构造函数  
    int i=getdata1(a1);        	//函数形参是类的对象，调用拷贝构造函数  
    int j=getdata2(a1);      	//函数形参类型是引用，不调用拷贝构造函数  
    A d1=getA1();       		//调用拷贝构造函数  
    A e1=getA2();     			//调用拷贝构造函数  
    return 0;  
}

浅拷贝和深拷贝的区别

深拷贝和浅拷贝可以简单的理解为：如果一个类拥有资源，当这个类的对象发生复制过程的时候，如果资源重新分配了就是深拷贝；反之没有重新分配资源，就是浅拷贝。

浅拷贝的问题

浅拷贝资源后在释放资源的时候会产生资源归属不清的情况导致程序运行出错。比如类内成员变量需要动态开辟堆内存，如果实行浅拷贝(位拷贝)，也就是把对象里的值完全复制给另一个对象，如A=B。这时，如果B中有一个成员变量指针已经申请了内存，那A中的那个成员变量也指向同一块内存。这就出现了问题：当B把内存释放了（如：析构），这时A内的指针就是野指针了，出现运行错误。

深拷贝的例子

#include <iostream>
using namespace std;
class CA
{
　public:
　　CA(int b,char* cstr)
　　{
　　　a=b;
　　　str=new char[b];
　　　strcpy(str,cstr);
　　}
　　CA(const CA& C)
　　{
　　　a=C.a;
　　　str=new char[a]; //深拷贝
　　　if(str!=0)
　　　　strcpy(str,C.str);
　　}
　　void Show()
　　{
　　　cout<<str<<endl;
　　}
　　~CA()
　　{
　　　delete str;
　　}
　private:
　　int a;
　　char *str;
};

int main()
{
　CA A(10,"Hello!");
　CA B=A;
　B.Show();
　return 0;
}

Reference： 1

NULL 和 nullptr 区别

NULL来自C语言，一般由宏定义实现，C语言中，NULL被定义为(void*)0。而在C++中，NULL则被定义为整数0。nullptr则是C++11的新增关键字，是用来专门区分0、NULL的。

C++不允许直接将void*隐式的转化为其他类型。C++中存在函数重载，比如有两个函数：

1 2	void func(int a); void func(char *a);

如果NULL被定义为0，func（NULL）会去调用void func（int），这是不合理的，所以引入nullptr，专门用来区分0、NULL。

nullptr的类型为nullptr_t，能够隐式的转换为任何指针。

lambda 捕获对象的实现（待补充）

堆定义的头文件

1	#include <algorithm>

模板类

long long根以前的C++ 版本有什么区别

long long是C++的64位整型的基本类型，“现任”长整型。long long占用8个字节，数据表示范围也从int的 [$-2^{31},2^{31}-1$] ，升级到 [$-2^{63},2{63}-1]$]。早期的C/C++标准中并没有规定64位长整型的规范，因此不同的编译器对这一模糊概念有不同的定义。

#include<file.h> #include “file.h” 的区别

前者是从标准库路径寻找
后者是从当前工作路径

.hpp 和 .h 区别

.hpp，本质就是将.cpp的实现代码混入.h头文件当中，定义与实现都包含在同一文件，则该类的调用者只需要include该.hpp文件即可，无需再将cpp加入到project中进行编译。而实现代码将直接编译到调用者的obj文件中，不再生成单独的obj，采用hpp将大幅度减少调用project中的cpp文件数与编译次数，也不用再发布lib与dll文件，因此非常适合用来编写公用的开源库。

hpp的优点不少，但是编写中有以下几点要注意： 
1、是Header Plus Plus的简写。（.h和.hpp就如同.c和.cpp似的） 
2、与.h类似，.hpp是C++程序头文件格式。 
3、是VCL专用的头文件,已预编译。 
4、是一般模板类的头文件。 
5、一般来说，.h里面只有声明，没有实现，而.hpp里声明实现都有，后者可以减少.cpp的数量。 
6、.h里面可以有using namespace std，而.hpp里则无。 
7、不可包含全局对象和全局函数。

文件操作

/*
    文件操作：写入+读取字符串
    r: 只读方式打开文本文件，不能写
    w: 只写方式打开文本文件，写了直接覆盖原来的
    a: 只写（添加）方式打开，写了添加在原来的后面
    +: 与上面的 r、 w、 a 结合，表示以读写方式打开文文本件
    b: 与上面的字符组合，表示打开二进制文件
*/
int main() {
    /* ----------------- 打开文件并写入一行语句 ------------------- */
    FILE *fp;
    char line[100];
    int len;
    while ((fp = fopen("./file.txt", "a+")) == NULL) {   // 只写方式打开文件，并用
        printf("打开文件失败！\n");
        exit(0);
    }
    gets(line);                 // 控制台获取一行
    len = strlen(line);
    fputs(line, fp);
    fclose(fp);

    /* ----------------- 打开文件，读取一行，并输出读取的一行 ------------------- */
    while ((fp = fopen("./file.txt", "rb")) == NULL) {
        printf("打开文件失败！\n");
        exit(0);
    }
    fgets(line, 100, fp);    // 从文件中读取100个字符 
    puts(line);
    return 0;
}

**其他问题待整理

操作系统

一、进程与线程—–

进程是资源分配的基本单位
线程是资源调度的基本单位
进程有独立的系统资源，一个进程中可以有多个线程，多个线程共享进程资源
进程通信需要借助IPC，线程间可以通过直接读写同一进程中的数据进行通信
进程在创建、切换和销毁时开销比较大，而线程比较小。
进程间不会相互影响；但一个线程挂掉将导致整个进程挂掉
进程试用于多核、多机分布；线程适用于多核
引入进程是为了使多个程序可以并发的执行，以提高系统的资源利用率和吞吐量。
引入线程目的是为了减少程序在并发执行过程中的开销，使OS的并发效率更高。

进程通信与同步

进程通信：进程间传输信息
进程同步：控制多个进程按一定顺序执行

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

进程之间的通信方式

一、线程
- os.fork()实现多进程
- multiprocessing 多进程模块（可以跨平台）
   - Process类 创建多进程，
   - Pool进程池类
- 子进程 subprocess模块

进程间通信
- Queue 消息队列
- Pipes 管道

二、线程
- threading线程模块
- Lock 加锁，用于线程同步
注意：由于python中有GIL锁，其把所有线程的执行代码都给伤了锁，所以，多线程在python中只能交替执行，无法利用多个核。
- ThreadLocal 同于多线程同步，解决了参数在一个线程中个个函数之间相互传递的问题。

管道（PIPE）
无名管道：一种半双工的通信方式（即数据只能在一个方向上流动），只能在具有亲缘关系的进程间使用（父子进程）
- 优点：简单方便
- 缺点：
1. 局限于单向通信
2. 只能创建在它的进程以及其有亲缘关系的进程之间
3. 缓冲区有限
有名管道：一种半双工的通信方式，它允许无亲缘关系进程间的通信
- 优点：可以实现任意关系的进程间的通信
- 缺点：
1. 长期存于系统中，使用不当容易出错
2. 缓冲区有限
消息队列（Message Queue）：是消息的链表，存放在内核中，并由消息队列标识符(队列ID)标识
优点：可以实现任意进程间的通信，并通过系统调用函数来实现消息发送和接收之间的同步。
缺点：信息的复制需要额外消耗 CPU 的时间，不适宜于信息量大或操作频繁的场合
信号量（Semaphore）：是一个计数器，用来控制多个进程对共享资源的访问。主要用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。
优点：可以同步进程
缺点：信号量有限
信号（Signal）：一种比较复杂的通信方式，用于通知接收进程某个事件已经发生
共享内存（Shared Memory）：它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等
优点：无须复制，快捷，信息量大
缺点：
1. 多个进程可以同时操作，所以需要进行同步
2. 利用内存缓冲区直接交换信息，内存的实体存在于计算机中，只能同一个计算机系统中的诸多进程共享，不方便网络通信
套接字（Socket）：可用于不同主机间的进程通信
优点：
1. 传输数据为字节级，传输数据可自定义，数据量小、效率高
2. 传输数据时间短，性能高
3. 适合于客户端和服务器端之间信息实时交互
4. 可以加密,数据安全性强
缺点：需对传输的数据进行解析，转化成应用级的数据。

进程之间的同步方式(不是很清晰)

主要通过信号量，一个计数器，来控制多个进程对共享资源的访问。

临界区：对临界资源进行访问的那段代码称为临界区。为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。
同步与互斥
同步：多个进程按一定顺序执行
互斥：多个进程在同一时刻只有一个进程能进入临界区
信号量：是一个整型变量，可以对其执行 P 和 V 操作
P : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
V ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 V 操作。

P 和 V 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

typedef int semaphore;
semaphore mutex = 1;
void T1() {
    P(&mutex);
    // 临界区
    V(&mutex);
}

void T2() {
    P(&mutex);
    // 临界区
    V(&mutex);
}

使用信号量实现生产者-消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

Reference: 1

——

线程之间的通信/同步方式

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

锁机制：包括互斥锁/量（mutex）、读写锁（reader-writer lock）、自旋锁（spin lock）、条件变量（condition）
互斥锁/量（mutex）：提供了以排他方式防止数据结构被并发修改的方法。
读写锁（reader-writer lock）：允许多个线程同时读共享数据，而对写操作是互斥的。
自旋锁（spin lock）与互斥锁类似，都是为了保护共享资源。互斥锁是当资源被占用，申请者进入睡眠状态；而自旋锁则循环检测保持者是否已经释放锁。
条件变量（condition）：可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
信号量机制(Semaphore)
无名线程信号量
命名线程信号量
信号机制(Signal)：类似进程间的信号处理
屏障（barrier）：屏障允许每个线程等待，直到所有的合作线程都达到某一点，然后从该点继续执行。

进程之间的通信方式以及优缺点来源于：进程线程面试题总结

线程安全和线程不安全

线程安全：就是多线程访问时，采用了加锁机制，当一个线程访问该类的某个数据时，进行保护，其他线程不能进行访问直到该线程读取完，其他线程才可以使用，不会出现数据不一致或者数据污染。
线程不安全：就是不提供数据访问保护，有可能多个线程先后更改数据所得到的数据就是脏数据。

进程/线程的私有、共享资源

进程之间私有和共享的资源

私有：地址空间、栈、堆、全局变量、寄存器
共享：进程目录、进程 ID、代码段、公共数据，

线程之间私有和共享的资源

私有：线程栈、寄存器、程序寄存器
共享：地址空间、堆、全局变量、静态变量

多进程与多线程对比

（1）对比

对比维度	多进程	多线程	总结
数据共享、同步	数据共享复杂，需要用 IPC；数据是分开的，同步简单	因为共享进程数据，数据共享简单，但也是因为这个原因导致同步复杂	各有优势
内存、CPU	占用内存多，切换复杂，CPU 利用率低	占用内存少，切换简单，CPU 利用率高	线程占优
创建销毁、切换	创建销毁、切换复杂，速度慢	创建销毁、切换简单，速度很快	线程占优
编程、调试	编程简单，调试简单	编程复杂，调试复杂	进程占优
可靠性	进程间不会互相影响	一个线程挂掉将导致整个进程挂掉	进程占优
分布式	适应于多核、多机分布式；如果一台机器不够，扩展到多台机器比较简单	适应于多核分布式	进程占优

（2）优劣

优劣	多进程	多线程
优点	编程、调试简单，可靠性较高	创建、销毁、切换速度快，内存、资源占用小
缺点	创建、销毁、切换速度慢，内存、资源占用大	编程、调试复杂，可靠性较差

（3）选择

需要频繁创建销毁的优先用线程
需要进行大量计算的优先使用线程
强相关的处理用线程，弱相关的处理用进程
可能要扩展到多机分布的用进程，多核分布的用线程
都满足需求的情况下，用你最熟悉、最拿手的方式

多进程与多线程间的对比、优劣与选择来自：多线程还是多进程的选择及区别

Linux 内核的同步方式

原因

在现代操作系统里，同一时间可能有多个内核执行流在执行，因此内核其实像多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上，更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。

同步方式

原子操作
信号量（semaphore）
读写信号量（rw_semaphore）
自旋锁（spinlock）
大内核锁（BKL，Big Kernel Lock）
读写锁（rwlock）
大读者锁（brlock-Big Reader Lock）
读-拷贝修改(RCU，Read-Copy Update)
顺序锁（seqlock）

来自：Linux 内核的同步机制，第 1 部分、Linux 内核的同步机制，第 2 部分

死锁

多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

原因

系统资源不足
资源分配不当
进程运行推进顺序不合适

产生条件

互斥：资源不能被共享，只能由一个进程使用
占有和等待：已经得到资源的进程可以再次申请新的资源
不可抢占：已经分配的资源不能从相应的进程中被强制地剥夺
循环等待：系统中若干进程组成环路，改环路中每个进程都在等待相邻进程正占用的资源

预防

打破互斥条件：改造独占性资源为虚拟资源，大部分资源已无法改造。
打破不可抢占条件：当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。
打破占有和等待条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有和等待。
打破循环等待条件：实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源。
有序资源分配法
银行家算法：当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

Reference: 1 银行家算法

进程状态

就绪状态（ready）：等待被调度
运行状态（running）
阻塞状态（waiting）：等待资源

注意一下两点：

只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

1. 批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）

（1）先来先服务 first-come first-serverd（FCFS）

按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

（2）短作业优先 shortest job first（SJF）

按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

（3）最短剩余时间优先 shortest remaining time next（SRTN）

按估计剩余时间最短的顺序进行调度。

2. 交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

（1）时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
而如果时间片过长，那么实时性就不能得到保证。

img

（2）优先级调度

为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

（3）多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

img

阻塞与非阻塞

阻塞：是指调用线程或者进程被操作系统挂起。
非阻塞：是指调用线程或者进程不会被操作系统挂起。

并发、并行

并发（concurrency）：指宏观上看起来两个程序在同时运行，比如说在单核cpu上的多任务。但是从微观上看两个程序的指令是交织着运行的，你的指令之间穿插着我的指令，我的指令之间穿插着你的，在单个周期内只运行了一个指令。这种并发并不能提高计算机的性能，只能提高效率。

并行（parallelism）：指严格物理意义上的同时运行，比如多核cpu，两个程序分别运行在两个核上，两者之间互不影响，单个周期内每个程序都运行了自己的指令，也就是运行了两条指令。这样说来并行的确提高了计算机的效率。所以现在的cpu都是往多核方面发展。

二、内存管理—–

物理地址和虚拟地址

将主板上的物理内存条所提供的内存空间定义为物理内存空间，其中每个内存单元的实际地址就是物理地址
将应用程序员看到的内存空间定义为虚拟地址空间(或地址空间)，其中的地址就叫做虚拟地址

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。
从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

img

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为（110 000000000100）。

img

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

1. 最佳(OPT)

Optimal replacement algorithm. 所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

2. 最近最久未使用(LRU)

Least Recently Used. 虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

img

3. 最近未使用(NRU)

Not Recently Used. 每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：

R=0，M=0
R=0，M=1
R=1，M=0
R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）

4. 先进先出(FIFO)

First In First Out. 选择换出的页面是最先进入的页面。该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。

5. 第二次机会算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

img

6. 时钟

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

img

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。

img

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

img

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页与分段的比较

对程序员的透明性：分页透明，但是分段需要程序员显示划分每个段。
地址空间的维度：分页是一维地址空间，分段是二维的。
大小是否可以改变：页的大小不可变，段的大小可以动态改变。
出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

三、设备管理—–

磁盘结构

盘面（Platter）：一个磁盘有多个盘面；
磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
制动手臂（Actuator arm）：用于在磁道之间移动磁头；
主轴（Spindle）：使整个盘面转动。

img

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. 先来先服务

FCFS, First Come First Served.按照磁盘请求的顺序进行调度。优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

2. 最短寻道时间优先

SSTF, Shortest Seek Time First

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

img

3. 电梯算法

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

img

Reference: 操作系统面试整理

Python

Python面试集合

常用函数

Reference: 1

map()

语法：map(func, *iterable)：将func用于每个iterable对象

import re
str = input()								# [1, 2, 3]
pattern = re.compile(r'\d+')
num_str_list = re.findall(pattern, str)		# ['1', '2', '3']
num_list = list(map(int, num_str_list))		# [1, 2, 3]
print(num_list)

1	list(map(lambda a,b:a+b,[1,2,3,4],[5,6,7])) # [6, 8, 10]

reduce()

reduce() 函数会对参数序列中元素进行累积。函数将一个数据集合（链表，元组等）中的所有数据进行下列操作：用传给 reduce 中的函数 function（有两个参数）先对集合中的第 1、2 个元素进行操作，得到的结果再与第三个数据用 function 函数运算，最后得到一个结果。

语法：reduce(function, iterable[, initializer])

参数：

function – 函数，有两个参数

iterable – 可迭代对象

initializer – 可选，初始参数

返回：返回函数计算结果。

from functools import reduce
def add(x, y) :            # 两数相加
	return x + y
reduce(add, [1,2,3,4,5])   # 计算列表和：1+2+3+4+5
# 15
reduce(lambda x, y: x+y, [1,2,3,4,5])  # 使用 lambda 匿名函数
# 15

zip()

zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。

如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。

语法：zip([iterable, ...])

参数说明：iterabl：一个或多个迭代器;

返回元祖列表

>>>a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b)     # 打包为元组的列表
[(1, 4), (2, 5), (3, 6)]
>>> zip(a,c)              # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]
>>> zip(*zipped)          # 与 zip 相反，*zipped 可理解为解压，返回二维矩阵式
[(1, 2, 3), (4, 5, 6)]

strip()

移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。注意：该方法只能删除开头或是结尾的字符，不能删除中间部分的字符。

str = "00000003210Runoob01230000000"; 
print str.strip( '0' );  # 去除首尾字符 0

str2 = "   Runoob      ";   # 去除首尾空格
print str2.strip();

# 获取一行，并提取其中的数字，存放与list中
while True:
    line = sys.stdin.readline().strip()  # .strip()用于出去该行末尾的空格或回车
    if line == '':
        break
        nums = list(map(int, list(line.split(' '))))
        print(nums)

split()

通过指定分隔符对字符串进行切片，如果参数 num 有指定值，则分隔 num+1 个子字符串

str = "Line1-abcdef \nLine2-abc \nLine4-abcd";
print(str.split( ))       # 以空格为分隔符，包含 \n
print(str.split(' ', 1 )) # 以空格为分隔符，分隔成两个

# ['Line1-abcdef', 'Line2-abc', 'Line4-abcd']
# ['Line1-abcdef', '\nLine2-abc \nLine4-abcd']

join()

Python join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串。

语法：str.join(sequence)

1
2
3

str = "-";
seq = ("a", "b", "c"); # 字符串序列
print(str.join(seq)); # a-b-c

find()

检测字符串中是否包含子字符串 str ，如果指定 beg（开始）和 end（结束）范围，则检查是否包含在指定范围内，如果包含子字符串返回开始的索引值，否则返回-1。

语法：str.find(str, beg=0, end=len(string))

str1 = "this is string example....wow!!!";
str2 = "exam";
 
print str1.find(str2);		# 15
print str1.find(str2, 10);	# 15
print str1.find(str2, 40);	# -1

index()

Python index() 方法检测字符串中是否包含子字符串 str ，如果指定 beg（开始）和 end（结束）范围，则检查是否包含在指定范围内，该方法与 python find()方法一样，只不过如果str不在 string中会报一个异常。

语法：str.index(str, beg=0, end=len(string))

如果包含子字符串返回开始的索引值，否则抛出异常。

str1 = "this is string example....wow!!!";
str2 = "exam";
print str1.index(str2); 	# 15
print str1.index(str2, 10); # 15
print str1.index(str2, 40); # 报异常

count()

用于统计字符串里某个字符出现的次数。可选参数为在字符串搜索的开始与结束位置。

语法：str.count(sub, start= 0,end=len(string))

str = "this is string example....wow!!!";
 
sub = "i";
print "str.count(sub, 4, 40) : ", str.count(sub, 4, 40)

sub = "wow";
print "str.count(sub) : ", str.count(sub)

# str.count(sub, 4, 40) :  2
# str.count(sub) :  1

逆序迭代

# 正序循环
for i in range(5):
    print(i)
# 0 1 2 3 4 

# 逆序循环
# 方法一：
for i in range(5)[::-1]:
    print(i)
# 4 3 2 1 0

# 方法二：
for i in range(4, -1, -1):  # 注意这里是4
    print(i)
# 4 3 2 1 0

# 方法三：
for i in reversed(range(5)):
    print(i)
# 4 3 2 1 0

range() 定义步长

1
2
3

for i in range(0, 6, 2):
	print(i, end=',')
# 0,2,4

enumerate()

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中.

语法：enumerate(sequence, [start=0])

参数：

sequence – 一个序列、迭代器或其他支持迭代对象。

start – 下标起始位置。

1
2
3

seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
	print i, element

help()

用于查看函数或者模块用途的详细说明

dir()

dir() 函数不带参数时，返回当前范围内的变量、方法和定义的类型列表；带参数时，返回参数的属性、方法列表。如果参数包含方法__dir__()，该方法将被调用。如果参数不包含 __dir__()，该方法将最大限度地收集参数信息。

type()

只有第一个参数则返回对象的类型，三个参数返回新的类型对象

语法：

1
2
3

> type(object)
> type(name, bases, dict)
>

参数：

> name  -- 类的名称。
> bases -- 基类的元组。
> dict  -- 字典，类内定义的命名空间变量。
>

# 一个参数实例
type(1)
<type 'int'>

# 三个参数
class X(object):
   a = 1
X = type('X', (object,), dict(a=1))  # 产生一个新的类型 X
print(X)
<class '__main__.X'>

sort() 和 sorted() 区别

sort 是应用在 list 上的方法，属于列表的成员方法，sorted 可以对所有可迭代的对象进行排序操作。
list 的 sort 方法返回的是对已经存在的列表进行操作，而内建函数 sorted 方法返回的是一个新的 list，而不是在原来的基础上进行的操作。
sort使用方法为ls.sort()，而sorted使用方法为sorted(ls)

使用一个key函数，把字符串映射为忽略大小写排序

1 2	sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower) # ['about', 'bob', 'Credit', 'Zoo']

要进行反向排序，不必改动 key 函数，可以传入第三个参数 reverse=True

1 2	sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower, reverse=True) # ['Zoo', 'Credit', 'bob', 'about']

Reference: *

random随机数/随机字符串

import random
import string

print( random.randint(1, 10) )        # 产生 1 到 10 的一个整数型随机数  
print( random.randrange(1, 100, 2) )   # 生成从1到100的间隔为2的随机整数

print( random.random() )             # 产生 0 到 1 之间的随机浮点数
print( random.uniform(1.1, 5.4) )     # 产生  1.1 到 5.4 之间的随机浮点数，区间可以不是整数

print( random.choice('tomorrow') )   # 随机字符，从序列中随机选取一个元素
print random.choice(['剪刀', '石头', '布'])  # 随机选取字符串
print random.sample('zyxwvutsrqponmlkjihgfedcba', 5) # 多个字符中生成指定数量的随机字符

items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
print random.shuffle(items)			 # 打乱排序

三元运算

不像C++，我们在Python中没有 ?:，但我们有这个：

1	[on true] if [expression] else [on false]

如果表达式为True，就执行[on true]中的语句。否则，就执行[on false]中的语句。

1
2
3

a,b = 2,3
min=a if a<b else b
print(min)  # 2

常用的Python模块

os：与操作系统相关联的函数。提供了丰富的方法来处理文件和目录。

os.remove(‘path/filename’) 删除文件
os.rename(oldname, newname) 重命名文件
os.mkdir/makedirs('dirname')创建目录/多层目录
os.rmdir/removedirs('dirname') 删除目录/多层目录
os.listdir('dirname') 列出指定目录的文件
os.getcwd() 取得当前工作目录
os.path.exists() 是否存在
os.path.isabs() 是否为绝对路径
os.path.isdir() 是否为目录
os.path.isfile() 是否为文件

sys: 通常用于命令行参数

sys.exit(n) 退出程序，正常退出时exit(0)
sys.stdin 标准输入
sys.stdout 标准输出
sys.path 返回模块的搜索路径，初始化时使用PYTHONPATH环境变量的值

time：time.time() 用于获取当前时间戳
re: 正则匹配
math: 数学运算
datetime:处理日期时间
numpy: 数据科学包

模块和包

模块：一个.py 文件就称之为一个模块（ Module）

大大提高了代码的可维护性
还可以避免函数名和变量名冲突

这个 fibonacci.py 文件就是一个模块

def fib_yield(n):
    a, b = 0, 1
    while b < n:
        yield b
        a, b = b, a+b

def fib(n):
    for num in fib_yield(n):
        print(num)

# 可以用 if __name__ == "__main__": 在模块代码中定义一些测试代码。        
if __name__ == "__main__":
    fib(10)

然后在python解释器或其他文件中 import 它

1
2
3

import fibonacci
for num in fibonacci.fib_yield(5):
    print(num)

包：按目录来组织模块的方法，成为包。即包是一个包含__init__.py 文件的目录，该目录下一定得有这个 __init__.py 文件和其它模块或子包。

通过包来组织模块，避免冲突

几种魔法方法

__init__:对象初始化方法

__new__:创建对象时候执行的方法，单列模式会用到

__str__:当使用print输出对象的时候，只要自己定义了__str__(self)方法，那么就会打印从在这个方法中return的数据

__del__:删除对象执行的方法

补充：

__new__ 和 __init__ 区别

__new__是一个静态方法,而__init__是一个实例方法.
__new__方法会返回一个创建的实例,而__init__什么都不返回.
只有在__new__返回一个cls的实例时后面的__init__才能被调用.
当创建一个新实例时调用__new__,初始化一个实例时用__init__.

单利模式

使用 new 关键字实现单例模式

_instance 用来存放实例，如果 _instance 为 None，则新建实例，否则直接返回 _instance 存放的实例。

class Single(object):

    _instance = None

    def __new__(cls, *args, **kwargs):
        if cls._instance is None:
            cls._instance = object.__new__(cls, *args, **kwargs)
        return cls._instance

    def __init__(self):
        pass

single1 = Single()
single2 = Single()
print(id(single1) == id(single2))  # id用于获取对象的内存地址
# True

装饰器版本

def singleton(cls):
    instances = {}
    def getinstance(*args, **kw):
        if cls not in instances:
            instances[cls] = cls(*args, **kw)
        return instances[cls]
    return getinstance

@singleton
class MyClass:

深拷贝和浅拷贝

直接赋值：其实就是对象的引用（别名）。
浅拷贝(copy)：拷贝父对象，不会拷贝对象的内部的子对象。
深拷贝(deepcopy)： copy 模块的 deepcopy 方法，完全拷贝了父对象及其子对象。

1、b = a: 赋值引用，a 和 b 都指向同一个对象。

2、b = a.copy(): 浅拷贝, a 和 b 是一个独立的对象，但他们的子对象还是指向统一对象（是引用）。

b = copy.deepcopy(a): 深度拷贝, a 和 b 完全拷贝了父对象及其子对象，两者是完全独立的。

如果给定一个正整数数N，对于一个最小位是2的s次幂的数，需要多少位才能表示这个数？如何确定数字系统中的参数位数。

range 和 xrange 区别

Python2.7

range ：返回一个列表 list，type是 <type ‘list’> 类型，会直接分配相应的内存空间给 list
xrange：返回一个生成器，type 是 <type ‘xrange’> 类型，在for in 循环中中，每次调用就生成一个。

Python3

Python3 中取消了 xrange 函数，此时的 range 就是 xrange 函数

range：返回一个生成器，type 是 <type ‘range’>，并没有将数据完全实例化，for 循环每次用的时候返回一个，这样可以大大节省空间，优化性能。

内建数据类型

整型–int
布尔型–bool
字符串–str
列表–list
元组–tuple
字典–dict

list 和 tuple 区别

两者的主要区别是列表是可变的，而元组是不可变的。一般元组能做到的，列表也能做到，但有两个原因是列表不能替代的：

不能将列表当做字典的key，而元组可以。
元组作为很多内建函数和方法的返回值存在。

列表、元组、集合、字典的区别

	列表	元组	集合	字典
英文	list	tuple	set	dict
可否读写	读写	只读	读写	读写
可否重复	是	是	否	是
存储方式	值	值	键(不能重复)	键值对(键不能重复)
是否有序	有序	有序	无序	无序，自动正序
初始化	`[1,'a']`	`('a', 1)`	`set([1,2])` 或 `{1,2}`	`{'a':1,'b':2}`
添加	`append`	只读	`add`	`d['key'] = 'value'`
读元素	`l[2:]`	`t[0]`	无	`d['a']`

列表元组转其他

# 列表转集合(去重)
list1 = [6, 7, 7, 8, 8, 9]
set(list1)
# {6, 7, 8, 9}

#两个列表转字典
list1 = ['key1','key2','key3']
list2 = ['1','2','3']
dict(zip(list1,list2))
# {'key1': '1', 'key2': '2', 'key3': '3'}

#嵌套列表转字典
list3 = [['key1','value1'],['key2','value2'],['key3','value3']]
dict(list3)
# {'key1': 'value1', 'key2': 'value2', 'key3': 'value3'}

# 列表、元组转字符串
list2 = ['a', 'a', 'b']
''.join(list2)
# 'aab'

tup1 = ('a', 'a', 'b')
''.join(tup1)
# 'aab'

字典转其他

# 字典转换为字符串
dic1 = {'a':1,'b':2}
str(dic1)
# "{'a': 1, 'b': 2}"

# 字典key和value互转
dic2 = {'a': 1, 'b': 2, 'c': 3}
{value:key for key, value in dic2.items()}
# {1: 'a', 2: 'b', 3: 'c'}

字符串转其他

# 字符串转列表
s = 'aabbcc'
list(s)
# ['a', 'a', 'b', 'b', 'c', 'c']

# 字符串转元组
tuple(s)
# ('a', 'a', 'b', 'b', 'c', 'c')

# 字符串转集合
set(s)
# {'a', 'b', 'c'}

# 字符串转字典
dic2 = eval("{'name':'ljq', 'age':24}")

# 切分字符串
a = 'a b c'
a.split(' ')
# ['a', 'b', 'c']

collections 模块

defaultdict

dict在使用时，当key值不存在时，直接添加value时会出现错误，使用defaultdict可以很好的规避该错误。defaultdict是对字典类型的补充，它可以给字典的值设置一个类型，当key不存在时可以自动生成相应类型的value。

# 最长无重复字符子串
def lengthOfLongestSubstringIII(self, s):
    """
    方法三：使用滑动窗口，左右指针，套用模板
    （1）使用双指针，初始化 left = right = 0, 把索引闭区间 [left, right] 称为窗口
    （2）先不断的增加right指针，扩大窗口 [left, right]，同时记录当前窗口中每个字符出现的次数，
        如果某个字符次数超过1次，则说明有重复字符，然后就需要更新left左指针，缩小窗口范围，
        直到窗口中每个字符最多只出现一次
    （3）每次更新right，我们都需要更新当前最长不重复的最长子串
    """
    from collections import defaultdict
    str_dict = defaultdict(int)     # 作为计数器，记录窗口中字符穿线次数
    left = 0
    right = 0
    max_len = 0
    counter = 0
    while right < len(s):
        if str_dict[s[right]] > 0:
            counter += 1
        str_dict[s[right]] += 1
        right += 1
        while counter > 0:
            if str_dict[s[left]] > 1:
                counter -= 1
            str_dict[s[left]] -= 1
            left += 1
        max_len = max(max_len, right - left)
    return max_len

orderedDict

在Python3.6之前的字典是无序的，但是有时候我们需要保持字典的有序性，orderDict可以在dict的基础上实现字典的有序性，这里的有序指的是按照字典key插入的顺序来排列，这样就实现了一个先进先出的dict，当容量超出限制时，先删除最早添加的key。
举例：

from collections import OrderedDict
original_dict = {'a': 2, 'b': 4, 'c': 5}
for key, value in original_dict.items():
    print(key, value)

ordered_dict = OrderedDict([('a', 2), ('b', 4), ('c', 5)])
for key, value in ordered_dict.items():
    print(key, value)
# a 2
# b 4
# c 5
# a 2
# b 4
# c 5

deque

Python中的list是基于数组实现的，所以，查找容易，但是插入和删除操作时间复杂度较大。
deque就是为了高效实现插入和删除操作的双向列表，适合用于队列和栈，而且线程安全。
list只提供了append和pop方法来从list的尾部插入或者删除元素，deque新增了appendleft/popleft等方法可以更高效的在元素的开头来插入/删除元素。(可以进行双向操作元素，十分方便)
举例：

from collections import deque
d = deque([1, 2, 3, 4, 5])
d.extendleft([0])	
print(d)			# deque([0, 1, 2, 3, 4, 5])
d.extend([6, 7])
d.popleft()
print(d)			# deque([1, 2, 3, 4, 5, 6, 7])

Counter

字典子类，为可以哈希的对象计数。可以实现对一个对象中的元素进行计数。

from collections import Counter
test_counter_data = ['cat', 'dog', 'sheep', 'cat', 'dog']
counter_data = Counter()
for item in test_counter_data:
    counter_data[item] += 1
print(counter_data)
# Counter({'cat': 2, 'dog': 2, 'sheep': 1})

namedtuple

元组子类。
我们知道，Python中元组的一个重要特征就是元素不可增删改，而查找tuple元素时一般采取索引。
使用namedtuple(typename, field_name)可以命名tuple中的元素，之后便可使用名字来查找tuple中的值，有点类似于字典中的查找。

from collections import namedtuple

animal = namedtuple('animal', 'type age')
mark = animal(type='dog', age=2)
print(mark.type)  	# dog

使用namedtuple可以提高代码的可读性和文档性。

heapq

list删除元素

使用 del 删除指定元素

li = [1, 2, 3, 4]
del li[3]
print(li)
# Output [1, 2, 3]

使用list方法 pop 删除元素

li = [1, 2, 3, 4]
li.pop(2)
print(li)
# Output [1, 2, 4]

注：指定pop参数，将会删除该位置的元素；无参数时默认删除最后一个元素

使用切片删除元素

li = [1, 2, 3, 4]
li = li[:2] + li[3:]
print(li)
# Output [1, 2, 4]

使用list方法 remove 删除指定值的元素

li = [1, 2, 3, 4]
li.remove(3)
print(li)
# Output [1, 2, 4]

注：remove方法删除指定值的元素，与其他方法不同。

创建二维数组

(1) 直接创建法

1	test = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

简单粗暴，不过太麻烦，一般不用。

(2) 列表生成式法

1	test = [[0 for i in range(m)] for j in range(n)]

(3) 使用模块numpy创建

1 2	import numpy as np test = np.zeros((m, n), dtype=np.int)

下划线命名

_xxx：私有化属性或方法，不能用from somemodule import * 导入，类对象和子类可以访问。但按照约定俗成的规定，定义成这样就表示，虽然可以访问，但还是要把其看成是私有的，不要随便访问。
__xxx：表示是一个私有成员，它无法直接像公有成员一样访问，但可以通过 对象名._类名__xxx 方式访问。
__xxx__：特殊成员，特殊成员是可以直接访问的，其不是 private 成员，例如： __init__() 、__del__() 这样的魔法函数。

Reference: 1 2

！函数参数

必选参数：必须要传入的参数。如定义一个函数 fun(x): return x，x 则为必选参数。
默认参数：一定要用不可变对象，如果是可变对象，程序运行时会有逻辑错误！ fun(x, n=2): return x * n
*args 可变参数：args 接收的是一个 tuple
**kw 是关键字参数， kw 接收的是一个 dict

调用函数时，如何传入可变参数和关键字参数语法：

可变参数既可以直接传入： func(1, 2, 3)，又可以先组装 list 或 tuple，再通过 *args 传入： func(*(1, 2, 3))
关键字参数既可以直接传入： func(a=1, b=2)，又可以先组装 dict，再通过 **kw 传入： func(**{'a': 1, 'b': 2})

命名关键字参数：命名的关键字参数是为了限制调用者可以传入的参数名，同时可以提供默认值。注意：定义命名的关键字参数在没有可变参数的情况下不要忘了写分隔符*，否则定义的将是位置参数。

定义参数顺序必须是：必选参数、默认参数、可变参数、命名关键字参数、关键字参数。

def f1(a, b, c=0, *args, **kw): # a,b必选参数、c默认参数、*args可变参数、**关键字参数
    print('a =', a, 'b =', b, 'c =', c, 'args =', args, 'kw =', kw)
    
def f2(a, b, c=0, *, age, **kw):  # a,b必选参数、c默认参数、age命名关键字参数、**kw关键字参数
	print('a =', a, 'b =', b, 'c =', c, 'age =', d, 'kw =', kw)
    
# 函数调用
f1(1, 2) 
# a = 1 b = 2 c = 0 args = () kw = {}
f1(1, 2, c=3)
# a = 1 b = 2 c = 3 args = () kw = {}
f1(1, 2, 3, 'a', 'b')
# a = 1 b = 2 c = 3 args = ('a', 'b') kw = {}
f1(1, 2, 3, 'a', 'b', x=99)
# a = 1 b = 2 c = 3 args = ('a', 'b') kw = {'x': 99}

f2(1, 2, age=99, ext=None)
# a = 1 b = 2 c = 0 age = 99 kw = {'ext': None}

# 最神奇的是通过一个 tuple 和 dict，你也可以调用上述函数
args = (1, 2, 3, 4)
kw = {'age': 99, 'x': '#'}
f1(*args, **kw)
# a = 1 b = 2 c = 3 args = (4,) kw = {'age': 99, 'x': '#'}

args = (1, 2, 3)
kw = {'age': 88, 'x': '#'}
f2(*args, **kw)
# a = 1 b = 2 c = 3 age = 88 kw = {'x': '#'}

生成器

1. 生成器：一遍循环一遍计算的机制称为生成器：generator

创建生成器

（1）只要把一个列表生成式的 [] 改成 ()

L = [x * x for x in range(10)]
g = (x * x for x in range(10))  # ①生成器
for n in g:
    print(n)

将 [] 改为 () 的生成器
带 yield 函数的生成器函数

generator 保存的是算法，每次调用 next()，就计算出 g 的下一个元素的值，遇到 yield 语句返回，再次执行时，从上次放回的 yield 语句处继续执行。一般创建了一个generator后，基本不会使用next()，而是通过for循环来迭代（Python的for循环本质上就是通过不断调用next()函数实现的）

如果直接使用next() 函数不断调用并返回下一个值，直到没有数据时抛出 StopIteration 错误。

# 原始斐波拉契数列
def fib(max):
    n, a, b = 0, 0, 1
    while n < max:
        print(b, end=' ')
        a, b = b, a + b
        n += 1
    return 'done'

# 将fib函数变为 ② 生成器函数
def fibII(max):
    n, a, b = 0, 0, 1
    while n < max:
        yield b     # 只做了这一处修改
        a, b = b, a + b
        n += 1
    return 'done'

if __name__ == '__main__':
    # 原始fib
    fib(6)
    print()

    # 生成器版fib
    for i in fibII(6):
        print(i, end=' ')

普通函数：调用直接返回结果
生成器generator函数：调用它实际返回一个generator对象

迭代器

（1）可迭代对象 Iterable

集合数据类型：list、tuple、dict、set、str
generator：生成器和带 yield 的 generator 函数

使用 isinstance() 判断一个对象是否是 Iterable 对象：

from collections import Iterable
isinstance([], Iterable) # True
isinstance({}, Iterable) # True
isinstance('abc', Iterable) # True

（2）迭代器 Iterator

可以被 next() 函数调用并不断返回下一个值的对象称为迭代器 Iterator.

可以使用 isinstance()判断一个对象是否是 Iterator 对象

from collections import Iterator
isinstance((x for x in range(10)), Iterator) # True
isinstance([], Iterator) # False
isinstance({}, Iterator) # False
isinstance('abc', Iterator) # False

生成器都是 Iterator 对象，但 list、 dict、 str 虽然是 Iterable，却不是 Iterator

把 list、 dict、 str 等 Iterable 变成 Iterator 可以使用 iter()函数：

1 2	isinstance(iter([]), Iterator) # True isinstance(iter('abc'), Iterator) # True

装饰器

装饰器本质是一个闭包函数，实现的功能是：在不修改原函数及调用方式的情况下对原函数进行功能扩展。

def wraper(func):
    def inner(*args, **kw):
        print('执行函数前扩展的内容')
        ret = func(*args, **kw)
        print('执行函数后扩展的内容')
        return ret
    return inner

@wraper
def index(name, age):
    print('我叫%s，今年%s岁' % (name, age))

index('小明', 25)

# 执行函数前扩展的内容
# 我叫小明，今年25岁
# 执行函数后扩展的内容

闭包

如果在一个内部函数里，对在外部作用域（但不是在全局作用域）的变量进行引用，那么内部函数就被认为是闭包(closure)

def outer(x):
    def inner(y):
        return x + y
    return inner

inner(y)就是这个内部函数，对在外部作用域（但不是在全局作用域）的变量进行引用：x就是被引用的变量，x在外部作用域outer里面，但不在全局作用域里，则这个内部函数inner就是一个闭包。

a = outer(2)
print('function:',a) 
print('result:',a(3))

# 输出结果
# function: <function outer.<locals>.inner at 0x7f61190e8e18>
# result: 5

这里a就是inner函数，是一个闭包。

注意：

闭包无法修改外部函数的局部变量
闭包无法直接访问外部函数的局部变量

作用：

闭包也具有提高代码可复用性的作用。

匿名函数 lambda

lambda函数省去了函数定义，不用担心函数名冲突。匿名函数也是一个函数对象，也可以把匿名函数赋值给一个变量，再利用变量来调用该函数：

1 2	list(map(lambda x: x * x, [1, 2, 3, 4, 5, 6, 7, 8, 9])) # [1, 4, 9, 16, 25, 36, 49, 64, 81]

其中匿名函数 lambda x: x * x 实际上就是：

1 2	def f(x): return x * x

type 与 isinstance 区别

相同点：都可以用来判断对象的类型

不同点：

type() 不会认为子类是一种父类类型
isinstance() 会认为子类是一种父类类型

class A:
    pass
 
class B(A):
    pass
 
isinstance(A(), A)    # True
type(A()) == A        # True

isinstance(B(), A)    # True
type(B()) == A        # False

—-Python中的继承

当一个类继承自另一个类，它就被称为一个子类/派生类，继承自父类/基类/超类。它会继承/获取所有类成员（属性和方法）。

继承能让我们重新使用代码，也能更容易的创建和维护应用。Python支持如下种类的继承：

单继承：一个类继承自单个基类
多继承：一个类继承自多个基类
多级继承：一个类继承自单个基类，后者则继承自另一个基类
分层继承：多个类继承自单个基类
混合继承：两种或多种类型继承的混合更多关于继承的内容，参见：

Python继承教程

进程 / 线程 / 协程

（1）进程：是系统资源分配和调度的一个独立单位，每个进程都有自己的内存空间，占用内存资源比较多，上下文切换开销大，比较稳定和安全。

（2）线程：【同步机制】CPU处理器调度的基本单位，进程中的一个执行单位可调度的实体，占用系统资源很少，同一个进程中的多个线程可以共享全局变量，通信主要是共享进程内存，资源开销很小，不够稳定，易丢失数据。

（3）协程：【异步机制】调度由用户控制，更加轻量级的线程，拥有自己的寄存器和上下文栈，开销小，切换上下文迅速。

GIL锁

GIL 是python的全局解释器锁，同一进程中假如有多个线程运行，一个线程在运行python程序的时候会霸占python解释器（加了一把锁即GIL），使该进程内的其他线程无法运行，等该线程运行完后其他线程才能运行。如果线程运行过程中遇到耗时操作，则解释器锁解开，使其他线程运行。所以在多线程中，线程的运行仍是有先后顺序的，并不是同时进行。

多进程中因为每个进程都能被系统分配资源，相当于每个进程有了一个python解释器，所以多进程可以实现多个进程的同时运行，缺点是进程系统资源开销大

内存管理

Python有一个私有堆空间来保存所有的对象和数据结构。作为开发者，我们无法访问它，是解释器在管理它。但是有了核心API后，我们可以访问一些工具。Python内存管理器控制内存分配。

另外，内置垃圾回收器会回收使用所有的未使用内存，所以使其适用于堆空间。

引用计数机制

python垃圾回收主要以引用计数为主，标记-清除和分代清除为辅的机制，其中标记-清除和分代回收主要是为了处理循环引用的难题。

1. 引用计数

当有1个变量保存了对象的引用时，此对象的引用计数就会加1。当使用del删除变量指向的对象时，引用计数就会减1，当引用计数为0时，此时会真的把对象进行删除。

优点:

简单
实时性

缺点:

维护引用计数消耗资源
循环引用

Python GC主要使用引用计数（reference counting）来跟踪和回收垃圾。在引用计数的基础上，通过“标记-清除”（mark and sweep）解决容器对象可能产生的循环引用问题，通过“分代回收”（generation collection）以空间换时间的方法提高垃圾回收效率。

2. 标记-清除机制

基本思路是先按需分配，等到没有空闲内存的时候从寄存器和程序栈上的引用出发，遍历以对象为节点、以引用为边构成的图，把所有可以访问到的对象打上标记，然后清扫一遍内存空间，把所有没标记的对象释放。

3. 分代技术

分代回收的整体思想是：将系统中的所有内存块根据其存活时间划分为不同的集合，每个集合就成为一个“代”，垃圾收集频率随着“代”的存活时间的增大而减小，存活时间通常利用经过几次垃圾回收来度量。

Python默认定义了三代对象集合，索引数越大，对象存活时间越长。

举例：当某些内存块M经过了3次垃圾收集的清洗之后还存活时，我们就将内存块M划到一个集合A中去，而新分配的内存都划分到集合B中去。当垃圾收集开始工作时，大多数情况都只对集合B进行垃圾回收，而对集合A进行垃圾回收要隔相当长一段时间后才进行，这就使得垃圾收集机制需要处理的内存少了，效率自然就提高了。在这个过程中，集合B中的某些内存块由于存活时间长而会被转移到集合A中，当然，集合A中实际上也存在一些垃圾，这些垃圾的回收会因为这种分代的机制而被延迟。

当退出Python时，是否释放全部内存？

答案是No。循环引用其它对象或引用自全局命名空间的对象的模块，在Python退出时并非完全释放。另外，也不会释放C库保留的内存部分。

Flask

Flask是Python编写的一款轻量级Web应用框架。其 WSGI 工具箱采用 Werkzeug ，模板引擎则使用 Jinja2。Flask使用 BSD 授权。其中两个环境依赖是Werkzeug和jinja2，这意味着它不需要依赖外部库。正因如此，我们将其称为轻量级框架。

Flask会话使用签名cookie让用户查看和修改会话内容。它会记录从一个请求到另一个请求的信息。不过，要想修改会话，用户必须有密钥Flask.secret_key。

文件操作

# 读文件
# r: 只读方式打开文件
# rb：二进制格式打开文件只读
# r+: 打开文件用于读写，不存在则会创建该文件。文件指针在文件的开头
# rb+: 以二进制格式打开文件用于读写，不存在则会创建该文件。文件指针在文件的开头
f = open('./file.txt', 'r')
print(f.read())
f.close()

# 写文件
# w : 打开文件，只写（覆盖写）
# wb：以二进制格式打开文件，只写（覆盖）
# w+: 打开文件用于读写（覆盖写），不存在则会创建该文件
# wb+: 以二进制格式打开文件，读写（覆盖写），不存在则会创建该文件
f = open('./file.txt', 'w+')
f.write('Hello, world!')
f.close()

# a: 打开文件并再文件末尾追加，文件不存在则创建新的文件
# ab: 二进制方式打开文件并在末尾追加
# a+： 打开文件用于读写，追加
# ab+: 以二进制格式打开文件并在末尾追加
f = open('./file.txt', 'a+')
f.write('你好')   # 写入字符串
f.close()

# 以上都没有做异常处理，由于文件读写时，会产生IOError，以上一旦出错，后面的f.close()就不会调用。
# 所以我们为了要保证文件正确地关闭，可以使用try...finally来实现
try:
    f = open('./file.txt', 'r')
    print(f.read())
    finally:
        if f:
            f.close()

            # 每次都这样写比较繁琐，Python引入了with语句来自动帮我们调用close()方法
            with open('./file.txt', 'r') as f:
                # print(f.read())         # read()        读取文件所有内容
                # print(f.readline())     # readline()    读取一行内容
                print(f.read(5))        # read(size)    读取5个字节的字符串

如何自己实现迭代器
Python的内存回收机制
使用迭代器遍历和非迭代器遍历的区别

计算机网络

TCP 和 UDP 的特点

用户数据报协议 UDP（User Datagram Protocol）是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信。
传输控制协议 TCP（Transmission Control Protocol）是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块），每一条 TCP 连接只能是点对点的（一对一）。

TCP 的三次握手

假设 A 为客户端，B 为服务器端。

首先 B 处于 LISTEN（监听）状态，等待客户的连接请求。
A 向 B 发送连接请求报文，SYN=1，ACK=0，选择一个初始的序号 x。
B 收到连接请求报文，如果同意建立连接，则向 A 发送连接确认报文，SYN=1，ACK=1，确认号为 x+1，同时也选择一个初始的序号 y。
A 收到 B 的连接确认报文后，还要向 B 发出确认，确认号为 y+1，序号为 x+1。
B 收到 A 的确认后，连接建立。

三次握手的原因

第三次握手是为了防止失效的连接请求到达服务器，让服务器错误打开连接。

客户端发送的连接请求如果在网络中滞留，那么就会隔很长一段时间才能收到服务器端发回的连接确认。客户端等待一个超时重传时间之后，就会重新请求连接。但是这个滞留的连接请求最后还是会到达服务器，如果不进行三次握手，那么服务器就会打开两个连接。如果有第三次握手，客户端会忽略服务器之后发送的对滞留连接请求的连接确认，不进行第三次握手，因此就不会再次打开连接。

TCP 的四次挥手

以下描述不讨论序号和确认号，因为序号和确认号的规则比较简单。并且不讨论 ACK，因为 ACK 在连接建立之后都为 1。

A 发送连接释放报文，FIN=1。
B 收到之后发出确认，此时 TCP 属于半关闭状态，B 能向 A 发送数据但是 A 不能向 B 发送数据。
当 B 不再需要连接时，发送连接释放报文，FIN=1。
A 收到后发出确认，进入 TIME-WAIT 状态，等待 2 MSL（最大报文存活时间）后释放连接。
B 收到 A 的确认后释放连接。

四次挥手的原因

客户端发送了 FIN 连接释放报文之后，服务器收到了这个报文，就进入了 CLOSE-WAIT 状态。这个状态是为了让服务器端发送还未传送完毕的数据，传送完毕之后，服务器会发送 FIN 连接释放报文。

TIME_WAIT

客户端接收到服务器端的 FIN 报文后进入此状态，此时并不是直接进入 CLOSED 状态，还需要等待一个时间计时器设置的时间 2MSL。这么做有两个理由：

确保最后一个确认报文能够到达。如果 B 没收到 A 发送来的确认报文，那么就会重新发送连接释放请求报文，A 等待一段时间就是为了处理这种情况的发生。
等待一段时间是为了让本连接持续时间内所产生的所有报文都从网络中消失，使得下一个新的连接不会出现旧的连接请求报文。

Linux

常用命令

常用Linux命令	作用
cd	进入目录
cp	拷贝文件
mv	移动文件
rm	删除文件
ls	查看文件
ls -l -a	查看文件目录详情
tree -L 2	以树形结构查看目录
grep -n -H -R	递归查找包含某一条语句的文件，并显示行号
find / -name test	查找 / 目录下名为test的文件
locate test	查找和 test 相关的文件
cat	查看文本文件内容
chown	改变文件的所有者
chmod	改变文件的权限
mkdir	新建文件夹
`ls -l \| grep '^-' \| wc -l`	统计某文件夹下文件的个数
`ls -l \| grep '^d' \| wc -l`	统计某文件夹下目录的个数
`ls -lR \| grep '^d' \| wc -l`	统计文件夹下文件的个数，包括子文件夹里的
jobs -l	查看后台进程
bg %1	将后台进程1切换到当前运行
kill %1	杀死进程好为1的进程
top	显示系统中各个进程的资源占用状况
df	查看磁盘空间
df -hl	查看磁盘剩余空间

gbd

命令	解释	示例
file <文件名>	加载被调试的可执行程序文件。因为一般都在被调试程序所在目录下执行GDB，因而文本名不需要带路径。	(gdb) file gdb-sample
r	Run的简写，运行被调试的程序。如果此前没有下过断点，则执行完整个程序；如果有断点，则程序暂停在第一个可用断点处。	(gdb) r
c	Continue的简写，继续执行被调试程序，直至下一个断点或程序结束。	(gdb) c
b <行号>b <函数名称>b <函数名称>b <代码地址> d [编号]	b: Breakpoint的简写，设置断点。两可以使用“行号”“函数名称”“执行地址”等方式指定断点位置。其中在函数名称前面加“”符号表示将断点设置在“由编译器生成的prolog代码处”。如果不了解汇编，可以不予理会此用法。 d: Delete breakpoint的简写，删除指定编号的某个断点，或删除所有断点。断点编号从1开始递增。 \| (gdb) b 8(gdb) b main(gdb) b main(gdb) b *0x804835c (gdb) d \| \| s, n \| s: 执行一行源程序代码，如果此行代码中有函数调用，则进入该函数；n: 执行一行源程序代码，此行代码中的函数调用也一并执行。 s 相当于其它调试器中的“Step Into (单步跟踪进入)”；n 相当于其它调试器中的“Step Over (单步跟踪)”。这两个命令必须在有源代码调试信息的情况下才可以使用（GCC编译时使用“-g”参数）。 \| (gdb) s(gdb) n \| \| si, ni \| si命令类似于s命令，ni命令类似于n命令。所不同的是，这两个命令（si/ni）所针对的是汇编指令，而s/n针对的是源代码。 \| (gdb) si(gdb) ni \| \| p <变量名称> \| Print的简写，显示指定变量（临时变量或全局变量）的值。 \| (gdb) p i(gdb) p nGlobalVar \| \| display … undisplay <编号> \| display，设置程序中断后欲显示的数据及其格式。例如，如果希望每次程序中断后可以看到即将被执行的下一条汇编指令，可以使用命令“display /i $pc”其中 $pc 代表当前汇编指令，/i 表示以十六进行显示。当需要关心汇编代码时，此命令相当有用。 undispaly，取消先前的display设置，编号从1开始递增。 \| (gdb) display /i $pc (gdb) undisplay 1 \| \| i \| info的简写，用于显示各类信息，详情请查阅“help i”。 \| (gdb) i r \| \| q \| Quit的简写，退出GDB调试环境。 \| (gdb) q \| \| help [命令名称] \| GDB帮助命令，提供对GDB名种命令的解释说明。如果指定了“命令名称”参数，则显示该命令的详细说明；如果没有指定参数，则分类显示所有GDB命令，供用户进一步浏览和查询。 \| \|

Reference：gdb入门

Git