为什么std :: sort和partial_sort需要随机访问迭代器？

Question

我想知道为什么c ++标准要求std::sort只应该采用随机访问迭代器？我没有看到优势,因为std :: sort和std :: list :: sort都有复杂性N*log(N).限制std::sort随机访问迭代器(RAI)似乎已经使得必须为具有相同复杂性的列表编写单独的函数.

这同样适用于partial_sort,直到今天根本没有列出非RAI对应部分的部分.

这个设计是因为人们使用历史quick_sort实现的变体std::sort吗？

如果在RAI容器上编写排序算法是有好处的,那么更好地制作std::sort更通用的,并让RAI容器std::vector提供专门的v.sort吗？

Answer 1

O(N*log(N))复杂性并不意味着容器按顺序迭代，也不意味着仅按扫描顺序对其进行更改。使用顺序迭代器会产生O(N)存储所有这些迭代器的内存成本。