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

欢迎订阅，希望能点个赞！！！！

正在持续更新！！！！！欢迎探讨！！！

完整专栏地址：https://blog.nowcoder.net/zhuanlan/gmPWX0


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

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

也有相当一部分是本人在经历提前批以及秋招的过程中遇到和验证过的。


系列文章PDF下载地址：《最全C_C++及嵌入式软开面试题宝典.pdf》



71、vector与list的区别与应用？怎么找某vector或者list的倒数第二个元素

1.vector数据结构

vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。因此能高效的进行随机存取，时间复杂度为o(1);但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。连续存储结构：vector是可以实现动态增长的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。它与数组最大的区别就是vector不需程序员自己去考虑容量问题，库里面本身已经实现了容量的动态增长，而数组需要程序员手动写入扩容函数进形扩容。

2.list数据结构

list是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);但由于链表的特点，能高效地进行插入和删除。非连续存储结构：list是一个双链表结构，支持对链表的双向遍历。每个节点包括三个信息：元素本身，指向前一个元素的节点（prev）和指向下一个元素的节点（next）。因此list可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。

3、vector与list区别：


  • vector的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。
  • list的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。list是单向的，vector是双向的。vector中的迭代器在使用后就失效了，而list的迭代器在使用之后还可以继续使用。


为什么链表插入复杂度不是O(n)而是O(1)，不需要找到吗？

查找并不属于插入和删除操作范围内，你说的情况只能说查找元素的复杂度是O(n)。查找完元素之后才开始插入或删除，而由于链表本身的特性：插入时不用移动后续所有节点或者将整个链表拷贝到新的内存空间删除时可以用下一个节点覆盖当前节点，将问题转化成删除下一个节点所以插入和删除都是O(1)。

int mySize = vec.size();vec.at(mySize -2);

list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历：

72、STL vector的实现，删除其中的元素，迭代器如何变化？为什么是两倍扩容？释放空间？

1、size()函数返回的是已用空间大小，capacity()返回的是总空间大小，capacity()-size()则是剩余的可用空间大小。当size()和capacity()相等，说明vector目前的空间已被用完，如果再添加新元素，则会引起vector空间的动态增长。

2、由于动态增长会引起重新分配内存空间、拷贝原空间、释放原空间，这些过程会降低程序效率。因此，可以使用reserve(n)预先分配一块较大的指定大小的内存空间，这样当指定大小的内存空间未使用完时，是不会重新分配内存空间的，这样便提升了效率。只有当n>capacity()时，调用reserve(n)才会改变vector容量。resize()成员函数只改变元素的数目，不改变vector的容量。

3、resize()与reserve()

resize()设置大小（size）并初始化新元素;reserve()，设置容量（capacity），只是预留空间，而不会构造新的元素出来

1)空的vector对象，size()和capacity()都为0

2)当空间大小不足时，新分配的空间大小为原空间大小的2倍。

3)使用reserve()预先分配一块内存后，在空间未满的情况下，不会引起重新分配，从而提升了效率。

4)当reserve()分配的空间比原空间小时，是不会引起重新分配的。

5)resize()函数只改变容器的元素数目，未改变容器大小。

6)用reserve(size_type)只是扩大capacity值，这些内存空间可能还是“野”的，如果此时使用“[ ]”来访问，则可能会越界。而resize(size_type new_size)会真正使容器具有new_size个对象。

4、vector扩容方式

1)不同的编译器，vector有不同的扩容大小。在vs下是1.5倍，在GCC下是2倍；

2)空间和时间的权衡。简单来说，空间分配的多，平摊时间复杂度低，但浪费空间也多。

3)使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1,2)

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

5、如何释放空间：

由于vector的内存占用空间只增不减，比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。

如果需要空间动态缩小，可以考虑使用deque。如果vector，可以用swap()来帮助你释放内存。

vector(Vec).swap(Vec);//将Vec的内存空洞清除；

vector().swap(Vec);//清空Vec的内存；

73、容器内部删除一个元素

1、顺序容器

erase迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效(list除外)，所以不能使用erase(it++)的方式，但是erase的返回值是下一个有效迭代器；

It = c.erase(it);

2、关联容器

erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器；

c.erase(it++)

74、STL迭代器如何实现

1.迭代器是一种抽象的设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器，除此之外，STL中迭代器一个最重要的作用就是作为容器与STL算法的粘合剂。

2.迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器内部必须保存一个与容器相关联的指针，然后重载各种运算操作来遍历，其中最重要的是*运算符与->运算符，以及++、--等可能需要重载的运算符重载。这和C++中的智能指针很像，智能指针也是将一个指针封装，然后通过引用计数或是其他方法完成自动释放内存的功能。

3.最常用的迭代器的相应型别有五种：value type、difference type、pointer、reference、iterator catagoly;

75、set与hash_set的区别

1.set底层是以RB-Tree实现，hash_set底层是以hash_table实现的；

2.RB-Tree有自动排序功能，而hash_table不具有自动排序功能；

3.set和hash_set元素的键值就是实值；

4.hash_table有一些无法处理的型别；