STL相关面试问题

1. set与优先队列区别在哪？set如何实现对结构体排序？

2.list_1 插入 list_2 ，list_2中的节点不知道数量，如何插入最好？

3. vector 插入1000个数据，用什么办法最好？

4. linux系统中搜索某个 .c 文件 用什么办法？

reply：

1. set 与 优先队列的区别：

优先队列定义： priority_queue

type：数据类型；

Container：容器类型（必须是用数组实现的容器，比如vector，deque，但不能用list，stl中默认 vector）；

Functional：是比较的方式。

当需要自定义数据类型时，传入上述参数，使用基本数据类型时，只需要传入数据类型，默认排序方式是大顶堆。

自定义比如：

//升序队列----小顶堆
priority_queue ,greater > q;
//降序队列----大顶堆 【默认】
priority_queue ,less >q;

• 什么是大顶堆、什么是小顶堆？

首先，堆的本质是一颗完全二叉树：

【1】每个根结点的值都大于或等于其左右孩子结点的值，成为大顶堆；

【2】每个根节点的值都小于或等于其左右孩子结点的值，成为小顶堆；

• 什么是堆排序算法？

堆排序算法就是利用堆（大顶堆或小顶堆）进行排序的方法；

        将待排序的序列构造成一个大顶堆，此时将整个序列中最大的根节点移走。此时，将堆中的末尾元素放在根节点的位置上，然后再根据大顶堆的思想重新构造一个堆。如此反复执行，每次移除的结点值便可组成一个降序序列了。

 

优先队列与队列的基本操作相同：

        top访问队头元素；

        empty队列是否为空；

        size返回队列内元素个数；

        push插入元素到队尾并且排序！！！！

        emplace 原地构造一个元素 插入队列中

        pop弹出队头元素；

        swap 交换内容；

so,set与priority_queue的区别在哪？

set是关联式容器，通过红黑树实现自动排序，默认是升序排序，不允许重复值出现；

priority_queue是序列式容器，尾部插入元素，头部弹出元素，与队列不同在于，元素弹出的顺序是按照从大到小弹出，因为优先队列是通过堆排序算法进行排序的，默认是大顶堆，允许重复值出现，不提供迭代器。

set如何实现对结构体排序？

在结构体中重写 < 操作符

2/3. vector 插入、list插入问题

 即：vector中插入大量连续的数据时，如果预知数据量大小，可以通过resize来调整原先vector的空间大小，同时 利用 赋值 = ，可以减少耗时。

对于list来说，可以通过 遍历list然后insert插入，但还可以通过成员方法 splice 来进行插入，且效率较高，耗时较少。

4. linux中要查找某个文件？

        Linux下查找文件可以用whereis、locate或者find命令。如果是快速搜索文件，最好是用whereis或者locate命令，它们的查找速度要比find命令快很多，这是因为在Linux系统中有个数据库，记录了系统内的所有文件，而whereis和locate命令就是在这个数据库中查找，并没有实际查找硬盘，而数据库查找往往是非常快的；而find命令是直接查找硬盘，如果硬盘文件比较多，就比较费时间。----转自Linux中在当前目录下查找某个文件_土木桩的博客-CSDN博客_linux 搜索某个文件

注意：

1. grep命令用于在一个或多个文件中查找关键字（可以是字符串也可以是正则表达式），而不是查找文件；

2. whereis 和 locate 命令 的数据库是一天更新一次，有时候会找到已经删除的文件，有的时候会找不到刚刚创建的文件，出现这种情况  可以用 find 命令来查找。

find用法：【. 表示当前目录】

find + . + -name + “ 文件名”

不明确文件名称时，可以用通配符

find + . + -name +“文件*”

在当前文件夹中查找 文件名含有“ ”内部字符串的文件

find+ / -name 文件 在根目录下查找文件