为什么std:：sort和partial_sort需要随机访问迭代器？
我想知道为什么c标准要求std:：sort只接受随机访问迭代器？我不认为这有什么好处，因为std:：sort和std:：list:：sort的复杂性都是N*log（N）。将std:：sort限制为随机访问迭代器（RAI），似乎需要为具有相同复杂性的列表编写单独的函数。
同样的情况也适用于部分排序，其中列表的非RAI计数器部分至今仍然缺失。
这种设计是因为历史上人们使用了quick\u sort的变体来实现std:：sort？
如果在RAI容器上编写排序算法有好处，那么最好使std:：sort更通用，并让像std:：vector这样的RAI容器提供专门的v.sort？
共有2个答案
算法复杂性并不能说明一切。实际上，在C语言中（从形式的角度来看），它什么也没有说，因为你不能将N增长到无穷大（size\u t不是一个任意精度的数字），因此用C语言编写的每种排序算法（形式上）也是O（1）。
从实用的角度来看，std:：sort是qsort的孙子，它很可能是作为快速排序的一种变体实现的。
对数组使用合并排序将需要与数组大小成比例的额外存储（到下一个元素的链接），而对列表使用合并排序不需要任何额外空间，因为您可以重用节点中已经存在的链接（无论如何，它都会被排序破坏）。
在不知道要处理哪种容器的情况下编程的想法主要是一种幻觉，因此有两种不同的显式方法来有效地排序两种不同类型的容器本身并不被认为是不好的。
确实很烦人的是，std::排序不包含针对列表迭代器的专门化（我不是模板元编程大师，但这似乎很简单）。
O（N*log（N））复杂性并不意味着容器是按顺序迭代的，也不意味着对它的更改只是按扫描顺序进行的。使用顺序迭代器将以O（N）内存开销来存储所有这些迭代器。
-
我可以看到返回。但是现在已经添加到C++20标准中，为什么返回？cppreference指定： 返回值 等于last的迭代器。 这个选择背后的理性是什么？ 与相比，用例的优势是什么？
-
下面非常简单的代码在C 98中编译和链接时没有警告，但在C 11模式下会出现无法理解的编译错误。 标准=c 11的错误是，gcc版本4.9.0 20140302（实验）（gcc）： 带clang版本3.5（trunk 202594） 我一直在看中的代码，我不明白为什么它试图实例化。 为什么在C 11中需要复制构造函数std：：pair？ 注：上述代码是从不可复制映射的映射迭代器上不支持的等式运算符
-
但是，我想直接看到的缺点，所以我做了一个快速的实验： 基本上，我编写了两个函数和，它们分别使用和+生成0和5之间的随机数。 然后我用“老”的方式生成了960,000个（可被6整除）随机数，并记录了数字0-5的频率。然后我计算了这些频率的标准差。我所寻找的是一个尽可能低的标准偏差，因为如果分布是真正均匀的，那么就会发生这种情况。 我运行该模拟1000次，并记录每次模拟的标准偏差。我还记录了以毫秒为单
-
由于对std：：vector的大多数操作都需要/返回size\t，这就是我用于索引的类型。但现在我已经启用了所有编译器警告，以修复我知道存在的一些有符号/无符号转换问题，这条消息让我感到惊讶： 警告C4365：“参数”：从“size\u t”转换为“\uu w64 int”，有符号/无符号不匹配 它是由以下代码生成的： 我有很多其他类似的消息建议迭代器的算术运算符接受并返回。为什么不？修复所有这些
-
问题内容： 在回答中，用户说了这样的话：“带有ArrayLists的迭代器的一个大用例是，当您要在迭代时删除元素时”。 即使使用Java中的ArrayList的remove方法也可以实现。我的问题是为什么我们在ArrayList中需要迭代器？ 考虑以下代码： 谁能解释迭代器的意义？如果可以用代码解释我，那将是很棒的。 问题答案： 如前所述，迭代器用于迭代数组内容时要删除的内容。如果您不使用迭代器，
-
问题内容： 当您要依次遍历数字列表时，您将编写： 但是，如果要随机遍历范围（0..999）的数字列表怎么办？需要（在每个迭代中）随机选择在任何先前迭代中未选择的数字，并且需要对范围（0..999）内的所有数字进行迭代。 你知道该怎么做（聪明）吗？ 问题答案： 您可以习惯随机播放列表： 顺便说一句，在许多情况下，您将在其他编程语言中使用整数范围内的循环，则可以直接描述要在Python中迭代的“事物”