c++ - 检查 vector 是否已排序的最佳算法

检查std::vector排序的最佳方法是什么？有比循环检查v[i]<=v[i+1]更快的方法吗？迭代器是否更快/更干净？还是每次都只调用sort更好(尽管“v已经排序”的情况很常见)？

我们可以安全地假设 vector 仅包含POD，通常是float，有时还包括double和int。

vector 的大小是不平凡的(通常是几千个项目)，但不是极端的(不是千兆字节大小)。

在某些情况下，我们会立即对 vector 进行排序，但是在其他情况下，我们不进行排序(这是算法的错误情况)。

我们已经尽可能使用了“IsSorted”标志。

最佳答案

考虑多个Cpu核心

这取决于您的平台和 vector 中的项目数。您必须进行基准测试才能找到最好的。

无法回答:是否有比循环检查v [i] 没有。

因为...现在，如今的计算机有多个cpus/核心/超线程。因此，通过将检查工作拆分为多个线程来利用计算机中的并行性可能会快很多，因此每个cpu可以并行检查一个小的范围。

最好是通过库函数而不是自己实现它。新版本的库将利用并行性。因此，如果您使用std::sort进行新的STL实现时可能会发现，它们将为您并行执行操作，而您不必担心。我不知道是否已经有现成的STL版本可以执行此操作，但是值得坚持使用库函数，因此当您升级到可以使用的STL版本时，可以进行此优化而无需进行任何更改。