腾讯事务型开发面试-蒲公英云

腾讯电话一面

1、malloc 和 new 的区别？

malloc 是一个库函数，而 new 是C++11 新引进的关键字，不过 new 的底层也是一个 malloc 函数，相当于对 malloc 进行了封装，另外 malloc 函数返回值是 void*,所以需要强占类型转化，对于 new 是可以指定类型返回的，在申请的时候，malloc 需要指定特定的字节数去申请，那么 new 可以直接通过类型去推导出申请多个字节，所以 new 使用起来更加方便点

对于申请内置类型，malloc 和 new 区别不大，但是如果申请的自定义类型，在创建对象的时候会调用构造函数，那么 new 它是通过调用 operator new 函数去申请的，如果申请成功返回，申请失败则抛出一个异常，operator new 它的底层依然是通过 malloc 去向内存申请资源.

2、引用和指针的区别，使用场景？

引用本身就是一个实体，也可以理解为一个别名，而指针是通过一个指针变量去指向内存中的一块资源，引用可以直接对实体操作，而指针是通过解引用的方式去操作，而且可能会发生内存错误的问题，所以引用使用起来比指针更加安全.

对引用求字节数，比如 sizeof 函数，得出来的结果是实体所占的字节数，而指针在 32 和 64 位系统分别是 4 个字节和 8 个字节，引用不可为空，它一定是要指向一个实体，而指针可以为空，另外指针也存在二级指针，三级指针…，引用是不存在的

使用场景：在给变量起别名的时候，也可以将引用作为函数的形参，比如在拷贝构造函数的时候，传入的是一个引用形参，另外也可以将引用作为函数的返回值，通过传引用的方式可以减少开销；如果对象时一个数组的时候，在进行传入参数使用指针去传入首地址就可以了，另外如果对象是一个结构体，那么也可以通过指针的方式传入

3、vector 使用过吗？仿函数是什么？迭代器失效原理，为什么会失效？

vector 是 STL 中的序列式容器，底层是一个动态的数组，在进行访问的时候是以 O(1) 的时间复杂度，因为是它一块连续的内存，可以直接通过下标去访问，主要的使用场景就是查找访问次数多的情况，对于插入和删除的情况可以使用 list 容器，它的底层结构是双向链表，所以在插入和删除方面是高效的.

迭代器是相当于一个工具，它在不知道容器内部的结构情况下，遍历容器内的元素，vector 在插入的一个元素的时候可能会导致迭代器失效，比如插入元素的时候需要扩容，那么扩容就可能导致所有的迭代器失效，在删除的时候，会导致后面的迭代器失效

迭代器之所以失效，是因为一些操作影响了元素的位置，就比如一组数据 1 2 3 4 5 6 7 8 9 ，假如此时迭代器指向的是 6 元素，如果把 6 删除后，6 后面的元素就会向前走，对迭代器进行操作的时候就会导致内存访问错误，正确的做法应该是让迭代器赋值到指向 7 的元素.

4、在使用容器的时候，如何分配空间的？

通过空间配置器，空间配置器可以分为两级，一级是对比较大的内存，比如大于 128k 进行处理，它是通过对 malloc 进行了封装，然后去内存中申请资源，如果申请成功的话返回，如果失败会抛出一个异常，对于二进空间配置器，它是通过内存池来实现的，内存池是首先向内存中申请一大块内存，然后用户需要的时候直接去内存池取就可以了，使用完内存还给内存池，这样做可以避免频繁的申请内存而导致内存碎片所带来得空间资源浪费

5、排序问题，冒泡排序和快速排序如何实现？各自的时间复杂度，最坏情况的时间复杂度？

冒泡排序是通过比较相邻的两个元素，如果两个元素不满足规则就进行交换，每一对相邻的元素都做同样的工作，一般有两种情况，一种是向上排序，一种是向下排序，将最大的由元素或者最小的元素排在前面或者后面.

冒泡法最好的时间复杂度是O(N)，最坏是O(N2)

快速排序是通过划分基准值的方式，左边所有的元素比基准值小，右边所有的元素比基准值大，然后通过递归的方式分别对左右两边进行同样的操作，直到整个数据有序.时间复杂度为N*log(N)，最坏为O(N2)

6、浅拷贝和深拷贝，所有的浅拷贝都是多个对象使用一个资源吗？深拷贝是一个对象占用一个资源？

浅拷贝是在拷贝的过程中，将值和地址一起拷贝过去，那么就会导致多个对象指向同一块内存，例如类中的默认拷贝构造函数就是一种浅拷贝的方式，使用起来是比较危险的，可以通过深拷贝的方式来解决浅拷贝带来的问题

深拷贝的意思是两个指针或对象指向的不同的内存资源，他们之间是独立的并不共享内存，这样可以避免释放资源的时候发生错误

当然也有一种方法，可以解决浅拷贝的问题，就是采用写时拷贝，它的本质是一个引用计数器，对于构造的时候会对计数器 +1，然后释放的时候会 -1 操作，只有当这个计数器值为 0 的时候，然后才会释放资源，另外关于写时拷贝在读取的时候，如果不需要对内存进行操作那么就不进行拷贝，如果需要进行操作内存的时候，就会为操作的对象拷贝一份资源，这样可以无论它怎么修改，都不会影响到原来的内存，既保证了安全性，也提高大量拷贝带来的开销.

7、static 关键字用法？

static 修饰局部变量，全局变量，函数，类中的成员变量，类中的成员函数

修饰局部变量的时候，生命周期边长，本来局部变量在函数调用完成之后就会释放，现在它随着整个程序结束后才会释放，作用域是不变的，static 修饰全局变量的时候作用域变小，本来是源程序的作用域，经过修饰后变为当前文件可见，生命周期不变，当修饰普通函数的时候和全局变量类型，只对当前文件可见

修饰类中的成员变量时，存储在全局数据区，不属于某个对象而是属于整个类，初始化的时候就会分配内存空间，对所有的对象共享，修饰成员函数的时候，称为静态成员函数，里面没有 this 指针，所以不会修改成员变量，同样被所有的对象共享，并不属于某一个对象，另外静态成员函数不可以调用非静态的成员函数.

8、const 使用方法以及常用的使用场景？

const 可以指定一个变量不可以被修改，有三种写法，当 const 写在最前面的时候，指定的时候变量的值不可以被修改，如果写在最后面的时候，表示指针的指向不可以修改，写在中间和前面的功能是一样的.另外在传入参数的时候可以使用 const 保证变量的安全

9、map 容器，底层原理，key 可以重复吗？

map 底层结构红黑树，通过键值对的形式存储元素，key 是不可以重复的，如果重复的话可以使用 multimap 容器，对于 map 也自带排序的功能，查找起来也比较快，是 log(N)的时间复杂度.

10、二叉树有了解吗？

二叉树有很多种类，比如二叉搜索树，它的时间复杂度是O(N)，因为会有极端的情况出现，所谓为了避免这种情况，引入了 AVL 树，它在搜索树的基础上增加了平衡因子，可以保证二叉搜索树的平衡，时间复杂度降低到 O(logN)，但是由于需要进行旋转，所以会带来很大的开销，那么又引入红黑树，它不是绝对的平衡，根据自己的特性，比如一个节点只能不是红色就是黑色，根节点和叶子节点都是黑色这种特性，保证旋转的次数被大大的减少，但是它的查找时间复杂度依然是O(logN)

11、进程间通信方式？

进程之间通过通信可以传输文件，传送信息，那么可以通过管道来进行通信，管道是半双工的通信方式，管道分为匿名管道和命名管道，匿名管道它只能允许亲缘进程之间的通信，而命名管道则不受限制，它们都有共同的特性和读写规则

当管道没有数据的时候，不可以读，当数据满的时候，不可以写，如果对应的写文件描述符被关闭，则读的时候 read 函数会返回0，如果读端被关闭，则写的时候，写端会触发异常

另外我觉得管道就是一块内存的缓冲区构成的一个队列，使用一对文件描述符来访问这个内存，读文件描述符就是往队列中取数据，写文件描述符就是往队列中插入数据

它的缺陷是效率比较低，而且如果数据没有取出，则不会返回，所以可以使用消息队列

消息队列是内核维护的一个队列，发送信息的一端往队列中插入信息，接收的一端从队列中取走数据就可以了，消息队列传输的是有类型的数据块节点，它的缺陷是需要从内核态到用户态之间的拷贝，效率依然不是很高，所以可以使用共享内存的通信方法

共享内存它不需要数据拷贝，只需要各个进程的虚拟地址空间映射到相同的物理地址空间就可以了，然后通过共享出来的内存进行通信

大致可以分为五个步骤，创建共享内存，将共享内存映射到虚拟地址空间，通过虚拟地址空间进行内存的访问与操作，如果不需要通信的时候，就解除映射关系，最后释放共享内存.

由于共享内存不需要用户态到内核态，以及内核态到用户态之间的数据拷贝，所以它是进程间最快的通信方式

但是需要注意的时候，共享内存并没有实现同步的机制，那么就可以使用信号量进行通信

信号量它的本质是维护了一个计数器，可以保证多进程之间的同步与互斥，例如信号量的初始值为1，当一个进程占用资源的时候，会将值设为0，意味着其他进程不可以访问资源，然后当内存资源被释放的时候，值变为1，这个时候其他进程就可以访问资源

上述的四种通信方式，仅仅限于同一台主机，如果想要实现对端之间的通信，那么可以使用套接字的通信方式

套接字通过网络中的协议对数据进行组装，然后发送，就比如 http 协议，将数据封装为发送报文，然后传送给传输层，可以使用 tcp 或者 udp 协议将数据发送给 IP端，ip 协议可以实现端与端之间的通信.

12、网络接口的 apl 函数有哪些？

通过 socket 创建套接字，然后客户端通过 connect 函数与服务器建立连接，服务器在建立连接之前，需要先调用 listen 函数进行监听，并且通过 bind 函数绑定IP地址和端口号，当服务器收到连接请求后，服务器通过 accept 函数从已完成的队列中获取一个客户端请求，然后如果客户端发送消息的时候，可以通过 send 函数发送给服务器，那么服务器通过 recv 函数进行接收.最后通过 close 函数可以关闭套接字

13、数据库事务？

数据库的事务就是，系统对数据进行一系列的访问与更新操作，而这些操作组成一个程序的执行逻辑单元，一共有四大特性

原子性保证的是，该操作要么成功，要么失败，不会执行到一半，一致性指的是事务的开始和结束没有破坏整个数据库的完整性，隔离性指的是当多个用户并发操作数据库的时候，可以保证其安全性，最后一个是持久性，当数据提交到数据库的时候，是永久的

数据库通过隔离级别来解决读的问题，MySQL的默认隔离级别是可重复读，它可以避免脏读，和不可重复读带来的影响，脏读也就是读取了未提交的数据，不可重复读针对的是对数据进行了修改的操作，但是默认隔离级别不可以解决幻读的问题，幻读主要针对的是插入和删除时导致的问题，解决幻读可以通过可串行化读，在读取的时候需要锁住了整张表.所以效率是比较低的.

14、数据库的索引？

数据库索引它是对一列或者多列进行排序的一种结构，它的底层是 B+ 数，有的也是哈希结构，索引的目的是提高数据的检索速度，当然不同的索引也有不同的特性

普通索引，它没有限制，单纯的就是为了提高数据的检索，唯一索引它的值必须是唯一的，可以保证记录数据每一行的唯一性，对于主键索引，它是一种特殊的唯一索引，只要体现在一张表只能有一个主键索引，且不为空，另外还有组合索引，组合索引可以覆盖多个列

15、数据库表的排序关键字、求和关键字？

distinct 可以去重，like 进行匹配，desc 降序，asc 是升序，查询总数 count，数据的更新 update ，数据的删除 delete