Difference between revisions of "cpp/algorithm/minmax"

Latest revision as of 07:02, 9 April 2024

Defined in header `<algorithm>`
template< class T > std::pair<const T&, const T&> minmax( const T& a, const T& b );	(1)	(since C++11) (constexpr since C++14)
template< class T, class Compare > std::pair<const T&, const T&> minmax( const T& a, const T& b, Compare comp );	(2)	(since C++11) (constexpr since C++14)
template< class T > std::pair<T, T> minmax( std::initializer_list<T> ilist );	(3)	(since C++11) (constexpr since C++14)
template< class T, class Compare > std::pair<T, T> minmax( std::initializer_list<T> ilist, Compare comp );	(4)	(since C++11) (constexpr since C++14)

Returns the lowest and the greatest of the given values.

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

1) Uses operator< to compare the values.

If T is not LessThanComparable, the behavior is undefined.

2) Use the comparison function comp to compare the values.

3,4) Returns the smallest and the greatest of the values in initializer list ilist.

If ilist.size() is zero, or T is not CopyConstructible, the behavior is undefined.

3) Uses operator< to compare the values.

If T is not LessThanComparable, the behavior is undefined.

4) Use the comparison function comp to compare the values.

While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1& is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy(since C++11)).
The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both of them.

[edit] Return value

1,2) Returns the result of std::pair<const T&, const T&>(a, b) if a < b or if a is equivalent to b. Returns the result of std::pair<const T&, const T&>(b, a) if b < a.

3,4) A pair with the smallest value in ilist as the first element and the greatest as the second. If several elements are equivalent to the smallest, the leftmost such element is returned. If several elements are equivalent to the largest, the rightmost such element is returned.

[edit] Complexity

1) Exactly one comparison using operator<.

2) Exactly one application of the comparison function comp.

3,4) Given

N

as ilist.size():

3) At most

3N 2

comparisons using operator<.

4) At most

3N 2

applications of the comparison function comp.

[edit] Possible implementation

minmax (1)
template<class T> constexpr std::pair<const T&, const T&> minmax(const T& a, const T& b) { return (b < a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b); }
minmax (2)
template<class T, class Compare> constexpr std::pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp) { return comp(b, a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b); }
minmax (3)
template<class T> constexpr std::pair<T, T> minmax(std::initializer_list<T> ilist) { auto p = std::minmax_element(ilist.begin(), ilist.end()); return std::pair(p.first, p.second); }
minmax (4)
template<class T, class Compare> constexpr std::pair<T, T> minmax(std::initializer_list<T> ilist, Compare comp) { auto p = std::minmax_element(ilist.begin(), ilist.end(), comp); return std::pair(p.first, p.second); }

[edit] Notes

For overloads (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 minmax:

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

[edit] Example

Run this code

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
    std::srand(std::time(0));
    std::pair<int, int> bounds = std::minmax(std::rand() % v.size(),
                                             std::rand() % v.size());
 
    std::cout << "v[" << bounds.first << "," << bounds.second << "]: ";
    for (int i = bounds.first; i < bounds.second; ++i)
        std::cout << v[i] << ' ';
    std::cout << '\n';
}

Possible output:

v[2,7]: 4 1 5 9 2

[edit] See also

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

@@ Line 2: / Line 2: @@
 {{cpp/algorithm/navbar}}
 {{dcl begin}}
-{{dcl header | algorithm}}
+{{dcl header|algorithm}}
-{{dcl rev begin|num=1}}
+{{dcla|num=1|since=c++11|notes={{mark constexpr since c++14}}|
-{{dcl | since=c++11 | until=c++14 |
+template< class T >
-template< class T >
+std::pair<const T&, const T&> minmax( const T& a, const T& b );
-std::pair<const T&,const T&> minmax( const T& a, const T& b );
 }}
-{{dcl | since=c++14 |
+{{dcla|num=2|since=c++11|notes={{mark constexpr since c++14}}|
-template< class T >
-constexpr std::pair<const T&,const T&> minmax( const T& a, const T& b );
-}}
-{{dcl rev end}}
-{{dcl rev begin|num=2}}
-{{dcl | since=c++11 | until=c++14 |
 template< class T, class Compare >
-std::pair<const T&,const T&> minmax( const T& a, const T& b,
+std::pair<const T&, const T&> minmax( const T& a, const T& b,
-                                     Compare comp );
+                                      Compare comp );
-}}
-{{dcl | since=c++14 |
-template< class T, class Compare >
-constexpr std::pair<const T&,const T&> minmax( const T& a, const T& b,
-                                               Compare comp );
-}}
-{{dcl rev end}}
-{{dcl rev begin|num=3}}
-{{dcl | since=c++11 | until=c++14 |
-template< class T >
-std::pair<T,T> minmax( std::initializer_list<T> ilist);
 }}
-{{dcl | since=c++14 |
+{{dcla|num=3|since=c++11|notes={{mark constexpr since c++14}}|
 template< class T >
-constexpr std::pair<T,T> minmax( std::initializer_list<T> ilist);
+std::pair<T, T> minmax( std::initializer_list<T> ilist );
 }}
-{{dcl rev end}}
+{{dcla|num=4|since=c++11|notes={{mark constexpr since c++14}}|
-{{dcl rev begin|num=4}}
-{{dcl | since=c++11 | until=c++14 |
 template< class T, class Compare >
-std::pair<T,T> minmax( std::initializer_list<T> ilist, Compare comp );
+std::pair<T, T> minmax( std::initializer_list<T> ilist,
+                        Compare comp );
 }}
-{{dcl | since=c++14 |
-template< class T, class Compare >
-constexpr std::pair<T,T> minmax( std::initializer_list<T> ilist, Compare comp );
-}}
-{{dcl rev end}}
 {{dcl end}}
 Returns the lowest and the greatest of the given values.
-@1-2@ Returns the smaller and the greater of {{tt|a}} and {{tt|b}}.
+@1,2@ Returns references to the smaller and the greater of {{c|a}} and {{c|b}}.
+:@1@ Uses {{c/core|operator<}} to compare the values.
+:@@ If {{tt|T}} is not {{named req|LessThanComparable}}, the behavior is undefined.
+:@2@ Use the comparison function {{c|comp}} to compare the values.
-@3-4@ Returns the smallest and the greatest of the values in initializer list {{tt|ilist}}.
+@3,4@ Returns the smallest and the greatest of the values in initializer list {{c|ilist}}.
+@@ If {{c|ilist.size()}} is zero, or {{tt|T}} is not {{named req|CopyConstructible}}, the behavior is undefined.
-The {{v|1,3}} versions use {{c|operator<}} to compare the values, whereas the {{v|2,4}} versions use the given comparison function {{tt|comp}}.
+:@3@ Uses {{c/core|operator<}} to compare the values.
+:@@ If {{tt|T}} is not {{named req|LessThanComparable}}, the behavior is undefined.
+:@4@ Use the comparison function {{c|comp}} to compare the values.
 ===Parameters===
 {{par begin}}
-{{par | a, b | the values to compare}}
+{{par|a, b|the values to compare}}
-{{par | ilist | initializer list with the values to compare}}
+{{par|ilist|initializer list with the values to compare}}
-{{par cmp | comp | t1=T <!--| if {{tt|a}} is ''less'' than {{tt|b}}-->}}
+{{par cmp|comp|t1=T}}
-{{par hreq}}
-{{par req concept | T | LessThanComparable}}
-{{par req concept | T | CopyConstructible | overloads=3,4}}
 {{par end}}
 ===Return value===
-@1-2@ Returns the result of {{c|std::make_pair(a, b)}} if {{tt|a<b}} or if {{tt|a}} is equivalent to {{tt|b}}. Returns the result of {{c|std::make_pair(b, a)}} if {{tt|b<a}}.
+@1,2@ Returns the result of {{c|std::pair<const T&, const T&>(a, b)}} if {{c|a < b}} or if {{c|a}} is equivalent to {{c|b}}. Returns the result of {{c|std::pair<const T&, const T&>(b, a)}} if {{c|b < a}}.
-@3-4@ A pair with the smallest value in {{tt|ilist}} as the first element and the greatest as the second. If several elements are equivalent to the smallest, the leftmost such element is returned. If several elements are equivalent to the largest, the rightmost such element is returned.
+@3,4@ A pair with the smallest value in {{c|ilist}} as the first element and the greatest as the second. If several elements are equivalent to the smallest, the leftmost such element is returned. If several elements are equivalent to the largest, the rightmost such element is returned.
 ===Complexity===
-@1-2@ Constant
+@1@ Exactly one comparison using {{c/core|operator<}}.
-@3-4@ Linear in {{tt|ilist.size()}}
+@2@ Exactly one application of the comparison function {{c|comp}}.
+@3,4@ Given {{mathjax-or|\(\scriptsize N\)|N}} as {{c|ilist.size()}}:
+:@3@ At most {{mathjax-or|\(\scriptsize \frac{3N}{2}\)|{{mfrac|3N|2}}}} comparisons using {{c/core|operator<}}.
+:@4@ At most {{mathjax-or|\(\scriptsize \frac{3N}{2}\)|{{mfrac|3N|2}}}} applications of the comparison function {{c|comp}}.
 ===Possible implementation===
-{{eq fun
+{{eq impl
- | 1=
+|title1=minmax (1)|ver1=1|1=
 template<class T>
-std::pair<const T&, const T&> minmax(const T& a, const T& b)
+constexpr std::pair<const T&, const T&> minmax(const T& a, const T& b)
 {
-     return (b < a) ? std::make_pair(b, a)
+     return (b < a) ? std::pair<const T&, const T&>(b, a)
-                    : std::make_pair(a, b);
+                    : std::pair<const T&, const T&>(a, b);
 }
- | 2=
+|title2=minmax (2)|ver2=2|2=
 template<class T, class Compare>
-std::pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp)
+constexpr std::pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp)
 {
-     return comp(b, a) ? std::make_pair(b, a)
+     return comp(b, a) ? std::pair<const T&, const T&>(b, a)
-                       : std::make_pair(a, b);
+                       : std::pair<const T&, const T&>(a, b);
 }
- | 3=
+|title3=minmax (3)|ver3=3|3=
-template< class T >
+template<class T>
-std::pair<T, T> minmax( std::initializer_list<T> ilist)
+constexpr std::pair<T, T> minmax(std::initializer_list<T> ilist)
 {
      auto p = std::minmax_element(ilist.begin(), ilist.end());
-     return std::make_pair(*p.first, *p.second);
+     return std::pair(*p.first, *p.second);
 }
- | 4=
+|title4=minmax (4)|ver4=4|4=
-template< class T, class Compare >
+template<class T, class Compare>
-std::pair<T, T> minmax( std::initializer_list<T> ilist, Compare comp )
+constexpr std::pair<T, T> minmax(std::initializer_list<T> ilist, Compare comp)
 {
      auto p = std::minmax_element(ilist.begin(), ilist.end(), comp);
-     return std::make_pair(*p.first, *p.second);
+     return std::pair(*p.first, *p.second);
 }
+}}
+===Notes===
+For overloads {{vl|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}}:
+{{source|1=
+int n = 1;
+auto p = std::minmax(n, n + 1);
+int m = p.first; // ok
+int x = p.second; // undefined behavior
+// Note that structured bindings have the same issue
+auto [mm, xx] = std::minmax(n, n + 1);
+xx; // undefined behavior
 }}
 ===Example===
 {{example
- | p=true
+|code=
- | code=
 #include <algorithm>
+#include <cstdlib>
+#include <ctime>
 #include <iostream>
 #include <vector>
-#include <cstdlib>
-#include <ctime>
 int main()
 {
-     std::vector<int> v {3, 1, 4, 1, 5, 9, 2, 6};
+     std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
      std::srand(std::time(0));
      std::pair<int, int> bounds = std::minmax(std::rand() % v.size(),
                                               std::rand() % v.size());
      std::cout << "v[" << bounds.first << "," << bounds.second << "]: ";
-     for (int i = bounds.first; i < bounds.second; ++i) {
+     for (int i = bounds.first; i < bounds.second; ++i)
          std::cout << v[i] << ' ';
-    }
      std::cout << '\n';
 }
- | output=
+|p=true
+|output=
 v[2,7]: 4 1 5 9 2
 }}
@@ Line 136: / Line 130: @@
 ===See also===
 {{dsc begin}}
-{{dsc inc | cpp/algorithm/dsc min}}
+{{dsc inc|cpp/algorithm/dsc min}}
-{{dsc inc | cpp/algorithm/dsc max}}
+{{dsc inc|cpp/algorithm/dsc max}}
+{{dsc inc|cpp/algorithm/dsc minmax_element}}
+{{dsc inc|cpp/algorithm/ranges/dsc minmax}}
 {{dsc end}}
-[[de:cpp/algorithm/minmax]]
+{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
-[[es:cpp/algorithm/minmax]]
-[[fr:cpp/algorithm/minmax]]
-[[it:cpp/algorithm/minmax]]
-[[ja:cpp/algorithm/minmax]]
-[[pt:cpp/algorithm/minmax]]
-[[ru:cpp/algorithm/minmax]]
-[[zh:cpp/algorithm/minmax]]

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

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/minmax"

Latest revision as of 07:02, 9 April 2024

Contents

[edit] Parameters