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 1: / Line 1: @@
 {{cpp/title|minmax}}
-{{cpp/algorithm/sidebar}}
+{{cpp/algorithm/navbar}}
-{{ddcl list begin}}
+{{dcl begin}}
-{{ddcl list header | algorithm}}
+{{dcl header|algorithm}}
-{{ddcl list item | num=1 | notes={{mark c++11 feature}} |
+{{dcla|num=1|since=c++11|notes={{mark constexpr since c++14}}|
 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 );
 }}
-{{ddcl list item | num=2 | notes={{mark c++11 feature}} |
+{{dcla|num=2|since=c++11|notes={{mark constexpr since c++14}}|
 template< class T, class Compare >
-std::pair<const T&,const T&> minmax( const T& a, const T& b, Compare comp );
+std::pair<const T&, const T&> minmax( const T& a, const T& b,
+                                      Compare comp );
 }}
-{{ddcl list item | num=3 | notes={{mark c++11 feature}} |
+{{dcla|num=3|since=c++11|notes={{mark constexpr since c++14}}|
 template< class T >
-std::pair<T,T> minmax( std::initializer_list ilist);
+std::pair<T, T> minmax( std::initializer_list<T> ilist );
 }}
-{{ddcl list item | num=4 | notes={{mark c++11 feature}} |
+{{dcla|num=4|since=c++11|notes={{mark constexpr since c++14}}|
 template< class T, class Compare >
-std::pair<T,T> minmax( std::initializer_list ilist, Compare comp );
+std::pair<T, T> minmax( std::initializer_list<T> ilist,
+                        Compare comp );
 }}
-{{ddcl list end}}
+{{dcl end}}
--2) Returns the smaller and the greater of the two values.
+Returns the lowest and the greatest of the given values.
--4) Returns the smallest and the greatest of the values in initializer list {{tt|ilist}}.
+@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.
-The (1,3) versions use {{cpp|operator<}} to compare the values, the (2,4) versions use the given comparison function {{tt|comp}}.
+@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.
+:@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===
-{{param list begin}}
+{{par begin}}
-{{param list item | a, b | the values to compare}}
+{{par|a, b|the values to compare}}
-{{param list item | ilist | initializer list with the values to compare}}
+{{par|ilist|initializer list with the values to compare}}
-{{param list cmp | cmp | t1=T | if {{tt|a}} is ''less'' than {{tt|b}}}}
+{{par cmp|comp|t1=T}}
-{{param list end}}
+{{par end}}
 ===Return value===
--2) Returns the result of {{cpp|std::make_pair(a, b)}} if {{tt|a<b}} or if {{tt|a}} is equivalent to {{tt|b}}. Returns the result of {{cpp|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}}.
--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===
--2) Constant
+@1@ Exactly one comparison using {{c/core|operator<}}.
--4) Linear in {{tt|ilist.size()}}
+@2@ Exactly one application of the comparison function {{c|comp}}.
-===Equivalent function===
+@3,4@ Given {{mathjax-or|\(\scriptsize N\)|N}} as {{c|ilist.size()}}:
-{{eq fun cpp
+:@3@ At most {{mathjax-or|\(\scriptsize \frac{3N}{2}\)|{{mfrac|3N|2}}}} comparisons using {{c/core|operator<}}.
- | 1=
+:@4@ At most {{mathjax-or|\(\scriptsize \frac{3N}{2}\)|{{mfrac|3N|2}}}} applications of the comparison function {{c|comp}}.
-template<class T>
-std::pair<const T&,const T&> minmax(const T& a, const T& b)
+===Possible implementation===
+{{eq impl
+|title1=minmax (1)|ver1=1|1=
+template<class T>
+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 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 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 cpp
+{{example
- | code=
+|code=
- | output=
+#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';
+}
+|p=true
+|output=
+v[2,7]: 4 1 5 9 2
 }}
 ===See also===
-{{dcl list begin}}
+{{dsc begin}}
-{{dcl list template | cpp/algorithm/dcl list min}}
+{{dsc inc|cpp/algorithm/dsc min}}
-{{dcl list template | cpp/algorithm/dcl list max}}
+{{dsc inc|cpp/algorithm/dsc max}}
-{{dcl list end}}
+{{dsc inc|cpp/algorithm/dsc minmax_element}}
+{{dsc inc|cpp/algorithm/ranges/dsc minmax}}
+{{dsc end}}
+{{langlinks|de|es|fr|it|ja|pt|ru|zh}}

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