Fintech砖

2023-07-28 23:15 兴业银行_金融科技部_Fintech金融科技岗

关注

【11】C++岗位求职面试八股文系列文章（语言基础）

第一篇：语言基础

第二篇：设计模式

第三篇：数据库

第四篇：计算机网络

第五篇：操作系统

第六篇：LInux

第七篇：数据结构

第八篇：智力题

[201]谓词概念

[202]内建函数对象

链接内建函数对象：仿函数（算术、逻辑、关系仿函数）

[203]STL 容器用过哪些，查找的时间复杂度是多少，为什么？

STL中常用的容器有vector、deque、list、 map、set、multimap、multiset、unordered_map、unordered_set、 stack、queue等。容器底层实现方式及时间复杂度分别如下：vector采用一维数组实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N)查看: O(1)删除: O(N)deque采用双向队列实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N)查看: O(1)删除: O(N)list采用双向链表实现，元素存放在堆中，不同操作的时间复杂度为：插入: O(1)查看: O(N)删除: O(1)map、set、multimap、multiset上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种（自平衡二叉搜索树）。不同操作的时间复杂度近似为:插入: O(logN)查看: O(logN)删除: O(logN)unordered_map、unordered_set、unordered_multimap、 unordered_multiset上述四种容器采用哈希表实现，不同操作的时间复杂度为：插入: O(1)，最坏情况O(N)查看: O(1)，最坏情况O(N)删除: O(1)，最坏情况O(N)注意：容器的时间复杂度取决于其底层实现方式。

[204]迭代器用过吗？什么时候会失效

总结：迭代器失效分三种情况考虑，也是非三种数据结构考虑，分别为数组型，链表型，树型数据结构。数组型数据结构：对于序列容器vector，deque，该数据结构的元素是分配在连续的内存中，insert和erase操作，都会使得删除点和插入点之后的元素挪位置，所以，插入点和删除掉之后的迭代器全部失效，也就是说insert(*iter)(或erase(*iter))，然后在iter++，是没有意义的。解决方法：erase(*iter)的返回值是下一个有效迭代器的值。 iter =cont.erase(iter);所以不能使用erase(iter++)的方式，还好erase，insert方法可以返回下一个有效的iterator。

链表型数据结构：对于list型的数据结构，使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.解决办法两种，erase(*iter)会返回下一个有效迭代器的值，或者erase(iter++).

树形数据结构：使用红黑树来存储数据，插入不会使得任何迭代器失效；删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器. erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。不能使用返回下一个有效迭代器值（因为不连续也不连接）

[205]说一下STL中迭代器的作用，有指针为何还要迭代器？

迭代器的作用：指向元素，读取值，改变指向（1）用于指向顺序容器和关联容器中的元素（2）通过迭代器可以读取它指向的元素（3）通过非const迭代器还可以修改其指向的元素

迭代器和指针的区别迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，重载了指针的一些操作符，-->、++、--等。迭代器封装了指针，是一个”可遍历STL（ Standard Template Library）容器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，--等操作。

迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

迭代器产生的原因Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果

[206]说说 STL 迭代器是怎么删除元素的

这是主要考察迭代器失效的问题。对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器；对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可；对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。

容器适配器不支持迭代器

[207]说说 STL 中 resize 和 reserve 的区别

（1）capacity：该值在容器初始化时赋值，指的是容器能够容纳的最大的元素的个数。还不能通过下标等访问，因为此时容器中还没有创建任何对象。（2）size：指的是此时容器中实际的元素个数。可以通过下标访问0-(size-1)范围内的对象。

resize和reserve区别主要有以下几点：（1）resize既分配了空间，也创建了对象；reserve表示容器预留空间，但并不是真正的创建对象，需要通过insert（）或push_back（）等创建对象。（2）resize修改size大小；reserve修改capacity大小（3）两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为0）；reserve只带一个参数，表示容器预留的大小。

当resize(len)中len>v.capacity()，则数组中的size=len，capacity动态扩容增大
当resize(len)中len<=v.capacity()，则数组中的size设置为len，⽽capacity不变;

如果reserve(len)的值 > 当前的capacity()，那么会᯿新分配⼀块能存len个象的空间，然后把之前的对象通过copy construtor复制过来，销毁之前的内存; capacity=len,size不变

当reserve(len)中len<=当前的capacity()，则数组中的capacity不变，size不变，即不对容器做任何改变。

使用reserve()预先分配一块内存后，在空间未满的情况下，不会引起重新分配，从而提升了效率。3. Reverse的空间小于size个数，size也不变4sizeof(vector)=16 分配了四个指针 sizeof 计算的是在栈中分配的内存大小！！！_A allocator;iterator _First, _Last, _End;

[208]Vector如何释放空间

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

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

[209]说说 STL 容器动态链接可能产生的问题？

可能产生的问题容器是一种动态分配内存空间的一个变量集合类型变量。在一般的程序函数里，局部容器，参数传递容器，参数传递容器的引用，参数传递容器指针都是可以正常运行的，而在动态链接库函数内部使用容器也是没有问题的，但是给动态库函数传递容器的对象本身，则会出现内存堆栈破坏的问题。产生问题的原因容器和动态链接库相互支持不够好，动态链接库函数中使用容器时，参数中只能传递容器的引用，并且要保证容器的大小不能超出初始大小，否则导致容器自动重新分配，就会出现内存堆栈破坏问题。

[210] 说说 map 和 unordered_map 的区别？底层实现

map实现机理map内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。

unordered_map实现机理unordered_map内部实现了一个哈希表（也叫散列表），通过把关键码值映射到Hash表中一个位置来访问记录，查找时间复杂度可达O（1），其中在海量数据处理中有着广泛应用。因此，元素的排列顺序是无序的。

[211]说说 vector 和 list 的区别，分别适用于什么场景？

vector和list区别在于底层实现机理不同，因而特性和适用场景也有所不同。

vector：一维数组特点：元素在内存连续存放，动态数组，在堆中分配内存，元素连续存放，有保留内存，如果减少大小后内存也不会释放。优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以它的查找效率高，其时间复杂度O(1)。缺点：由于开辟一段连续的空间，所以插入删除会需要对数据进行移动比较麻烦，时间复杂度O（n），另外当空间不足时还需要进行扩容。

list：双向链表特点：元素在堆中存放，每个元素都是存放在一块内存中，它的内存空间可以是不连续的，通过指针来进行数据的访问。优点：底层实现是循环双链表，当对大量数据进行插入删除时，其时间复杂度O(1)。缺点：底层没有连续的空间，只能通过指针来访问，所以查找数据需要遍历其时间复杂度O（n），没有提供[]操作符的重载。

应用场景vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

[212]数据结构的四种存储方式

顺序存储、链式存储、索引存储、散列存储

[213]数据结构的顺序存储和链式存储

[214]简述 vector 的实现原理

vector底层实现原理为一维数组（元素在空间连续存放）。1.新增元素Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素。插入新的数据分在最后插入push_back和通过迭代器在任何位置插入，这里说一下通过迭代器插入，通过迭代器与第一个元素的距离知道要插入的位置，即int index=iter-begin()。这个元素后面的所有元素都向后移动一个位置，在空出来的位置上存入新增的元素。

2.删除元素删除和新增差不多，也分两种，删除最后一个元素pop_back和通过迭代器删除任意一个元素erase(iter)。通过迭代器删除还是先找到要删除元素的位置，即int index=iter-begin();这个位置后面的每个元素都想前移动一个元素的位置。

erase不释放内存只初始化成默认值。删除全部元素clear：只是循环调用了erase，所以删除全部元素的时候，clear不释放内存。内存是在析构函数中释放的。

3.迭代器iteraotr迭代器iteraotr是STL的一个重要组成部分,通过iterator可以很方便的存储集合中的元素.STL为每个集合都写了一个迭代器, 迭代器其实是对一个指针的包装,实现一些常用的方法,如++,--,!=,==,*,->等, 通过这些方法可以找到当前元素或是别的元素. vector是STL集合中比较特殊的一个,因为vector中的每个元素都是连续的,所以在自己实现vector的时候可以用指针代替。

将4移动到最后，最后用6替换

Remove前开后闭吧2添加到3的后面，将2换为3，其余不变采用remove一般情况下不会改变容器的大小，而pop_back()与erase()等成员函数会改变容器的大小size。

[215]说一下STL每种容器对应的迭代器

[216]简述 STL 中的 map 的实现原理

map是关联式容器，它们的底层容器都是红黑树。map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。

map的特性如下（1）map以RBTree作为底层容器；（2）所有元素都是键+值存在；（3）不允许键重复；（4）所有元素是通过键进行自动排序的；（5）map的键是不能修改的，但是其键对应的值是可以修改的。

[217]为什么insert之后，map、set以前保存的iterator不会失效？

因为 map 和 set 底部使⽤红⿊树实现，插⼊和删除的时间复杂度是 O(logn)，⽽向 vector 这样的序列容器插⼊和删除的时间复杂度是 O(N)，不涉及内存的拷贝和移动

[218]C++ 的 vector 和 list中，如果删除末尾的元素，其指针和迭代器如何变化？若删除的是中间的元素呢？

1.vector和list特性vector特性动态数组。元素在内存连续存放。随机存取任何元素都在常数时间完成。在尾端增删元素具有较大的性能（大部分情况下是常数时间）。

2list特性双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

3vector增删元素对于vector而言，删除某个元素以后，该元素后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。It = c.erase(it);

4list增删元素对于list而言，删除某个元素，只有“指向被删除元素”的那个迭代器失效，其它迭代器不受任何影响。所以既可以返回下一个有效迭代器位置，也可以删除之前，先迭代器加加。

关联容器(关联式容器，比如map、set、multimap、multiset等)erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器；c.erase(it++)

[219]请你来说一下 map 和 set 有什么区别，分别又是怎么实现的？

set是一种关联式容器，其特性如下：（1）set以RBTree作为底层容器（2）所得元素的只有key没有value，value就是key（3）不允许出现键值重复（4）所有的元素都会被自动排序（5）不能通过迭代器来改变set的值，因为set的值就是键，set的迭代器是const的

map和set一样是关联式容器，其特性如下：（1）map以RBTree作为底层容器（2）所有元素都是键+值存在（3）不允许键重复（4）所有元素是通过键进行自动排序的（5）map的键是不能修改的，但是其键对应的值是可以修改的（6）能通过迭代器来改变map的值，综上所述，map和set底层实现都是红黑树；map和set的区别在于map的值不作为键，键和值是分开的。