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

Question

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

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

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

• 在某些情况下，我们会立即对 vector 进行排序，但在其他情况下我们不会(这是我们算法的错误情况)。
• 我们已尽可能使用“IsSorted”标志。

Answer 1

Is there something faster than a loop checking that v[i]<=v[i+1] ?

没有。

如果这是您希望经常检查的内容，您可能希望创建一个包装类，该类保留一个以 False 开头的“排序”标志，每当添加项目时将其设置为 False，并添加一个成员函数 sort( ) 在排序后将标志设置为 True。