C++开发面经总结

https://www.nowcoder.com/discuss/90907?type=2&order=0&pos=3&page=1

一、C语言基础

1、struct 的内存对齐和填充问题
其实只要记住一个概念和三个原则就可以了：

• 一个概念：
  自然对齐：如果一个变量的内存起始地址正好位于它长度的整数倍，就被称做自然对齐。
  如果不自然对齐，会带来CPU存取数据时的性能损失。（PS：具体应该与CPU通过总线读写内存数据的细节相关，具体没有细究）
• 三个原则：
  1）struct 的起始地址需要能够被其成员中最宽的基本数据类型整除；
  2）struct 的size 也必须能够被其成员中最宽的基本数据类型整除；
  3）struct 中每个成员地址相对于struct 的起始地址的offset，必须是自然对齐的。
  填充的字节是随意填充任意字符的，除非赋值前先对结构体变量s进行memset(s, 0, sizeof(s));进行整个内存清零处理（全0填充，也可以用其他字符全填充）。

2、struct变量能进行比较吗？

• C语言不能直接用==、>、>=、<、<=这些进行比较。但是C++若是对这些用于比较的关系运算符进行了重载（重载内部可以调用memcmp函数），那就可以进行比较了。
• 在对结构体变量都用memset初始化的前提下，可以用memcmp函数进行一个一个字节的比较。int memcmp(const void *buf1, const void *buf2, unsigned int count);相同返回0，大于返回正数，小于返回负数。（类似于strcmp函数的返回值）
• 若是没有用memset统一初始化填充字节，那么任意的填充字节就会影响比较结果。
• 结构体变量之间可以直接赋值，如struct student stu1 = stu2;但是注意，赋值是调用memcpy一个一个字节复制过去的，而不是按照stu1.id=stu2.id;这样一个一个成员复制过去的。因此对于用=直接赋值的两个变量，再用memcmp比较，肯定是相等的。

3、运算符优先级问题

• 优先级排序：() > !非(其他单目的) > 算术运算符 > 关系(> < == !=)运算符>逻辑(& ^ | && ||)运算符>赋值运算符>逗号

https://blog.csdn.net/u013630349/article/details/47444939

4、手写strcpy字符串拷贝函数？先问要C风格的还是C++风格的？

#include <assert.h>
#include <stdio.h>
char* strcpy(char* des, const char* src)  //注意const。C++风格的(char& des, const char &src)
{
    assert((des!=NULL) && (src!=NULL));   //注意输入合法性检查。
//但是对于C++可以有更好的解决方案，将输入参数指针改为引用&，就默认不能传入NULL，否则报错
    char *address = des;          //注意返回值是目的串首地址
    while((*des++ = *src++) != '\0')  
        ;  
    return address;
}

https://www.nowcoder.com/ta/review-c/review?tpId=22&tqId=21053&query=&asc=true&order=&page=4
另有strlen、strcmp、strcat函数的手写：https://blog.csdn.net/lisonglisonglisong/article/details/44278013
另外strncpy函数，复制完后des目标字符串的末尾不会有'\0'结束符，一种解决办法是自己加上一行 des[n]='\0';。更好的做法是给des字符数组初始化为全空字符串char des[100]="";或者memset(des, 0, 100);

5、手写一个memcpy函数？

• 陷阱是要注意有重叠区的拷贝，比如str[10]="123456789"，要memcpy(str+2, str, 5);，若是不考虑重叠区而简单的从前往后拷贝，会得到返回"1212189"，然而我们想要的结果是"1234589"

void* Memcpy(void* dest, const void* src, size_t size)
{
    char *pdest, *psrc;
    if (NULL == dest || NULL == src)
    {
        return NULL;
    }
    //要考虑如果目标地址和源地址后面有重叠，则要防止源地址后面的原始数据被目标地址拷贝过来的数据覆盖
    //这种情况就需要从后往前拷贝
    if (dest>src && (char *)dest<(char *)src+size)
    {
        pdest = (char *)dest + size - 1;
        psrc = (char *)src + size - 1;
        while (size--)
        {
            *pdest-- = *psrc--;
        }
    }
    //从前往后正常拷贝赋值
    else
    {
        pdest = (char*)dest;
        psrc = (char*)src;
        while (size--)
        {
            *pdest++ = *psrc++;
        }
    }
    return dest;
}

6、main函数的返回值作用？如何捕获返回值？

• int main(int argc, char *argv[]) { return 0; }标准main函数写法，在命令行运行可执行文件时，argc表示参数个数，argv表示指针数组，数组里面每个元素都是一个字符串指针首地址。
• 返回0表示程序正常退出，返回其他数字的含义由操作系统决定。
• 在windows中再命令行执行上面最简单的代码编译承德可执行文件test.exe后，再执行命令echo %ERRORLEVEL%（windows命令行大小写不敏感）可以输出main函数的返回值：0，修改为return -1;实验后也可以看到返回值为：-1。
• 在linux中可在执行可执行文件./test后，再输入一行命令echo $?打印出main函数的返回值。
• 在win的test.exe && dir或linux的./test && ls，都可以根据可执行文件的main返回值来判断是否后面的系统命令是否继续执行，main返回值为0时才表示真，则后面的列出当前目录命令都可以执行。main返回其他值则后面的不继续执行。

7、进程间通信的方式有哪些？

• 无名管道（父子进程兄弟进程使用单发单收）；有名管道FIFO（任意两进程间）；共享内存；消息队列（需要内核维护这个消息队列）；信号（如一些引发中断信号kill）；信号量（也是需要由内核维护）；socket（可跨网络主机进程通信）

8、线程间的通信

• 共享的全局变量，然后利用全局的锁变量或者信号量来实现同步互斥访问共享的全局变量达到通信的目的。

9、进程调度算法有哪些？Linux使用的什么进程调度方法？

• 【解】进程调度算法有下面几种：
  先来先服务
  短作业优先
  时间片轮转
  基于优先级

Linux系统中，进程分为实时和非实时两种：

• 实时进程（相对于普通进程优先级更高）
  SCHED_FIFO —> 相同优先级时，先来先服务；不同优先级，抢占式调度。进程一旦占用cpu则一直运行，直到有更高优先级任务到达或自己放弃。
  SCHED_RR —> 时间片轮转，抢占式调度。
• 普通进程
  SCHED_OTHER —> priority（静态优先级）+counter（剩余时间片）之和作为动态优先级，基于动态优先级的时间片轮转。

10、虚拟内存和物理内存？

• 先说说为什么会有虚拟内存和物理内存的区别。正在运行的一个进程，他所需的内存是有可能大于内存条容量之和的，比如你的内存条是256M，你的程序却要创建一个2G的数据区，那么不是所有数据都能一起加载到内存（物理内存）中，势必有一部分数据要放到其他介质中（比如硬盘），待进程需要访问那部分数据时，再通过调度从磁盘进入物理内存。所以，虚拟内存是进程运行时所有内存空间的总和，并且可能有一部分不在物理内存中而在磁盘中，而物理内存就是我们平时所了解的内存条。有的地方呢，也叫这个虚拟内存为内存交换区。

1）每个进程都有自己的虚拟内存空间，所有进程共享物理内存空间。
2）虚拟内存大小和机器的位数有关，如32位的是4GB的地址总线（0~0xFFFFFFFF字节）其中每个进程都有自己的0~0xBFFFFFFF的3GB虚拟内存空间——用户空间，然后所有进程共用0xCFFFFFFF~0xFFFFFFFF这1GB的虚拟内存空间——内核空间。64位的有2^64字节的地址总线。

3）该图显示了两个 64 位进程的虚拟地址空间：Notepad.exe 和 MyApp.exe。每个进程都有其各自的虚拟地址空间，范围从 0x000'0000000 至 0x7FF'FFFFFFFF（8TB用户进程虚拟内存空间）。每个阴影框都表示虚拟内存或物理内存的一个页面（大小都为4KB）。注意，Notepad 进程使用从 0x7F7'93950000 开始的虚拟地址的三个相邻页面。但虚拟地址的这三个相邻页面会映射到物理内存中的非相邻页面。而且还注意，两个进程都使用从 0x7F7'93950000 开始的虚拟内存页面，但这些虚拟页面都映射到物理内存的不同页面，说明个进程间的虚拟内存互不影响。
4）这种虚拟内存一个页page（4KB）和物理内存一个页帧（4KB）之间的映射关系，由操作系统的一个页表来维护，页表中给各个页都有编号（页号和页帧号对应映射）。进程中虚拟内存页》页表中的页号—MMU内存管理单元—页表中的页帧号《物理内存中的页帧【由MMU的页表来维护映射关系】

5）但是问题来了，虚拟内存页的个数=3GB/4KB > 物理内存页帧的个数=256MB/4KB，岂不是有些虚拟内存页的地址永远没有对应的物理内存地址空间？不是的，操作系统是这样处理的。操作系统有个缺页中断（page fault）缺页异常功能。操作系统把暂时不访问的物理内存页帧，让他缺页失效，并把它的原内容写入磁盘转存起来——这个过程叫分页-分页是磁盘和内存间传输数据块的最小单位。，随后把当前需要访问的页放到页帧中，并修改页表中的映射，这样就保证所有的页都有被调度的可能了。当进程又要访问原转存的内容，会先访问原物理内存页但是引发缺页中断然后从磁盘中取出页内容到物理内存页，然后进程访问到数据继续执行。这就是处理虚拟内存地址到物理内存的步骤。

https://www.cnblogs.com/curtful/archive/2012/02/16/2354496.html

11、为什么需要虚拟内存？通过虚拟地址访问内存有哪些优势？

• 虚拟内存地址可以提供只读只写的访问权限来保护实际对应的物理地址的数据。
• 程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
• 不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。
• 程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将（暂时不用的）物理内存页（通常大小为 4 KB）保存到磁盘文件，从而空出可用的物理内存。数据或代码页会根据需要在物理内存与磁盘之间移动。

12、死锁产生的四个条件，死锁发生后怎么检测和恢复？

• 死锁的四个必要条件：
  互斥条件：一个资源每次只能被一个进程使用。
  请求与保持条件：一个进程在申请新的资源的同时保持对原有资源的占有。
  不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。
  循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。
• 死锁发生后：
  检测死锁：首先为每个进程和每个资源指定一个唯一的号码，然后建立资源分配表和进程等待表。
  解除死锁：当发现有进程死锁后，可以直接撤消死锁的进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止。

13、不用中间变量实现两个元素交换值。

void swap1(int &a, int &b)
{  //异或操作只适用于整型数，不能用于小数
    if (a != b)  //如果两个数地址相同，异或操作会清零
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
}
void swap2(double  &a, double &b)
{//用double型可以使适用的范围更大，防止加法和越界
    a = a + b;
    b = a - b;
    a = a - b;
}

14、一些常见的位操作

• 位操作符的运算优先级比加减更低，如int a = 1 << 2+ 1;得到a的值1左移3位得8，与int a = (1 << 2)+ 1;得5不同。
• 取得a的相反数-a：~a+1; a取反再加一。
• 可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。即只需判断a的最低位是0还是1。
• 取得绝对值

int my_abs(int a)
{
    int i = a >> 31;  //得到最高位符号位，a为正或0返回0，a为负数返回-1
    return i == 0 ? a : (~a + 1);  //正数返回本身，负数返回相反数
    //return (a^i)-i;  //a^0 ==a本身；a^(-1) == a取反，再减-1即加1得到相反数
}

• 给出一个16位的无符号整数。称这个二进制数的前8位为“高位”，后8位为“低位”。现在写一程序将它的高低位交换。a = (a >> 8) | (a << 8);

二、C++基础

1、new表达式（new operator）和std::operator new标准库函数的区别

• new operator 是先调用operator new函数来分配返回值为void*的内存，然后再调用作用类型的构造函数去初始化赋值这块内存。如string * str = new string("hello");就是对new表达式的常用方式。

这里我们可以这么理解，new表达式(new operator)其实可以分解为两部，即先调用new操作符(operator new)申请内存，再调用placement new来初始化对象。即上面对new表达式的使用string * str = new string("hello");等价于下面两句。

void *buffer = ::operator new(sizeof(string));
buffer = new(buffer) string(“hello”);

• 而operator new函数相当于是malloc，其实它的内部实现也就是调用了void * malloc(size_t size);函数。

 void* operator new(size_t sizt)
{
      return malloc(size);      
}

详见：https://www.jianshu.com/p/a07ba8f384da

2、new和malloc有哪些区别？

最重要的是要说到最下面一条。
详见：https://www.cnblogs.com/QG-whz/p/5140930.html

3、头文件防卫式编程，防止头文件多次嵌套导入。
比如要编写头文件mystring.h，就可以这样写。如果统一遵循这种规则，那么就不会出现mystring.h头文件内容在编译前预处理时被重复导入的情况。

#ifndef __MYSTRING__
#define __MYSTRING__

#include<string.h>    //用到C语言的字符串处理函数
class mystring
{
public:
        mystring();
        ~mystring();
private:
        char * head;
        int length;
}；
#endif

4、const函数？——函数定义后面加const有什么作用？

• 只有类成员函数后面才能加const，普通函数没有所谓的const函数，不能在后面加const。如复数complex类的获取实部成员函数int getReal() const { return real; }
• 作用是表示此类成员函数不能改变所有类成员变量的值。
• 当定义一个const的类对象时const complex con1;，此对象con1就只能调用这些const成员函数，调用非const成员函数就会报错。

5、C++内存分区？进程虚拟内存分布？共有5个分区

6、一个进程可用的内存大小、线程可用内存大小？堆内存多大？栈内存多大？

• 根据上面这张图可以分析出，一个用户进程最多可用3GB内存，进程里既有堆又有栈。而一个线程只有自己的栈空间，所以可用的最大栈内存也就是上图说的8MB或10MB（可手动修改）。因此一个最多可开辟3GB/10MB=300个线程。
• 对于4GB内存封顶的32位系统，用户空间堆内存<3GB（留1GB给内核空间），而栈内存一般只有8M(ubuntu)或10M(centos)各系统默认值不同，可修改。

7、用vs编程时debug和release版本有啥区别？

• Debug通常称为调试版本，它包含很多调试信息，并且不作任何优化，便于程序员调试程序（加断点实时查看变量值）。会检查assert断言语句。也可关闭assert断言——先#define NDEBUG 后#include<assert.h>，就可以将后面写的那些assert断言语句关闭检查。
• Release称为发布版本，它往往是进行了各种优化（比如调整某些变量在栈内存的地址顺序），使得程序在代码大小和运行速度上都是最优的，以便用户很好的使用。会忽略assert断言语句。

8、面向对象的三大特性讲一下？

• 封装：将变量和对变量的操作组合在一起形成一个类或者一个模块，就是封装。一处封装，多处调用。目的是代码复用。
• 继承：子类在原有父类代码的基础上进行扩展。目的是代码复用。
• 多态：调用同名函数，却因为上下文环境不同，而会有不同的实现。一个函数接口多种实现。目的是接口复用。

9、C++多态分几类？多态有几种实现方式？

10、C能直接用C++写的动态库吗？C++能直接用C写的动态库吗？

• 都不能直接互用。主要原因是C++有函数重载，相同函数在汇编代码中的会带上参数表示，而C不支持函数重载因此在汇编中函数名只有函数名。比如int add(int a, int b);，在C++编译后的汇编代码中是_add_int_int或其他表示，而在C语言汇编代码中只是_add。
• 因此，C++要调用用C的动态库，不用重新编译C，只需在自己的C++代码中吧要调用的C函数原型用extern "C" int add(int a, int b);，这样该C++代码在编译是就会将这个add函数原型用C的形式编译成_add。然后就和原C的动态库函数名对上了。否则C++代码中编译成_add_int_int在调用C动态库时会报错找不到该函数。
• C要调用C++的动态库时，必须修改原C++代码，将要被C调用的函数原型修改为extern "C" int add(int a, int b);，就可以被编译成C形式了，然后重新编译就可供C调用。编译完成后，提供给c使用的头文件里面不能包含extern “C”，可以使用宏开关解决，也可以重新写个头文件。当然还有一点就是该函数内部不能包含用C++特有的东西。
• 总结，要想互相能调用，都只需要对C++代码进行修改，函数原型前加extern "C"，而C代码不需要修改。

11、从源代码到可执行文件经历了那几步？

• 文本源代码》预处理（得去注释、宏替换、展开头文件等的文本源码》编译（得文本汇编代码.S）》汇编（得二进制的.o目标文件）》链接多个.o（得到二进制可执行文件）

12、C和C++的区别

• C语言更加注重的是过程，C++除了保留C语言的优点，还增加了面向对象的机制。
• 应用场景来看，由于C没有面向对象，所以在程序规模太大的时候写起来很复杂，面向对象的C++更适合大规模的程序。
• C没类class面向对象更多的是面向过程编程，struct的用法也有差异，比如定义struct变量的时候C要带上struct关键字，而C++的struct用法和class一样，只是内部数据访问权限struct默认public，calss默认private。
• C没有bool型，可用int型代替。C没有方便的string可用
• C++的泛型编程和STL提供的多种容器也是C所没有的。
• 函数重载，操作符重载，C也没有。这也导致两者代码不能直接调用。

13、C++和java的区别

• 我觉得C++与Java最大的区别是在于内存管理上，C++的内存管理是需要程序员自己控制的，自己开了需要自己去释放。然而Java提供了JVM，JVM就是用来进行内存管理的，不需要程序员自己手动开关。
• Java呢，摒弃了C++很多复杂的特性，比如指针、多继承、操作符重载等等，相对来说Java的编程学习入门比较容易。

14、static_cast 和 dynamic_cast 的区别？两个操作符

• cast转换发生的时间不同，一个是static静态编译时，一个是动态运行时；
• static_cast是相当于C的强制类型转换，用起来可能有一点危险，不提供运行时的检查来确保转换的安全性。
• dynamic_cast用于转换指针和和引用，不能用来转换对象 —— 主要用于类层次间的上行转换和下行转换，还可以用于类之间的交叉转换。在类层次间进行上行转换时，dynamic_cast和static_cast的效果是一样的；在进行下行转换时，dynamic_cast具有类型检查的功能，比static_cast更安全。在多态类型之间的转换主要使用dynamic_cast，因为类型提供了运行时信息。

15、说几个C++11的新特性。

1)auto类型推导：auto vData = vectors.begin();自动推导出vector中的数据类型
2)范围for循环：for( auto v:vectors) { cout<<v<<endl; }这样的v是只读的，也可以用到&引用，作为可修改的for(auto &v:vectors){ v=v+1; }
3)lambda表达式：是一个匿名函数，即没有函数名的函数。
4)override 和 final 关键字：两个继承控制关键字，override明确地表示一个函数是对基类中一个虚函数的重载，virtual void func(int) override;确保在派生类中声明的重载函数跟基类的虚函数有相同的签名。final阻止类的进一步派生class TaskManager {/*..*/} final;和虚函数的进一步重载virtual void func(int) override final;。
5)空指针常量nullptr
6)线程支持、智能指针等：https://www.kancloud.cn/wangshubo1989/new-characteristics/99704

16、如何在一个不安全的环境中实现安全的数据通信？

• 要实现数据的安全传输，当然就要对数据进行加密了。
• 如果使用对称加密算法，加解密使用同一个密钥，除了自己保存外，对方也要知道这个密钥，才能对数据进行解密。如果你把密钥也一起传过去，就存在密码泄漏的可能。所以我们使用非对称加密算法，过程如下：

首先 数据接收方 生成一对密钥，即私钥和公钥；
然后，数据接收方 将公钥发送给 数据发送方；
数据发送方用收到的公钥对数据加密，再发送给接收方；
接收方收到数据后，使用自己的私钥解密。
》由于在非对称算法中，公钥加密的数据必须用对应的私钥才能解密，而私钥又只有接收方自己知道，这样就保证了数据传输的安全性。

17、面向对象思想主要如何体现？

• 面向对象的三大特性是封装、继承、多态。
• 实际中，对一个类的数据成员和方法成员进行封装，对抽象基类的继承可以很好的复用基类封装的数据和方法成员，多态的应用可以使父类指针指向子类的实例对象从而在程序运行时动态地选择最合适的方法执行。
• 类与类之间的各种关系，也是面向对象的重点，合理地利用类与类之间的关系可以设计出很多很好的设计模式。

18、类与类之间的各种关系？

【继承inheritance】A is-a B
类A继承类B，UML类图是实线加三角形由A指向B。A is-a B.
public继承：父类中的成员访问权限不变。
pretected继承：父类的访问权限中public权限降为protected，其他不变。
private继承：父类中public和protected权限的成员全变为private，权限降级，即子类只有类成员变量和友元函数能够访问这些。
【依赖dependency】A use-a B.
类A依赖类B，UML类图是虚线加箭头由A指向B。A use-a B.
一般来说，依赖是指A的某些方法功能要用到B，常表现为B作为A的成员方法的形参或局部变量或返回值，即只和类成员方法有关。
【关联association】A has-a B, B has-a A.
类A和类B双向关联，UML类图是A——B一根实线连接。A与B互相作为类的数据成员变量。
【组合composition】A has-a B 实例对象
类A组合了类B，UML类图是A实心菱形再实线和箭头指向B。类A中定义了类B作为数据成员，B在A中定义构造。A和B的对象生命周期一样。A拥有完整的B，强拥有关系。
【聚合aggregation】A has-a B 引用
类A聚合了类B，UML类图是A空心菱形再实线和箭头指向B。类A中定义了类B的指针作为数据成员，类B的实例化在其他地方。A和B的对象生命周期不一样。A拥有不完整的B，弱拥有。可以认为是 composition by reference == aggregation 或者也可以叫做委托delegation。

19、谈谈你了解的设计模式有哪些？

• 设计模式本质上是通过类与类之间的各种关系来实现的。
• 【模板方法模式】技巧总结：抽象父类+抽象方法+继承+多态
• 【单例模式】技巧总结：聚合了一个自身的静态对象指针+私有构造+公有静态getInstance()方法（懒汉模式）
• 【简单工厂模式】技巧总结：继承+依赖+多态+前后端分离
• 【工厂方法模式】技巧总结：继承+依赖+多态+简单工厂升级（增加具体的工厂子类）
• 【策略模式】技巧总结：继承+依赖+多态+聚合（简单工厂多一个聚合和多一个算法调用函数）
• 【观察者模式】技巧总结：继承+聚合+依赖+多态

三、STL

1、STL的作用，为什么需要STL？（常用的是SGI版本的STL，被纳入GNU C++标准库）

• 一是可复用性。STL标准模板库，提供了一套常用的标准的数据结构和算法程序以及和泛型模板编程结合，我们在写程序时，可以快速复用，而不需要重复的去造轮子，要站在巨人的肩膀上，节约时间。
• 二是高效性。STL的代码经过多位C++大师的优化，比绝大多数人自己再重写相关的数据结构和算法代码效率更高，因此我们应该尽量多用STL。
• 研究STL源码的意义在于，深入理解和学习优秀的数据结构和算法原理，然后扩展轮子，或者是深入定制自己的轮子。
• STL更注重的是模板泛型编程，而不是面向对象编程。

2、STL六大组件之间的关系？

• 六大组件：空间配置器（allocator）、容器（container）、迭代器（iterator）、算法（algorithm）、仿函数（functor）[函数对象]、适配器（adapter）[包装器]。
• 空间配置器为容器分配内存，容器的模板参数中都有一个默认的空间配置器class Alloc = alloc。最简单的空间配置器实现就是类内部用alllocate成员函数封装::operator new(相当于malloc)分配内存，再用construct成员函数负责对象的构造（实际上是借用定位new——placement new来给这块内存初始化的buffer = new(buffer) T(value);其中T(value)就用到了构造函数）；用destroy成员函数完成析构，再用deallocate成员函数封装::operator delete（相当于free），来实现对象的内存分配和构造初始化以及用完后析构和释放内存。而这些分步也是实现常用的new/delete表达式的步骤。STL提供的空间配置器分为第一级配置器和第二级配置器。
• 容器分为序列式容器（vector/deque/list/forward_list）和关联式容器（set/map/unordered_set/unordered_map）。
• 迭代器作为容器和算法的粘合剂，算法函数的传入参数一般都是容器的迭代器。指针也是一种特特殊的迭代器。迭代器有5中类型：
  1）input iterator：只读入数据的迭代器，不能通过它修改指向的元素值
  2）output iterator：只写入数据的迭代器
  3）forward iterator：包含上面的可读可写功能，然后只有operator++向前单步移动的功能。
  4）bidirectional iterator：包含上面的读写功能，可双向单步移动，支持operator++和--。
  5）random access iterator：随机存取迭代器，不仅可读可写，还支持顺序存储如用数组下标的跳步移动访问功能。
• 算法
• 仿函数又叫函数对象，常用类名加()代表一个临时对象，可为算法动态地提供某种策略。类中一定重载了operator()。比如常用的将算法库中的sort函数的比较策略用一个仿函数传入，当然也可传入一个函数指针或是对类型重载<号。一般函数指针可以当做仿函数对象用。
• 适配器类的内部封装（组合）了一个其他类的对象。如容器适配器stack/queue默认就是在内部组合了一个deque<T> dq;，该deque对象的生命周期和stack/queue对象一样，然后通过封装dq对象的某些成员函数来实现自己的功能。还有仿函数适配器；迭代器适配器。

3、vector、map/multimap、unordered_map/unordered_multimap的底层数据结构，以及几种map容器如何选择？

• 底层数据结构：vector基于数组，map/multimap基于红黑树，unordered_map/unordered_multimap基于哈希表。
  根据应用场景进行选择：
  map/unordered_map 不允许重复元素
  multimap/unordered_multimap允许重复元素
  map/multimap底层基于红黑树，元素自动有序，且插入、删除效率高
  unordered_map/unordered_multimap底层基于哈希表，故元素无序，查找效率高。

4、type_traits<T>是什么作用？

• 这个的作用是对类型T进行一些和类型相关的询问，然后返回true或false的相关回答（即对类型T萃取出相关类型说明）。也有iterator_traits可以萃取出一个迭代器的相关类型。
  比如在空间配置器alloctor的实现中，有个destroy成员函数在对数组中的所有成员析构时，会先用type_traits<T>::has_trivial_destructor检查成员类型的析构函数是否是trivial（不重要的），若是返回__false_type则说明这个类型T的析构函数是重要的，必须对数组中每个对象依次调用析构函数。相反，若是返回__true_type说明确实是不重要的析构函数（甚至是只有默认隐藏的空析构函数），则不需要去遍历数组对象调用析构函数，可以大大提高效率。

5、STL的空间配置器实现原理？

• STL空间配置器的作用是维护对象的内存分配、释放以及构造、析构。因此我们可以从这四个作用来看实现原理，空间配置器中一定实现了allocate/deallocate/contructor/destroy这四个成员函数。这几个成员函数如何实现又要根据使用的空间配置器是第一级还是第二级。
• STL的空间配置器分为第一级__malloc_alloc_template和第二级__default_alloc_template，第一级用于处理从堆中大块内存的申请（一次128字节以上算一大块？），第二级用于处理从自定义的内存池中取得小块内存的申请。默认使用第二级，但是在第二级的allocate会判断要申请的字节数n若是大于128则直接跳转到第一级，否则再从第二级内存池中对应的链表中获取合适的区块。
• 第一级配置器就是使用malloc/free/realloc这几个C语言函数从堆中分配释放内存给用户，并且自己写了处理内存不足的函数set_malloc_handle()，大致思想就是用一个无限循环来不断尝试分配内存（可能程序在刚开始时就预先分配了大块内存备用，这时候就可以释放一部分出来解决内存分配不足问题），直到分配成功。如果不写这个处理函数，那就只能返回内存分配不足的异常或直接退出程序。
• 第二级配置器（又叫次层配置sub-allocation）是维护了一个内存池，处理频繁的小块内存的申请，相比第一级从堆中申请不仅速度更快还更有线程安全性，也能更好地处理内存碎片的问题节约内存。内存池用一个数组free_list[16]维护了128/8=16个链表，分别存放区块大小为{8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128}。首次从对应链表中比如16申请区块时，会调用refill(n=16)函数先分配20个区块给区块大小n=16的链表备用。
• void * allocate(size_t n)申请内存过程：若是n>128那就转到第一级配置器去调用malloc从堆中申请，否则默认按照第二级配置器从内存池申请。比如你要申请n=10的一块内存，就可以向上升级到8的倍数16那个free_list[16/8-1]的那个链表中获取一个元素（区块）。链表中的元素(区块)obj也有意思，是一个union联合体，在分配给用户使用前将obj->free_list_link赋值给对应链表的首元素my_free_list（由于该变量是obj * volatile * 类型，直接指向了实际内存而不是存放在临时寄存器中，因此后面给它重新复制会被立即修改，而不用担心多线程问题），以便下次再从这个链表申请内存时可以立即获取一个空闲内存块。然后再分配给用户使用，从第一个char字节开始的内存。
  若是从链表中获取不到内存则要从内存池中重新分配区块到链表，若是内存池中没有了足够的内存那就要从堆中分配两倍多的内存到内存池，若是堆中内存不够则可以拆分大区块链表的内存，若是都获取不到内存，那就转到第一级配置的set_malloc_handle()去处理内存分配失败。

union obj{
    union obj * free_list_link;    //保存着下一个空闲区块的地址
    char client_data;    //表示给用户申请使用后的数据存放首字节地址
};

• void deallocate(void *p, size_t n); 释放内存过程：若是n>128，则直接转到第一级配置器去调用free释放内存到堆，否则默认按照第二级配置器的流程归还到内存池中16个链表对应的那个。

• 内存池设计：两根指针start_free和end_free分别代表池中自由的内存的首字节和尾字节地址；将要申请的字节数扩展到8的倍数的函数；一个指针数组free_list维护16个链表的区块的首地址；一个union obj表示一个区块，内含下一个区块的指针和首地址；allocate分配内存函数返回分配的区块的首地址若是大于128则转到第一级配置从malloc获取；refill()函数重新填充该种区块的链表，内部调用chunk_alloc()函数从内存池获取一大块内存，再转换成多个小区快(最多20块)并循环链接起来；chunk_alloc()负责提供大块的区块，管理内存池中剩余的区块，不够时从堆空间获取两倍多的需求填充内存池；deallocate头插法归还内存到对应链表的首部。

四、数据结构和算法

1、求一串数字序列中的连续子串最大和，比如arr=1 -2 3 -1 2，连续子串最大和就是3 -1 2组成的max_sum=4。

• 分析：这是一道动态规划的题目，可以设子问题dp[i]为以第i个数字结尾的连续子串的最大和，所以我们能得到dp[1]=1,dp[2]=-1,dp[3]=3,dp[4]=2,dp[5]=4，这5个数中最大的数max{dp[i]}就是我们要找的。
• 如果dp[i-1]<=0，那么dp[i]=arr[i]；如果dp[i-1]>0，则有必要把前面的数加入求和dp[i]=arr[i]+dp[i-1]。

int MaxSubSum(int *arr, int n)
{
    int sum=0, b=0;  //只用一个b记录dp[i]，更节省内存
    for (int i=1;i<=n; i++)
    {
        if (b>0) b+=a[i];
        else b=a[i];
        if (b>sum) sum=b;
    }
    return sum;
}

2、寻找100范围内的素数的算法，对于找到的前面的每个素数的n倍都必然不是素数，都可以剔除检查

五、网络

1、TCP三次握手，四次挥手状态改变过程？

2、ping网络主机之间通不通用到什么协议？

• ICMP（因特网控制报文协议）
• ICMP协议是IP层的附属协议，是介于IP层和TCP层之间的协议，一般认为属于IP层协议。IP协议用它来 与其他主机或路由器交换错误报文和其他的一些网络情况。在ICMP包重携带了控制信息和故障恢复信 息。主要用于路由器主机向其他路由器或者主机发送出错报文的控制信息
• 简单地说，ping就是给目标IP地址发送一个 ICMP 回显请求，并要求对方返回一个 ICMP 回显应答来确定两台网络机器是否连通，时延是多少。

六、操作系统

七、数据库

1、事务（transaction）是什么？

• 在数据库系统中，一个事务是指：由一系列数据库操作组成的一个完整的逻辑过程。例如银行转帐，从原账户扣除金额，以及向目标账户添加金额，这两个数据库操作的总和，构成一个完整的逻辑过程，不可拆分。这个过程被称为一个事务。

2、事务有几个特性？分别是什么？

• 四个特性，ACID（英语意思：酸）
• A 原子性（atomicity，或称不可分割性）一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被恢复（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。
• C 一致性（consistency）在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设规则，这包含资料的精确度、串联性以及后续数据库可以自发性地完成预定的工作。
• I 隔离性（isolation，又称独立性）数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括读未提交（Read uncommitted）、读提交（read committed）、可重复读（repeatable read）和串行化（Serializable）。
• D 持久性（durability）事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

其他

• 1、说一下为什么觉得自己适合做开发
  答：首先我对编程就有很大的兴趣，兴趣是最好的老师。我本人有较好的语言基础并且具备去做开发的职业技能。我个人在平时学习工作中都比较耐心，有较好的抗压能力，这是做开发必备的素质。兴趣+能力+素质，我想这三点就能让我可以认为自己适合做开发。