Difference between revisions of "cpp/algorithm/ranges/minmax"

Latest revision as of 10:34, 28 August 2023

Defined in header `<algorithm>`
Call signature
template< class T, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<const T*, Proj>> Comp = ranges::less > constexpr ranges::minmax_result<const T&> minmax( const T& a, const T& b, Comp comp = {}, Proj proj = {} );	(1)	(since C++20)
template< std::copyable T, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<const T*, Proj>> Comp = ranges::less > constexpr ranges::minmax_result<T> minmax( std::initializer_list<T> r, Comp comp = {}, Proj proj = {} );	(2)	(since C++20)
template< ranges::input_range R, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > requires std::indirectly_copyable_storable<ranges::iterator_t<R>, ranges::range_value_t<R>*> constexpr ranges::minmax_result<ranges::range_value_t<R>> minmax( R&& r, Comp comp = {}, Proj proj = {} );	(3)	(since C++20)
Helper types
template< class T > using minmax_result = ranges::min_max_result<T>;	(4)	(since C++20)

Returns the smallest and the greatest of the given projected values.

1) Returns references to the smaller and the greater of a and b.

2) Returns the smallest and the greatest of the values in the initializer list r.

3) Returns the smallest and the greatest of the values in the range r.

The function-like entities described on this page are niebloids, that is:

Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to argument-dependent lookup.
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions.

2,3) {s, l}, where s and l are respectively the smallest and largest values in r, according to their projected value. If several values are equivalent to the smallest and largest, returns the leftmost smallest value, and the rightmost largest value. If the range is empty (as determined by ranges::distance(r)), the behavior is undefined.

[edit] Complexity

1) Exactly one comparison and two applications of the projection.

2,3) At most 3 / 2 * ranges::distance(r) comparisons and twice as many applications of the projection.

[edit] Possible implementation

struct minmax_fn
{
    template<class T, class Proj = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = ranges::less>
    constexpr ranges::minmax_result<const T&>
         operator()(const T& a, const T& b, Comp comp = {}, Proj proj = {}) const
    {
        if (std::invoke(comp, std::invoke(proj, b), std::invoke(proj, a)))
            return {b, a};
 
        return {a, b};
    }
 
    template<std::copyable T, class Proj = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = ranges::less>
    constexpr ranges::minmax_result<T>
        operator()(std::initializer_list<T> r, Comp comp = {}, Proj proj = {}) const
    {
        auto result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
        return {*result.min, *result.max};
    }
 
    template<ranges::input_range R, class Proj = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
    requires std::indirectly_copyable_storable<ranges::iterator_t<R>,
                                               ranges::range_value_t<R>*>
    constexpr ranges::minmax_result<ranges::range_value_t<R>>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        auto result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
        return {std::move(*result.min), std::move(*result.max)};
    }
};
 
inline constexpr minmax_fn minmax;

[edit] Notes

For overload (1), if one of the parameters is a temporary, the reference returned becomes a dangling reference at the end of the full expression that contains the call to minmax:

int n = 1;
auto p = std::ranges::minmax(n, n + 1);
int m = p.min; // ok
int x = p.max; // undefined behavior
 
// Note that structured bindings have the same issue
auto [mm, xx] = std::ranges::minmax(n, n + 1);
xx; // undefined behavior

[edit] Example

Run this code

#include <algorithm>
#include <array>
#include <iostream>
#include <random>
 
int main()
{
    namespace ranges = std::ranges;
 
    constexpr std::array v{3, 1, 4, 1, 5, 9, 2, 6, 5};
 
    std::random_device rd;
    std::mt19937_64 generator(rd());
    std::uniform_int_distribution<> distribution(0, ranges::distance(v)); // [0..9]
 
    // auto bounds = ranges::minmax(distribution(generator), distribution(generator));
    // UB: dangling references: bounds.min and bounds.max have the type `const int&`.
 
    const int x1 = distribution(generator);
    const int x2 = distribution(generator);
    auto bounds = ranges::minmax(x1, x2); // OK: got references to lvalues x1 and x2
 
    std::cout << "v[" << bounds.min << ":" << bounds.max << "]: ";
    for (int i = bounds.min; i < bounds.max; ++i)
        std::cout << v[i] << ' ';
    std::cout << '\n';
 
    auto [min, max] = ranges::minmax(v);
    std::cout << "smallest: " << min << ", " << "largest: " << max << '\n';
}

Possible output:

v[3:9]: 1 5 9 2 6 5 
smallest: 1, largest: 9

[edit] See also

ranges::min (C++20)	returns the smaller of the given values (niebloid)[edit]
ranges::max (C++20)	returns the greater of the given values (niebloid)[edit]
ranges::minmax_element (C++20)	returns the smallest and the largest elements in a range (niebloid)[edit]
ranges::clamp (C++20)	clamps a value between a pair of boundary values (niebloid)[edit]
minmax (C++11)	returns the smaller and larger of two elements (function template) [edit]

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

a, b	-	the values to compare
r	-	a non-empty range of values to compare
comp	-	comparison to apply to the projected elements
proj	-	projection to apply to the elements

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/ranges/minmax"

Latest revision as of 10:34, 28 August 2023

Contents

[edit] Parameters

[edit] Return value

[edit] Complexity

[edit] Possible implementation

[edit] Notes

[edit] Example

[edit] See also

Navigation

Toolbox

@@ Line 2: / Line 2: @@
 {{cpp/algorithm/ranges/navbar}}
 {{dcl begin}}
-{{dcl header | algorithm}}
+{{dcl header|algorithm}}
-{{dcl h | Call signature}}
+{{dcl h|Call signature}}
-{{dcl | since=c++20 | num=1 | 1=
+{{dcl|since=c++20|num=1|1=
 template< class T, class Proj = std::identity,
            std::indirect_strict_weak_order<
                std::projected<const T*, Proj>> Comp = ranges::less >
 constexpr ranges::minmax_result<const T&>
-minmax( const T& a, const T& b, Comp comp = {}, Proj proj = {} );
+    minmax( const T& a, const T& b, Comp comp = {}, Proj proj = {} );
 }}
-{{dcl | since=c++20 | num=2 | 1=
+{{dcl|since=c++20|num=2|1=
 template< std::copyable T, class Proj = std::identity,
            std::indirect_strict_weak_order<
                std::projected<const T*, Proj>> Comp = ranges::less >
 constexpr ranges::minmax_result<T>
-minmax( std::initializer_list<T> r, Comp comp = {}, Proj proj = {} );
+    minmax( std::initializer_list<T> r, Comp comp = {}, Proj proj = {} );
 }}
-{{dcl | since=c++20 | num=3 | 1=
+{{dcl|since=c++20|num=3|1=
 template< ranges::input_range R, class Proj = std::identity,
            std::indirect_strict_weak_order<
@@ Line 24: / Line 24: @@
 requires std::indirectly_copyable_storable<ranges::iterator_t<R>, ranges::range_value_t<R>*>
 constexpr ranges::minmax_result<ranges::range_value_t<R>>
-minmax( R&& r, Comp comp = {}, Proj proj = {} );
+    minmax( R&& r, Comp comp = {}, Proj proj = {} );
 }}
-{{dcl h | Helper types}}
+{{dcl h|Helper types}}
-{{dcl | since=c++20 | num=4 | 1=
+{{dcl|since=c++20|num=4|1=
 template< class T >
 using minmax_result = ranges::min_max_result<T>;
@@ Line 35: / Line 35: @@
 Returns the smallest and the greatest of the given projected values.
-@1@ Returns references to the smaller and the greater of {{tt|a}} and {{tt|b}}.
+@1@ Returns references to the smaller and the greater of {{c|a}} and {{c|b}}.
-@2@ Returns the smallest and the greatest of the values in the initializer list {{tt|r}}.
+@2@ Returns the smallest and the greatest of the values in the initializer list {{c|r}}.
-@3@ Returns the smallest and the greatest of the values in the range {{tt|r}}.
+@3@ Returns the smallest and the greatest of the values in the range {{c|r}}.
 {{cpp/ranges/niebloid}}
@@ Line 43: / Line 43: @@
 ===Parameters===
 {{par begin}}
-{{par | a, b  | the values to compare}}
+{{par|a, b|the values to compare}}
-{{par | r     | a non-empty range of values to compare}}
+{{par|r|a non-empty range of values to compare}}
-{{par | comp  | comparison to apply to the projected elements}}
+{{par|comp|comparison to apply to the projected elements}}
-{{par | proj  | projection to apply to the elements.}}
+{{par|proj|projection to apply to the elements}}
 {{par end}}
 ===Return value===
-@1@ {{c|{b, a} }} if, according to their respective projected value, {{tt|b}} is smaller than {{tt|a}}; otherwise it returns {{c|{a, b} }}.
+@1@ {{c|{b, a} }} if, according to their respective projected value, {{c|b}} is smaller than {{c|a}}; otherwise it returns {{c|{a, b} }}.
-@2-3@ {{c|{s, l} }}, where {{tt|s}} and {{tt|l}} are respectively the smallest and largest values in {{tt|r}}, according to their projected value. If several values are equivalent to the smallest and largest, returns the leftmost smallest value, and the rightmost largest value. If the range is empty (as determined by {{c|ranges::distance(r)}}), the behavior is undefined.
+@2,3@ {{c|{s, l} }}, where {{tt|s}} and {{tt|l}} are respectively the smallest and largest values in {{c|r}}, according to their projected value. If several values are equivalent to the smallest and largest, returns the leftmost smallest value, and the rightmost largest value. If the range is empty (as determined by {{c|ranges::distance(r)}}), the behavior is undefined.
 ===Complexity===
 @1@ Exactly one comparison and two applications of the projection.
-@2-3@ At most {{c|3 / 2 * ranges::distance(r)}} comparisons and twice as many applications of the projection.
+@2,3@ At most {{c|3 / 2 * ranges::distance(r)}} comparisons and twice as many applications of the projection.
 ===Possible implementation===
 {{eq fun
- | 1=
+|1=
-struct minmax_fn {
+struct minmax_fn
-  template<class T, class Proj = std::identity,
+{
-           std::indirect_strict_weak_order<
+    template<class T, class Proj = std::identity,
-               std::projected<const T*, Proj>> Comp = ranges::less>
+             std::indirect_strict_weak_order<
-  constexpr ranges::minmax_result<const T&> operator()(
+                 std::projected<const T*, Proj>> Comp = ranges::less>
-      const T& a, const T& b, Comp comp = {}, Proj proj = {}) const
+    constexpr ranges::minmax_result<const T&>
-  {
+         operator()(const T& a, const T& b, Comp comp = {}, Proj proj = {}) const
-      if (std::invoke(comp, std::invoke(proj, b), std::invoke(proj, a))) {
+    {
-          return {b, a};
+        if (std::invoke(comp, std::invoke(proj, b), std::invoke(proj, a)))
-      }
+            return {b, a};
-      return {a, b};
+        return {a, b};
-  }
+    }
-  template<std::copyable T, class Proj = std::identity,
+    template<std::copyable T, class Proj = std::identity,
-           std::indirect_strict_weak_order<
+             std::indirect_strict_weak_order<
-               std::projected<const T*, Proj>> Comp = ranges::less>
+                 std::projected<const T*, Proj>> Comp = ranges::less>
-  constexpr ranges::minmax_result<T> operator()(
+    constexpr ranges::minmax_result<T>
-      std::initializer_list<T> r, Comp comp = {}, Proj proj = {}) const
+        operator()(std::initializer_list<T> r, Comp comp = {}, Proj proj = {}) const
-  {
+    {
-    auto result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
+        auto result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
-    return {*result.min, *result.max};
+        return {*result.min, *result.max};
-  }
+    }
-  template<ranges::input_range R, class Proj = std::identity,
+    template<ranges::input_range R, class Proj = std::identity,
-           std::indirect_strict_weak_order<
+             std::indirect_strict_weak_order<
-                std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
+                 std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
-  requires std::indirectly_copyable_storable<ranges::iterator_t<R>,
+    requires std::indirectly_copyable_storable<ranges::iterator_t<R>,
-                                             ranges::range_value_t<R>*>
+                                               ranges::range_value_t<R>*>
-  constexpr ranges::minmax_result<ranges::range_value_t<R>> operator()(
+    constexpr ranges::minmax_result<ranges::range_value_t<R>>
-      R&& r, Comp comp = {}, Proj proj = {}) const
+        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
-  {
+    {
-      auto result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
+        auto result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
-      return {std::move(*result.min), std::move(*result.max)};
+        return {std::move(*result.min), std::move(*result.max)};
-  }
+    }
 };
@@ Line 103: / Line 103: @@
 ===Notes===
-For overloads {{v|1,2}}, if one of the parameters is a temporary, the reference returned becomes a dangling reference at the end of the full expression that contains the call to {{tt|minmax}}:
+For overload {{v|1}}, if one of the parameters is a temporary, the reference returned becomes a dangling reference at the end of the full expression that contains the call to {{tt|minmax}}:
 {{source|1=
 int n = 1;
-auto p = ranges::minmax(n, n+1);
+auto p = std::ranges::minmax(n, n + 1);
-int m = p.first; // ok
+int m = p.min; // ok
-int x = p.second; // undefined behavior
+int x = p.max; // undefined behavior
+// Note that structured bindings have the same issue
+auto [mm, xx] = std::ranges::minmax(n, n + 1);
+xx; // undefined behavior
 }}
 ===Example===
-{{example | p=true | code=
+{{example
+|code=
 #include <algorithm>
+#include <array>
 #include <iostream>
 #include <random>
-#include <vector>
 int main()
 {
-    std::vector<int> v{3, 1, 4, 9, 1, 5, 9, 2, 6};
-    std::mt19937_64 generator;
      namespace ranges = std::ranges;
-    std::uniform_int_distribution<> distribution(0, ranges::distance(v));
-     auto bounds = ranges::minmax(distribution(generator), distribution(generator));
+     constexpr std::array v{3, 1, 4, 1, 5, 9, 2, 6, 5};
+    std::random_device rd;
+    std::mt19937_64 generator(rd());
+    std::uniform_int_distribution<> distribution(0, ranges::distance(v)); // [0..9]
+    // auto bounds = ranges::minmax(distribution(generator), distribution(generator));
+    // UB: dangling references: bounds.min and bounds.max have the type `const int&`.
+    const int x1 = distribution(generator);
+    const int x2 = distribution(generator);
+    auto bounds = ranges::minmax(x1, x2); // OK: got references to lvalues x1 and x2
      std::cout << "v[" << bounds.min << ":" << bounds.max << "]: ";
-     for (int i = bounds.min; i < bounds.max; ++i) {
+     for (int i = bounds.min; i < bounds.max; ++i)
          std::cout << v[i] << ' ';
-    }
      std::cout << '\n';
      auto [min, max] = ranges::minmax(v);
-     std::cout << "smallest: " << min << '\n'
+     std::cout << "smallest: " << min << ", " << "largest: " << max << '\n';
-              << "largest: " << max << '\n';
 }
- | output=
+|p=true
-v[2:7]: 4 9 1 5 9
+|output=
-smallest: 1
+v[3:9]: 1 5 9 2 6 5
-largest: 9
+smallest: 1, largest: 9
 }}
 ===See also===
 {{dsc begin}}
-{{dsc inc | cpp/algorithm/ranges/dsc min}}
+{{dsc inc|cpp/algorithm/ranges/dsc min}}
-{{dsc inc | cpp/algorithm/ranges/dsc max}}
+{{dsc inc|cpp/algorithm/ranges/dsc max}}
-{{dsc inc | cpp/algorithm/ranges/dsc minmax_element}}
+{{dsc inc|cpp/algorithm/ranges/dsc minmax_element}}
-{{dsc inc | cpp/algorithm/ranges/dsc clamp}}
+{{dsc inc|cpp/algorithm/ranges/dsc clamp}}
-{{dsc inc | cpp/algorithm/dsc minmax}}
+{{dsc inc|cpp/algorithm/dsc minmax}}
 {{dsc end}}
 {{langlinks|de|es|fr|it|ja|pt|ru|zh}}