为什么需要std :: minmax_element？

为什么我们需要std::min_element和std::max_element的组合版本std::minmax_element？这仅仅是为了节省比较，还是其他好处？为什么需要std :: minmax_element？

2015-12-02 Chen OT

std::min_element和std::max_element需要在返回之前遍历整个容器。如果你使用std::min_element然后std::max_element那么这是两个遍历，而如果你使用std::minmax_element那么你只需要一个。

所以是的，这只是保存比较的“正义”，但我认为减少检索所需数据而不损失清晰度所需的工作量是非常值得的。

2015-12-02 10:22:35 TartanLlama

还要注意'std :: minmax_element'找到_last_最大的元素，而'std :: max_element'找到_first_最大的元素。 [来源]（http://en.cppreference.com/w/cpp/algorithm/minmax_element） –

是的。 O（n）有点贵。保存一个遍历看起来值得。 –

@ Konrad'Zegis'很高兴知道，谢谢。 – Quentin

它列出了两点不同：

这种算法是从std::make_pair(std::min_element(), std::max_element())不同，不仅在效率，而且在这个算法找到最后最大的元素，而std::max_element发现第一最大的元素。

所提到的效率增益，是因为std::minmax_element只需要一次处理的数据，而同时运行std::min_element和std::max_element需要两次处理的数据。

2015-12-02 10:26:55

这不仅仅是处理一次数据，它还可以通过这种方式执行更少的比较（3n/2而不是2n）。顺便说一下，在某些情况下，它比调用min_element和max_element要慢（例如，由于分支预测更差，所以在x86上是int或double随机顺序的数组）。 –

回答