c++ - 与 min_element 和 max_element 一起使用 minmax_element 是否有任何效率优势？

Question

std::minmax_element :返回一个对，该对由指向最小元素的迭代器作为第一个元素和指向最大元素的迭代器作为第二个元素组成。

std::min_element :返回指向 [first, last) 范围内最小元素的迭代器。

std::max_element :返回指向 [first, last) 范围内最大元素的迭代器。

---

std::minmax_element 是否使用完整列表的排序 来实现此目的？

从 std::minmax_element 处理返回对的开销是否足够？

Answer 1

您不必担心 std::minmax_element 进行任何排序。它以遍历的确切方式离开范围。它更高效的原因是它可以在一次遍历中同时找到最大值和最小值，而当分别查找最大值和最小值时，您必须进行两次完整遍历。

std::minmax_element 的复杂度为 max(floor(3/2(N−1)), 0) 其中 std::max_element 和 std::min_element 都是 max(N-1,0) 所以使用 std::minmax_element< 的操作减少了大约 25%/

还有一个区别，std::minmax_element 找到最后一个最大的元素，而 std::max_element 找到第一个最大的元素。

因此，如果您需要找到一个范围的最小值和最大值，那么您应该使用 std::minmax_element。如果您只需要最小值或最大值，那么您应该使用专用版本。使用即将推出的 C++17 标准和结构化绑定(bind)，处理来自 std::minmax_element 的返回值将变得更加容易。你将能够写

auto [min, max] = std::minmax_element(...);

现在该对的第一个元素存储在 min 中，第二个元素存储在 max 中。