Skip to main content
 首页 » 编程设计

c++之std::max_element() 有多聪明

2024年05月22日13cyq1162

假设我有一个 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 个元素之后停止?

请您参考如下方法:

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

这个想法有几个问题:

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