c++ - std::max_element() 有多聪明？

Question

假设我有一个 std::vector<int> :

std::vector<int> v;
[v is initialized]

我想得到 v 的最大元素。有一个算法可以做到这一点:

int max_value = *std::max_element(v.begin(), v.end());

到目前为止，一切顺利。

现在，假设v包含 10,000,000 个元素，其第 10 个元素等于 std::numeric_limits<int>::max() 。是std::max_element()将(不必要地)检查 v 的最后 9,999,990 个元素，或者它会认识到不能有大于 std::numeric_limits<int>::max() 的元素，从而在第 10 个元素之后停止？

Answer 1

我不能代表所有的实现，但是 libc++ 的 max_element 的实现不这样做。

这个想法有几个问题:

• 假设存在 numeric_limits 的专门化为序列元素的类型。 ( max_element 适用于任何可以订购的东西。)这可以通过一些模板元编程来解决。
• 有一个版本 max_element它需要一个比较谓词，而不仅仅是 operator < 。这种情况下的最大值是多少？
• 这要求序列中的类型是“相等可比较的”，而不仅仅是“小于可比较的”。
• (可能是最重要的)这将在循环内引入一个测试，枚举序列的元素，从而减慢其他人的算法速度。