首页 > 试题广场 >

下列关于stl的说法正确的是（）

[不定项选择题]

下列关于stl的说法正确的是（）

map的迭代器的key是const类型，无法对其进行修改

stl的排序算法一般比较传统的快速排序快是因为其选取中值的算法好

list是双链表实现，插入的元素的复杂度为O(1)

vector的大小会增大或者减少，但容量只会增大不会减少

查看答案及解析

推荐

爱豆儿

可以调用shrink_to_fit来要求vector将超出当前大小的多余内存退回给系统。然而：调用shrink_to_fit只是一个请求，标准库并不保证退还内存。

编辑于 2017-08-11 14:01:15 回复(0)

不舌者说

http://m.blog.csdn.net/msdnwolaile/article/details/52461643

发表于 2017-08-12 15:35:42 回复(0)

走位崴了脚

B选项快速排序跟中值没关系

编辑于 2019-05-29 09:55:06 回复(0)

炮祺泡祺君

std::sort先采用快排，若递归深度过大，则转用堆排，与选取中值无关，故B错；std::vector可以调用shrink_to_fit()归还多余的空间，故D错，选AC。

编辑于 2018-11-28 22:23:26 回复(2)

哈迪斯龙

关于D：

有一个间接缩减vector容量的小窍门：采用swap让两个同期交换内容后，两者的容量也会互换：

有vector<int> v1;//经过大起大落、删删减减之后，原先有上万条内容，现在只剩下寥寥数十条

它的size不大，但是capcity由于只是删除元素，仍然保持者上万条的规模

vector<int>v2(v1);//v2中保存的是v1中的副本，但是v2是按需构建的，也就是说v2的size和它的capcity是比较相配的。

v1.swap(v2)//这样一来v1和v2不仅交换了内容（其实两者的内容是完全一模一样的），而且把capcity都交换了。

发表于 2018-05-27 14:06:01 回复(2)

李正浩大魔王

STL396页到397页有介绍sort排序和部分SGI STL源码

步骤1、先用快速排序

步骤2、如果排序过程中分割恶化（递归层次过深），改用堆排序，保持时间复杂度在O（nlogn）

步骤3、最后一趟采用插入排序（插入排序在面对几乎有序的数组时表现良好）

发表于 2018-09-19 16:14:45 回复(0)

叶赫那拉坤

我想知道D为什么不对，请赐教。

vector在增加删除元素的时候会导致size变化，但是capacity只会在容量不够时扩容，不会减小。有人能帮忙解答该项为什么不对么

发表于 2017-09-02 10:27:47 回复(3)

Pillar_c

插入的时间不算查找的。。

发表于 2017-08-11 16:34:36 回复(3)

牛客151847192号

调用vector，使用swap交换分区函数，向量大小就可以减小

发表于 2023-04-04 09:12:39 回复(0)

不要卷了1号

STL的sort算法，数据量大时采用QuickSort快排算法，分段归并排序。一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。如果递归层次过深，还会改用HeapSort堆排序。

发表于 2022-06-10 15:12:44 回复(0)

Tudorlin

c++11中提供了shrink_to_fit(); 会将vector的容量调整到实际大小

发表于 2024-01-05 19:11:29 回复(0)

杉杉来啦

快速排序方法中，选取中值以及待排序列是否基本有序都会影响。
但是快速排序快并不是因为选取中值的算法好，而是因为其平均情况下的时间复杂度可达到O(n * log 2 n)

发表于 2023-06-30 13:10:44 回复(0)

我们为什么在这？

list广义表

发表于 2021-03-23 01:05:15 回复(0)

Lei.Ch

B选项：
快速排序方法中，选取中值以及待排序列是否基本有序都会影响。
但是快速排序快并不是因为选取中值的算法好，而是因为其平均情况下的时间复杂度可达到O(n * log 2 n)

发表于 2021-03-05 15:33:50 回复(0)

圣嘉然之力

stl的sort使用的是内省排序：一开始使用快速排序，递归深度过高转换成堆排序

发表于 2017-08-17 18:03:31 回复(0)

提交观点

问题信息

C++工程师 2017 搜狗 C++

来自：搜狗2017校招C++...

上传者：阿奻_

难度：

15条回答 1010收藏 7841浏览

下列关于stl的说法正确的是（）

问题信息

热门推荐

相关试题