std :: sort检查一个向量是否已经排序？ [英] Does std::sort check if a vector is already sorted?

问题描述

我相信 std :: sort 不能保证已经排序的列表上的O（n）性能。但是，我想知道是否你的知识任何实现的STL（GCC，MSVC等）使 std :: is_sorted 检查之前执行排序算法？

在已排序容器上运行 std :: sort 时，期望（当然没有保证）？

我发布了一些基准 GCC 4.5与C ++ 0x在我的博客上启用。结果如下：

解决方案

然而，我看到了libstdc ++在linux上的性能比较，而libc ++是由Apple / LLVM开发的新的C ++库。这两个库对排序或反向排序的数据（比随机列表快得多）非常有效，新的库比旧的更快，并识别更多的模式。

为了确保你应该考虑做自己的基准。

I believe that the C++ standard for std::sort does not guarantee O(n) performance on a list that's already sorted. But still, I'm wondering whether to your knowledge any implementations of the STL (GCC, MSVC, etc) make the std::is_sorted check before executing the sort algorithm?

Asked another way, what performance can one expect (without guarantees, of course) from running std::sort on a sorted container?

Side note: I posted some benchmarks for GCC 4.5 with C++0x enabled on my blog. Here's the results:

解决方案

Implementations are free to use any efficient sorting algorithm they want so this is highly implementation dependant

However I have seen a performance comparison of libstdc++ as used on linux and against libc++ the new C++ library developed by Apple/LLVM. Both these libraries are very efficient on sorted or reverse sorted data (much faster then on a random list) with the new library being considerable faster then the old and recognizing many more patterns.

To be certain you should consider doing your own benchmarks.

这篇关于std :: sort检查一个向量是否已经排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！