检查 astd::vector是否已排序的最佳方法是什么？有没有比循环检查更快的东西v[i]<=v[i+1]？迭代器是否更快/更清洁？还是sort每次都调用实际上更好（尽管“v 已经排序”的情况很常见）？
我们可以安全地假设向量只包含 POD，通常是floats，有时double是 s 和ints。
向量的大小是非平凡的（通常是几千个项目）但不是极端的（不是千兆字节大小）。
有比循环检查 v[i]<=v[i+1] 更快的方法吗？
不。
如果这是您希望经常检查的内容，您可能希望创建一个包装类，该类保留一个“排序”标志，该标志以 False 开头，每当添加项目时设置为 False，并添加一个成员函数 sort() 设置排序后标志为True。
考虑多个 CPU 核心
这取决于您的平台和向量中的项目数。您必须进行基准测试才能找到最好的。
无法回答：有没有比循环检查 v[i]<=v[i+1] 更快的方法？
没有。
因为......现在的计算机有多个 cpu/cores/hyperthreading。因此，通过将检查工作拆分到多个线程来利用计算机中的并行性可能要快得多，因此每个 cpu 可以并行检查一个小范围。
最好通过库函数而不是自己实现它来做到这一点。新版本的库将利用并行性。因此，如果您选择 std::sort，您可能会发现，当您针对新的 STL 实现进行构建时，它们会为您并行执行操作，而您不必担心。我不知道是否有现成的 STL 版本已经可以做到这一点，但值得坚持使用库函数，这样当您升级到有此功能的版本时，这种优化就在那里，您无需进行任何更改.
std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()
当然我不知道你的问题领域，所以如果我说的不相关，请忽略我，但在我看来，如果我需要一个集合在我访问它时总是被排序，一个自然未排序的集合，如vector<T>可能不是最好的选择。
有比循环检查 v[i]<=v[i+1] 更快的方法吗？
您将需要检查任何值以查看它是否已排序，因此它不会比 O(n) 更快，除非您在变异向量时自己跟踪更改或使用已排序的数据结构。
还是每次都调用 sort 实际上更好（尽管“v 已经排序”的情况很常见）？
请记住，当列表已经排序（并且枢轴选择不正确）时，会发生快速排序最坏情况的行为。为了避免这种行为，您可能需要检查 std::stable_sort 作为替代品。
如果您希望列表非常接近排序，尝试修改插入排序可能会有所帮助。如果列表已经排序，它只会执行一次并告诉您。如果列表非常接近排序，它将很快排序。如果列表未排序，则在交换一些次数后中断排序并切换到快速排序（或 stable_sort）。
C++-11 在 <algorithm> 中包含 is_sorted。
有比循环检查 v[i]<=v[i+1] 更快的方法吗？
不。
但是，如果您要执行检查以决定是否对向量进行排序，那么如果您使用正确的排序算法，即 std::stable_sort 而不是 std::sort，则最好总是排序。
为了检查排序，您必须检查每个项目。所以 v[i]<=v[i+1] 是最快的检查。
正如其他人所指出的，确定排序状态的谓词是 O(n)。但是从你提到的排序标志，我有点想知道你是否不想要这样的东西：
我们的应用程序的基础库包括一个可以查询成员资格的容器类。这是一个简短的草图：
class ObjList {
public:
ObjList() {};
~ObjList() {};
bool isMember(const Item *);
void add(const Item *, bool sort = false);
private:
unsigned int last_sorted_d;
bool sorted_d;
unsigned int count_d;
Item *store_d;
};
isMember()对元素的排序范围使用二进制搜索，然后对排序范围之后的项目进行线性搜索。根据程序员的选择，插入可以触发或不触发某种项目。例如，如果你知道你将在一个紧密的循环中添加数千个项目，那么在最后插入之前不要排序。
上面只是一个草图，存储比指针数组更复杂，但你明白了。
如果在插入项目时使用二进制搜索来查找插入点，那么它永远不会被排序。
如果您的 C++ 标准库实现包含算法 is_sorted()，那么它是最佳选择。