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

Question

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

这同样适用于 partial_sort，其中列表的非 RAI 对应部分 is simply missing直到今天。

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

如果在 RAI 容器上编写排序算法有优势，是否最好使 std::sort 更通用，并让 RAI 容器像 std::vector提供专门的v.sort?

Answer 1

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