为什么std :: sort和partial_sort需要随机访问迭代器？ [英] why do std::sort and partial_sort require random-access iterators?

问题描述

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

I was wondering why does the c++ standard require that std::sort should only take random-access iterators? I don't see the advantage, since both std::sort and std::list::sort have a complexity of N*log(N). Restricting std::sort to random-access iterators (RAI) seems to have made it necessary to write a separate function for lists with the same complexity.

这同样适用于 partial_sort ，其中列表的非RAI计数器部分直到今天都没有。

The same applies to partial_sort, where the non-RAI counter-part for list is simply missing to this day.

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

Is this design because people used variants of quick_sort to implement std::sort historically?

如果在RAI容器上写排序算法有优势，那么更好的做法是使 std :: sort 更一般，让RAI容器像 std :: vector 提供专门的 v.sort ？

If there is advantage for writing sort algorithms on RAI containers, would it better to make std::sort more general, and let RAI containers like std::vector provide specialized v.sort?

推荐答案

O（N * log（N））复杂性并不意味着容器是按顺序迭代的，按扫描顺序进行。为了使用顺序迭代器，将存储所有这些迭代器的 O（N）内存成本。

O(N*log(N)) complexity doesn't imply that the container is iterated in order, nor that the changes to it are only made in scan order. To use sequential iterators would come at a O(N) memory cost to store all of those iterators.

这篇关于为什么std :: sort和partial_sort需要随机访问迭代器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！