排序
时间复杂度指平均时间。空间复杂度指辅助空间。稳定性指相同相邻数字是否会改变前后顺序，改变则不稳定。
常用的：直接插入、冒泡、快速、直接选择、堆。
不稳定：快速、选择、堆（希尔）。（其他都稳定）
时间复杂度：（n方）插入、冒泡、选择；（n乘logn）快速、堆
空间复杂度：（lgn）快速；其他（1）
（口令：快速选择堆，不稳！快堆， nlogn！快，空logn！）
直接插入排序：第一个数放入新数组，第二个到第n个依次插入新数组，每次都要找到他的大小位置。
冒泡排序：一个贴一个比较大小，大小顺序不对则互换。
快速排序：选第一个数，后面比他大放一个数组，比他小放一个数组。再继续这样快速排序这两个数组。
直接选择排序：遍历第一趟选最小的放在新数组第一个，第二趟选第二小的放第二个。。。
堆排序：把数组写成二叉树（大顶堆或小顶堆），然后把最上面根节点与最下最右子节点交换，再重新调整堆（不动最下最右节点，调成大顶堆或小顶堆），再交换最上面与倒二节点。以此类推。
先序：根左右；中序：左根右；后序：左右根
位运算&
它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理），数值改成二进制，两个对应位置是1才是1，否则是0
B：A
B继承A，A a=new B();若B重载了A的方法，a调用B中的方法，若没有，则调用A的方法。重载需要函数类型也一致(如A是虚函数，而B是new的普通函数，则不算重载，依然调用A。用override可以覆盖父类方法。（只能调用A的方法以及B中重写的A的方法，如用字段override覆盖（代替new）的方法）
C#中值类型与引用类型
|
值类型： |
byte，short，int，long，float，double，decimal，char，bool 和 struct 统称为值类型。 |
|
引用类型： |
string 和 class统称为引用类型。 |
Class与结构体的区别
最本质的一个区别就是默认的访问控制：
默认的继承方式（以子类是class还是struct决定）以及默认的成员访问权限
struct是public的，class是private的。
用struct定义的类中不包含成员访问限定符public、protected和private
C与C++区别
1.C是面向过程的语言，而C++是面向对象的语言
2.C和C++动态管理内存的方法不一样，C是使用malloc/free函数，而C++除此之外还有new/delete关键字
3.C++的类是C所没有的，但是C中的struct是可以在C++中正常使用的，并且C++对struct进行了进一步的扩展，使struct在C++中可以和class一样当做类使用，而唯一和class不同的地方在于struct的成员默认访问修饰符是public,而class默认的是private;
4. C++支持函数重载（条件：参数个数不同，或者参数类型不同），而C不支持函数重载
5. C++中有引用，而C没有
6.C 中用const修饰的变量不可以用在定义数组时的大小，但是C++用const修饰的变量可以
7. 局部变量的声明规则不同，多态，C++特有输入输出流之类的
#define和const的区别
1.const 定义的常数是变量 也带类型， #define 定义的只是个常数 不带类型
2.define是在编译的预处理阶段起作用，而const是在 编译、运行的时候起作用。
3.define只是简单的字符串替换，没有类型检查。而const有对应的数据类型，是要进行判断的，可以避免一些低级的错误。
4. const常量可以进行调试的，define是不能进行调试的，因为在预编译阶段就已经替换掉了
5. const不足的地方， const不能重定义，而#define可以通过#undef取消某个符号的定义，再重新定义。
static与const区别
Static：
static局部变量 将一个变量声明为函数的局部变量，那么这个局部变量在函数执行完成之后不会被释放，而是继续保留在内存中
static 全局变量 表示一个变量在当前文件的全局内可访问
static 函数 表示一个函数只能在当前文件中被访问
static 类成员变量 表示这个成员为全类所共有
static 类成员函数 表示这个函数为全类所共有，而且只能访问静态成员变量
const：
const 常量：定义时就初始化，以后不能更改。
const 形参：func(const int a){};该形参在函数里不能改变
const修饰类成员函数：该函数对成员变量只能进行只读操作
静态全局变量与全局变量区别
静态变量（Static Variable）在计算机编程领域指在程序执行前系统就为之静态分配（也即在运行时中不再改变分配情况）存储空间的一类变量。与之相对应的是在运行时只暂时存在的自动变量（即局部变量）与以动态分配方式获取存储空间的一些对象，其中自动变量的存储空间在调用栈上分配与释放。
在全局变量前加一个 static，使该变量只在这个源文件中可用，称之为全局静态变量，全局静态变量就是静态全局变量。
static 限制了变量的作用域只在该文件里，所以加上static在别的文件中定义一个相同的static没有问题。而没有static修饰的全局变量，要是在不同文件中定义了相同的变量名，程序会报错。
在一个cpp里开头声明全局变量，如int globe；在另一个cpp里写extern int globe；就可以调用这个全局变量。
静态变量与变量
静态局部变量是一种生存期为整个源程序的量。虽然离开定义它的函数后不能使用，但如再次调用定义它的函数时，它又可继续使用， 而且保存了上次被调用后留下的值。 因此，当多次调用一个函数且要求在调用之间保留某些变量的值时，可考虑采用静态局部变量。虽然用全局变量也可以达到上述目的，但全局变量有时会造成意外的副作用，因此仍以采用局部静态变量为宜。
Vector与list区别
1.vector数据结构
vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。
因此能高效地进行随机存取，时间复杂度为o(1);
但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。
另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。
2.list数据结构
list是由双向链表实现的，因此内存空间是不连续的。
只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);
但由于链表的特点，能高效地进行插入和删除。
（1）vector为存储的对象分配一块连续的地址空间，随机访问效率很高。但是插入和删除需要移动大量的数据，效率较低。尤其当vector中存储的对象较大，或者构造函数复杂，则在对现有的元素进行拷贝的时候会执行拷贝构造函数。
（2）list中的对象是离散的，随机访问需要遍历整个链表，访问效率比vector低。但是在list中插入元素，尤其在首尾插入，效率很高，只需要改变元素的指针。
（3）vector是单向的，而list是双向的；
（4）向量中的iterator在使用后就释放了，但是链表list不同，它的迭代器在使用后还可以继续用；链表特有的；
深拷贝，浅拷贝
浅拷贝是将原始对象中的数据型字段拷贝到新对象中去，将引用型字段的“引用”复制到新对象中去，不把“引用的对象”复制进去，所以原始对象和新对象引用同一对象，新对象中的引用型字段发生变化会导致原始对象中的对应字段也发生变化。
深拷贝是在引用方面不同，深拷贝就是创建一个新的和原始字段的内容相同的字段，是两个一样大的数据段，所以两者的引用是不同的，之后的新对象中的引用型字段发生改变，不会引起原始对象中的字段发生改变。
public，protected和private区别
public：可以被其他的类来调用，也可以被自己类里的函数来调用。
protected：这个函数可以被继承类调用，也可以被自己类里的函数调用，但不能被其他的类调用。
private：具有更少的权限了，只能被自己类里的其他函数调用，其他的一概不能调用。
类继承规则：（public继承、protected继承、private继承）
1、public继承不改变基类成员的访问权限
2、private继承使得基类所有成员在子类中的访问权限变为private
3、protected继承将基类中public成员变为子类的protected成员，其它成员的访问 权限不变。
4、基类中的private成员不受继承方式的影响，子类永远无权访问(使用using也不行)。
简而言之就是除基类private成员外，其他成员取类继承类型与基类成员访问权限的最低权限。(public>protected>private)
而基类的private成员永远不能被子类访问，不受继承类型影响。
派生类的构造函数和析构函数的执行顺序
首先执行基类的构造函数，随后执行派生类的构造函数，当撤销派生类对象时，先执行派生类的析构函数，再执行基类的析构函数。
派生类不能继承基类中的构造函数和析构函数。
当基类含有带参数的构造函数时，派生类必须定义构造函数，以提供把参数传递给基类构造函数的途径。
类成员初始化顺序
成员变量在使用初始化列表初始化时，与构造函数中初始化成员列表的顺序无关，只与定义成员变量的顺序有关。因为成员变量的初始化次序是根据变量在内存中次序有关，而内存中的排列顺序早在编译期就根据变量的定义次序决定了。
注意：类成员在定义时，是不能初始化的
注意：类中const成员常量必须在构造函数初始化列表中初始化。
注意：类中static成员变量，必须在类外初始化。
静态变量进行初始化顺序是基类的静态变量先初始化，然后是它的派生类。直到所有的静态变量都被初始化。这里需要注意全局变量和静态变量的初始化是不分次序的。这也不难理解，其实静态变量和全局变量都被放在公共内存区。可以把静态变量理解为带有“作用域”的全局变量。在一切初始化工作结束后，main函数会被调用，如果某个类的构造函数被执行，那么首先基类的成员变量会被初始化。
内存分配区域
程序的内存分配：
一个由C/C++编译的程序占用的内存分为以下几个部分：
1、栈区（stack）— 由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS（操作系统）回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
4、文字常量区 —常量字符串就是放在这里的。程序结束后由系统释放。
5、程序代码区—存放函数体的二进制代码。
（结构体里函数在程序代码区，不占内存，但虚函数占4字节，因为虚函数指针占空间）
new和malloc的区别
a.属性
new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持c。
b.参数
使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算。而malloc则需要显式地指出所需内存的尺寸。
c.返回类型
new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型。
e. 分配失败
new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。
f.自定义类型
new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。
malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作。
g.重载
C++允许重载new/delete操作符，特别的，布局new的就不需要为对象分配内存，而是指定了一个地址作为内存起始区域，new在这段内存上为对象调用构造函数完成初始化工作，并返回此地址。而malloc不允许重载。
h.内存区域
new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。自由存储区不等于堆，如上所述，布局new就可以不位于堆中。
进程与线程的关系
进程和线程的关系
（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程是操作系统可识别的最小执行和调度单位。
（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。 同一进程中的多个线程共享代码段(代码和常量)，数据段(全局变量和静态变量)，扩展段(堆存储)。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。
（3）处理机分给线程，即真正在处理机上运行的是线程。
（4）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。
进程管理了一堆资源，并且每个进程还拥有独立的虚拟内存地址空间，会真正地拥有独立与父进程之外的物理内存。并且由于进程拥有独立的内存地址空间，导致了进程之间无法利用直接的内存映射进行进程间通信。
并发的本质是在时间上重叠的多个逻辑流，也就是说同时运行的多个逻辑流。并发编程要解决的一个很重要的问题就是对资源的并发访问的问题，也就是共享资源的问题。而两个进程恰恰很难在逻辑上表示共享资源。
线程解决的最大问题就是它可以很简单地表示共享资源的问题，这里说的资源指的是存储器资源，资源最后都会加载到物理内存，一个进程的所有线程都是共享这个进程的同一个虚拟地址空间的，也就是说从线程的角度来说，它们看到的物理资源都是一样的，这样就可以通过共享变量的方式来表示共享资源，也就是通过直接共享内存的方式解决了线程通信的问题。
线程，在网络或多用户环境下，一个服务器通常需要接收大量且不确定数量用户的并发请求，为每一个请求都创建一个进程显然是行不通的，——无论是从系统资源开销方面或是响应用户请求的效率方面来看。因此，操作系统中线程的概念便被引进了。
进程与线程的区别
我们从调度，并发性，系统开销，拥有资源等方面来比较线程与进程
1.调度
在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而把进程作为资源拥有的基本单位，在同一个 进程中，线程的切换不会引起进程的切换，在由一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换
2.并发性
在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间，奕可并发执行，因而使操作系统具有更好的并发性，从而能够有效的使用系统资源和提高系统吞吐量
3.拥有资源
进程是拥有资源的一个独立单位。一般地说，线程自己不拥有系统资源（一个线程必不可少的资源：线程标识符，程序计数器，一组寄存器的值，和堆栈），但是它可以访问其隶属于进程的资源：代码段，数据段，以打开的文件，I/O设备等
4.系统开销
由于在创建或撤销进程时，系统都要为之分配或回收资源，如内存空间，i/o设备等。在进行进程切换时，涉及到整个当前进程CPU环境的保存以及新被调用运行的进程的CPU环境的设置。而线程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表、顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
死锁
死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
产生死锁的条件
产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。
互斥条件：进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。
三种用于避免死锁的技术
加锁顺序（线程按照一定的顺序加锁）
加锁时限（线程尝试获取锁的时候加上一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁）
死锁检测（每当一个线程获得了锁，会在线程和锁相关的数据结构中（map、graph等等）将其记下。除此之外，每当有线程请求锁，也需要记录在这个数据结构中。
当一个线程请求锁失败时，这个线程可以遍历锁的关系图看看是否有死锁发生。）
Linux基本命令
CentOS
1.ls命令：
格式：：ls [选项] [目录或文件]
功能：对于目录，列出该目录下的所有子目录与文件；对于文件，列出文件名以及其他信息。
2.cd命令
格式：cd [目录名称]
常用选项：
cd .. 返回上一级目录。
cd ../.. 将当前目录向上移动两级。
cd - 返回最近访问目录。
3.pwd命令
格式： pwd
功能：显示出当前工作目录的绝对路径。
5.mkdir命令
格式：mkdir [选项] dirname…
功能：mkdir命令用来创建目录。
6.rm命令
格式：rm [选项] 文件列表
功能：rm命令删除文件或目录。
7.rmdir命令
格式：rmdir [选项] dirname
功能：删除目录。
9.cp命令
格式：cp [选项] 源文件或目录 目标文件或目录
功能：复制文件或目录。
10.mv命令
格式：mv [选项] 源文件或目录 目标文件或目录
功能：mv命令对文件或目录重新命名，或者将文件从一个目录移到另一个目录中。
继承的优缺点：
优点
新的实现很容易，因为大部分是继承而来的
很容易修改和扩展已有的实现
缺点
打破了封装，因为基类向子类暴露了实现细节
白盒重用，因为基类的内部细节通常对子类是可见的
当父类的实现改变时可能要相应的对子类做出改变
不能在运行时改变由父类继承来的实现
一个结构体有三个成员，分别是char、int、short类型，整个结构体的大小可能？
根据内存对齐原则：
1. char int short char1 + 空3 + int4 + short2 + 空2 = 12
2. char short int char1 + 空1 + short2 + int4 = 8
3. int short char int4 + short2 + char1 + 空1 = 8
4. int char short int4 + char1 + 空1 + short2 = 8
5. short int char short2 + 空2 + int4 + char1 + 空3 = 12
6. short char int short2 + char1 + 空1 + int4 = 8
静态库与动态库的区别
静态库在程序编译时会被连接到目标代码中，程序运行时将不再需要该静态库。
动态库在程序编译时并不会被连接到目标代码中，而是在程序运行是才被载入，因此在程序运行时还需要动态库存在。
库从本质上来说是一种可执行代码的二进制格式，可以被载入内存中执行。库分静态库和动态库两种。
1. 静态函数库
这类库的名字一般是libxxx.a；利用静态函数库编译成的文件比较大，因为整个 函数库的所有数据都会被整合进目标代码中，他的优点就显而易见了，即编译后的执行程序不需要外部的函数库支持，因为所有使用的函数都已经被编译进去了。当然这也会成为他的缺点，因为如果静态函数库改变了，那么你的程序必须重新编译。
2. 动态函数库
这类库的名字一般是libxxx.so;相对于静态函数库，动态函数库在编译的时候 并没有被编译进目标代码中，你的程序执行到相关函数时才调用该函数库里的相应函数，因此动态函数库所产生的可执行文件比较小。由于函数库没有被整合进你的程序，而是程序运行时动态的申请并调用，所以程序的运行环境中必须提供相应的库。动态函数库的改变并不影响你的程序，所以动态函数库的升级比较方便。
TCP与UDP区别
1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接
2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付
Tcp通过校验和，重传控制，序号标识，滑动窗口、确认应答实现可靠传输。如丢包时的重发控制，还可以对次序乱掉的分包进行顺序控制。
3、UDP具有较好的实时性，工作效率比TCP高，适用于对高速传输和实时性有较高的通信或广播通信。
4.每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信
5、TCP对系统资源要求较多，UDP对系统资源要求较少。
虚函数
C++中的虚函数的作用主要是实现了多态的机制。关于多态，简而言之就是用父类型的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”。
虚函数使同一个基类指针，可以调用同一类族中不同类的虚函数。这就是多态性，对同一消息，不同对象有 不同的响应方式。
如果不用虚函数，就要重新声明一个子类指针，需重新命名，很不方便。（若有多个子类，就要重声明多个子类指针，都需要赋予不同的命名，极其复杂）
虚函数的以上功能是很有实用意义的。在面向对象的程序设计中，经常会用到类的继承，目的是保留基类的特性，以减少新类开发的时间。但是，从基类继承来的某些成员函数不完全适应派生类的需要。
在基类用virtual声明成员函数为虚函数。C++规定，当一个成员函数被声明为虚函数后，其派生类中的同名函数都自动成为虚函数。因此在派生类重新声明该虚函数时，可以加virtual，也可以不加，但习惯上一般在每一层声明该函数时都加virtual，使程序更加清晰。如果在派生类中没有对基类的虚函数重新定义，则派生类简单地继承其直接基类的虚函数。
重载、重写与重定义
重载：同一个类里定义两个同名函数（但参数不同）
重写：调用虚函数（多态），也叫覆盖。用父类型的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。重写是子类与父类之间；不能是static；函数三要素（函数名、函数参数、函数返回类型）完全一样。
重定义：子类重新定义父类中有相同名称的非虚函数，则子类无法调用父类该同名函数。
指针和引用的区别
1.指针和引用的定义和性质区别：
（1）指针：指针是一个变量，只不过这个变量存储的是一个地址，指向内存的一个存储单元；而引用跟原来的变量实质上是同一个东西，只不过是原变量的一个别名而已。如：
int a=1;int *p=&a;
int a=1;int &b=a;
上面定义了一个整形变量和一个指针变量p，该指针变量指向a的存储单元，即p的值是a存储单元的地址。
西，在内存占有同一个存储单元。
(2)引用不可以为空，当被创建的时候，必须初始化，而指针可以是空值，可以在任何时候被初始化。
(3)可以有const指针，但是没有const引用；
(4)指针可以有多级，但是引用只能是一级（int **p；合法 而 int &&a是不合法的）
(5)指针的值可以为空，但是引用的值不能为NULL，并且引用在定义的时候必须初始化；
(6)指针的值在初始化后可以改变，即指向其它的存储单元，而引用在进行初始化后就不会再改变了。
(7)”sizeof引用”得到的是所指向的变量(对象)的大小，而”sizeof指针”得到的是指针本身的大小；
(8)指针和引用的自增(++)运算意义不一样；
(9)如果返回动态内存分配的对象或者内存，必须使用指针，引用可能引起内存泄漏；
STL
标准模板库，在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>。
STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。
1：关联容器和顺序容器
c++中有两种类型的容器：顺序容器和关联容器，顺序容器主要有：vector、list、deque等。其中vector表示一段连续的内存地址，基于数组的实现，list表示非连续的内存，基于链表实现。deque与vector类似，但是对于首元素提供删除和插入的双向支持。关联容器主要有map和set。map是key-value形式的，set是单值。map和set只能存放唯一的key值，multimap和multiset可以存放多个相同的key值。
容器类自动申请和释放内存，我们无需new和delete操作。
堆、栈、队列（数据结构）
堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
·堆中某个节点的值总是不大于或不小于其父节点的值；
·堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
①栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
②栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来（先进后出）
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 [1]
链表反转代码
struct linka {
int data;
linka* next;
};//链表元素的结构体
void reverse(linka*& head)
{
if(head ==NULL)
return;
linka*pre, *cur, *ne;
pre=head;
cur=head->next;
while(cur)
{
ne = cur->next;
cur->next = pre;
pre = cur;
cur = ne;
}
head->next = NULL;
head = pre;
}
基本数据类型所占内存
类型 字节
char 1
short int 2
int 2(TC-16位)/4(VC-32位)
long 4
float 4
double 8
long long 8
long double 10
无符号数据类型与有符号数据类型所占内存均相同。
无符号数据类型指没有负数，在正数领域数据范围大一倍。比如16位系统中一个int能存储的数据的范围为-32768~32767，而unsigned能存储的数据范围则是0~65535。在一些不可能取值为负数的时候，可以定义为unsigned
内存对齐原则
struct/class以及union内存对齐四个原则：
1、数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小（只要该成员有子成员，比如说是数组，结构体等）的整数倍开始(比如int在３２位机为４字节, 则要从４的整数倍地址开始存储),基本类型不包括struct/class/uinon。
2、结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部"最宽基本类型成员"的整数倍地址开始存储.(struct a里存有struct b,b里有char,int ,double等元素,那b应该从8的整数倍开始存储.)。
3、收尾工作:结构体的总大小,也就是sizeof的结果,.必须是其内部最大成员的"最宽基本类型成员"的整数倍.不足的要补齐.(基本类型不包括struct/class/uinon)。
4、sizeof(union)，以结构里面size最大元素为union的size,因为在某一时刻，union只有一个成员真正存储于该地址。
Union(联合体类型)
所占内存为union中最大的数据类型所占内存，定义union类型可以节省内存空间。（里面所有数据类型共用一段内存）
1：同一个内存段可以用来存放几种不同类型的数据成员，但在每一个瞬间只能存放其中一个成员，而不是同时存放几个，这和结构体struct不同。
2：可以对联合体变量初始化，但初始化表中只能有一个常量。
3：联合体变量起作用的成员是最后一次被赋值的成员，在对联合体变量中的一个成员赋值后，原有变量存储单元中的值就被取代。
4：联合体变量的地址和它的各成员的地址是同一地址。
5：不能对联合体变量名赋值，也不能前途引用变量名来取得到一个值。
sizeof与strlen的区别
sizeof判断数据所占空间.
strlen一个个读数据直到遇到’ ’结尾（不计算 ）. 指字符的长度
extern “C”
extern "C"的主要作用就是为了能够正确实现C++代码调用其他C语言代码。加上extern "C"后，会指示编译器这部分代码按C语言的进行编译，而不是C++的。
string库里一些方法的具体实现代码
1.手写strcpy（把src复制到dst中，并覆盖）
char* strcpy1(char *strDest, const char* strSrc)
{
assert(strSrc != NULL );//判断是否为空，空则报错
assert(strDest != NULL);
int i;
char *address = strDest;
for(i = 0; strSrc[i] != ' '; i++)
strDest[i] = strSrc[i];
strDest[i] = ' ';
return address;
}
2.手写memcpy函数（由src所指内存区域复制count个字节到dest所指内存区域）
void *memcpy1(void *str1, const void *str2, size_t count)
{
if (str1 == NULL || str2 == NULL)
{
return NULL;
}
char *tmp1 = (char*)str1;
const char *tmp2 = (const char*)str2;
while (count--)
{
*tmp1 = *tmp2;
tmp1++;
tmp2++;
}
return str1;
} 3.手写strcat函数（连接字符串，把src加到dst末尾）
char* strcat1(char* str1, const char* str2)
{
char *pt = str1;
while(*str1!=' ') str1++;
while(*str2!=' ') *str1++ = *str2++;
*str1 = ' ';
return pt;
}
4.手写strcmp函数（比较两个字符串是否相同，相同返回0，str1小于2返回负数，大于返回正数）
int strcmp1(const char* str1, const char* str2)
{
while(*str1 == *str2 && *str1 != ' ')
{
str1++;
str2++;
}
return *str1 - *str2;
}
构造函数不能虚函数，基类析构函数必须虚函数
1.虚函数对应一个vtable，这大家都知道，可是这个vtable其实是存储在对象的内存空间的。问题出来了，如果构造函数是虚的，就需要通过 vtable来调用，可是对象还没有实例化，也就是内存空间还没有，无法找到vtable，所以构造函数不能是虚函数
2. 用对象指针来调用一个函数，有以下两种情况：
如果是虚函数，会调用派生类中的版本。
如果是非虚函数，会调用指针所指类型的实现版本。
析构函数也会遵循以上两种情况，因为析构函数也是函数嘛，不要把它看得太特殊。 当对象出了作用域或是我们删除对象指针，析构函数就会被调用。
当派生类对象出了作用域，派生类的析构函数会先调用，然后再调用它父类的析构函数， 这样能保证分配给对象的内存得到正确释放。
但是，如果我们删除一个指向派生类对象的基类指针，而基类析构函数又是非虚的话， 那么就会先调用基类的析构函数(上面第2种情况)，派生类的析构函数得不到调用。
对于在函数中定义的局部变量，如果是以指针或者引用的形式返回，那么将产生错误的结果。如果是以传值的方式返回，那么将没问题，因为返回的是对象的副本，它在函数结束之后仍然存在。