十八万字吐血整理的C/C++、嵌入式常见面试题！！！！

相关知识点都能零星在网上找到，这个文章系列将目前遇到的所有常见面试问题进行一个汇总。

文中很多资料避免不了从网上或是其他复习资料里收集整理，十分感谢前辈的辛勤付出，如果存在侵权请一定联系我进行删除。

86、map如何创建？

1.vector 底层数据结构为数组 ，支持快速随机访问

2.list底层数据结构为双向链表，支持快速增删

3.deque底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问

deque是一个双端队列(double-ended queue)，也是在堆中保存内容的。它的保存形式如下:

[堆1] --> [堆2] -->[堆3] --> ...

每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.

4.stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

5.queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）

6.priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

7.set 底层数据结构为红黑树，有序，不重复

8.multiset 底层数据结构为红黑树，有序，可重复 

9.map底层数据结构为红黑树，有序，不重复

10.multimap 底层数据结构为红黑树，有序，可重复

11.hash_set 底层数据结构为hash表，无序，不重复

12.hash_multiset 底层数据结构为hash表，无序，可重复 

13.hash_map 底层数据结构为hash表，无序，不重复

14.hash_multimap 底层数据结构为hash表，无序，可重复 

87、vector的增加删除都是怎么做的？为什么是1.5倍？

1.新增元素：vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；

2.对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了；

3.初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1；

4.不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。

对比可以发现采用采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。

扩容倍数

考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2二倍的方式扩容，或者以1.5倍的方式扩容。

1.以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间；

2.向量容器vector的成员函数pop_back()可以删除最后一个元素；

3.而函数erase()可以删除由一个iterator指出的元素，也可以删除一个指定范围的元素。

4.还可以采用通用算法remove()来删除vector容器中的元素.

5.不同的是：采用remove一般情况下不会改变容器的大小，而pop_back()与erase()等成员函数会改变容器的大小。

88、C++ sort排序算法底层

sort作为一个内置的排序方法，可以被vector等直接调用。

对于STL中的sort()算法：

1.当数据量大时，将会采用Quick Sort（快排），分段递归进行排序。

2.一旦分段后的数据量小于某个阈值，为了避免快排的递归带来过大的额外的开销，sort()算法就自动改为Insertion Sort（插入排序）。

3.如果递归的层次过深，还会改用Heap Sort（堆排序）。

简单来说，sort并非只是普通的快速排序，除了对普通的快排进行优化，它还结合了插入排序和堆排序。根据不同的数量级以及不同的情况，能够自动选择合适的排序算法。

89、 函数指针？

1.什么是函数指针?

函数指针指向的是特殊的数据类型，函数的类型是由其返回的数据类型和其参数列表共同决定的，而函数的名称则不是其类型的一部分。

一个具体函数的名字，如果后面不跟调用符号(即括号)，则该名字就是该函数的指针(注意：大部分情况下，可以这么认为，但这种说法并不很严格)。

2.函数指针的声明方法

int (*pf)(const int&, const int&); (1)

上面的pf就是一个函数指针，指向所有返回类型为int，并带有两个const int&参数的函数。注意*pf两边的括号是必须的，否则上面的定义就变成了：

int*pf(const int&, const int&); (2)

而这声明了一个函数pf，其返回类型为int *， 带有两个const int&参数。

3.为什么有函数指针

• 函数与数据项相似，函数也有地址(函数名就是指针)。我们希望在同一个函数中通过使用相同的形参在不同的时间使用产生不同的效果。
• 一个函数名就是一个指针，它指向函数的代码。一个函数地址是该函数的进入点，也就是调用函数的地址。函数的调用可以通过函数名，也可以通过指向函数的指针来调用。函数指针还允许将函数作为变元传递给其他函数；
• 两种方法赋值：

指针名 = 函数名；指针名 = &函数名

90、C与C++的联系与区别

一、C++与C的联系：

1、C++是在C语言的基础上开发的一种面向对象编程语言，应用广泛。C++支持多种编程范式 －－面向对象编程、泛型编程和过程化编程。 其编程领域众广，常用于系统开发，引擎开发等应用领域，是最受广大程序员受用的最强大编程语言之一,支持类：类、封装、重载等特性!

2、C++在C的基础上增添类，C是一个结构化语言，它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程，对输入（或环境条件）进行运算处理得到输出（或实现过程（事务）控制），而对于C++，首要考虑的是如何构造一个对象模型，让这个模型能够契合与之对应的问题域，这样就可以通过获取对象的状态信息得到输出或实现过程（事务）控制。

二、C++与C的区别

1、C是面向过程的语言，而C++是面向对象的语言，那么什么是面向对象？

面向对象：面向对象是一种对现实世界的理解和抽象的方法、思想，通过将需求要素转化为对象进行问题处理的一种思想。

2、C和C++动态管理内存的方法不一样，C是使用malloc、free函数，而C++不仅有malloc/free，还有new/delete关键字。那malloc/free和new/delete差别？

malloc/free和new/delete差别：

①malloc/free是C和C++语言的标准库函数，需要头文件包含，new/delete是C++的运算符，关键字，需要编译器支持。它们都可用于申请动态内存和释放内存。

②由于malloc/free是库函数不是运算符，不在编译器范围之内，不能够把执行构造函数和析构函数的任务强加入malloc/free。因此C++需要一个能完成动态内存分配和初始化工作的运算符new，一个能完成清理与释放内存工作的运算符delete。

③new可以认为是malloc加构造函数的执行。new出来的指针是直接带类型信息的。而malloc返回的都是void指针。

④malloc是从堆上开辟空间，而new是从自由存储区开辟(自由存储区是从C++抽象出来的概念，不仅可以是堆，还可以是静态存储区)。

⑤malloc对开辟的空间大小有严格指定，而new只需要对象名。

⑥malloc开辟的内存如果太小，想要换一块大一点的，可以调用relloc实现，但是new没有直观的方法来改变。

3、C中的struct和C++的类，C++的类是C中没有的，C中的struct可以在C++中等同类来使用，struct和类的差别是，struct的成员默认访问修饰符是public，而类默认是private。

4、C++支持重载，而C不支持重载，C++支持重载在于C++名字的修饰符与C不同，例如在C++中函数 int f(int) 经过名字修饰之后变为_f_int,而C是_f，所以C++才会支持不同的参数调用不同的函数。

5、C++中有引用，而C没有。那指针和引用有什么差别？

指针和引用的区别：

①指针有自己的一块空间，而引用只是一个别名。

②使用sizeof查看一个指针大小为4(32位)，而引用的大小是被引用对象的大小。

③指针可以是NULL，而引用必须被初始化且必须是对一个以初始化对象的引用。

④作为参数传递时，指针需要被解引用才可以对对象进行操作，而直接对引用的修改都会改变引用所指向的对象。

⑤指针在使用中可以指向其它对象，但是引用只能是一个对象的引用，不能被修改。

⑥指针可以有多级指针(**p)，而引用只有一级。

⑦指针和引用使用++运算符的意义不一样。

6、C++全部变量的默认连接属性是外连接，而C是内连接。

7、C中用const修饰的变量不可以用在定义数组时的大小，但是C++用const修饰的变量可以。（如果不进行&,解引用的操作的话，是存放在符号表的，不开辟内存）