检查向量是否已排序的最佳算法

检查a std::vector是否排序的最佳方法是什么？有没有比循环检查更快的东西v[i]<=v[i+1]？迭代器更快/更清洁吗？或者sort每次调用实际上更好(虽然"v已经排序"的情况很常见)？

我们可以安全地假设向量只包含POD,通常是floats,有时double是s和ints.

向量的大小是非平凡的(通常是几千个项目),但不是极端的(不是千兆字节大小).

在某些情况下,我们会在之后立即对矢量进行排序,但是还有其他情况我们不会(这是我们算法的错误情况).

我们已尽可能使用标志"IsSorted".

Deestan.. 28

有没有比循环检查v [i] <= v [i + 1]更快的东西？

没有.

如果这是您希望经常检查的内容,您可能希望创建一个包装类,它保持一个以"False"开头的"sorted"标志,每当添加一个项目时都设置为False,并添加一个成员函数sort()来设置排序后标志为True.

1> Deestan..：

---

有没有比循环检查v [i] <= v [i + 1]更快的东西？

没有.

如果这是您希望经常检查的内容,您可能希望创建一个包装类,它保持一个以"False"开头的"sorted"标志,每当添加一个项目时都设置为False,并添加一个成员函数sort()来设置排序后标志为True.

2> ShreevatsaR..：

---

最好的方法是使用std::is_sorted:

is_sorted(v.begin(), v.end())

:-)

---

C++ 11现在也有`is_sorted`

---

这是SGI扩展.我有GCC而不是VC++ 7.没错,它只是复制粘贴!无论如何,我必须将基于迭代器的方法与基于索引的方法进行对比......然后我们就能说它是"最好的方法".:)

3> Scott Langha..：

---

考虑多个Cpu核心

这取决于您的平台和向量中的项目数.你必须进行基准测试才能找到最好的东西.

这是不可能回答的:有没有比循环检查v [i] <= v [i + 1]更快的东西？
没有.

因为...计算机现在有几天有多个cpus/cores /超线程.因此,通过将检查工作分成多个线程来利用计算机中的并行性可能要快得多,因此每个cpu可以并行检查小范围.

最好通过库函数来实现,而不是自己实现.新版本的库将利用并行性.所以,如果你选择std :: sort,你可能会发现当你构建新的STL实现时,他们会为你并行执行操作,而不必担心它.我不知道是否有现成的STL版本可以做到这一点,但是值得坚持使用库函数,这样当你升级到这样的版本时,这个优化适合你而不需要做任何修改.

4> newacct..：

---

std::adjacent_find(v.begin(), v.end(), std::greater()) == v.end()

5> endian..：

---

当然我不知道你的问题领域,所以如果我说的不相关,请忽略我,但在我看来,如果我要求一个集合总是在我访问它时被排序,一个自然未分类的集合,如vector可能不是最好的选择.

6> Jasper Bekke..：

---

有没有比循环检查v [i] <= v [i + 1]更快的东西？

您将需要检查任何值以查看它是否已排序,因此它不会比O(n)快得多,除非您在改变向量或使用已经排序的数据结构时自己跟踪更改.

或者每次调用sort实际上更好(尽管"v已经排序"的情况很常见)？

请记住,当列表已经排序(并且错误地选择了轴)时,会发生快速排序最坏情况行为.为避免此类行为,您可能需要检查std :: stable_sort作为替换.