为什么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屋!