Difference between revisions of "cpp/algorithm/minmax"
(→Notes: Note structured bindings) |
m (→Notes: +link to the Synopsis.) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 2: | Line 2: | ||
{{cpp/algorithm/navbar}} | {{cpp/algorithm/navbar}} | ||
{{dcl begin}} | {{dcl begin}} | ||
− | {{dcl header | algorithm}} | + | {{dcl header|algorithm}} |
− | {{ | + | {{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 ); | |
− | + | ||
− | + | ||
− | template< class T > | + | |
− | + | ||
}} | }} | ||
− | {{ | + | {{dcla|num=2|since=c++11|notes={{mark constexpr since c++14}}| |
− | | | + | |
template< class T, class Compare > | 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 ); | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
}} | }} | ||
− | {{ | + | {{dcla|num=3|since=c++11|notes={{mark constexpr since c++14}}| |
− | | | + | |
template< class T > | template< class T > | ||
− | + | std::pair<T, T> minmax( std::initializer_list<T> ilist ); | |
− | + | ||
− | + | ||
− | + | ||
}} | }} | ||
− | {{ | + | {{dcla|num=4|since=c++11|notes={{mark constexpr since c++14}}| |
− | | | + | |
− | + | ||
− | + | ||
− | + | ||
template< class T, class Compare > | template< class T, class Compare > | ||
− | + | std::pair<T, T> minmax( std::initializer_list<T> ilist, | |
+ | Compare comp ); | ||
}} | }} | ||
{{dcl end}} | {{dcl end}} | ||
Line 41: | Line 25: | ||
Returns the lowest and the greatest of the given values. | Returns the lowest and the greatest of the given values. | ||
− | @1 | + | @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 | + | @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=== | ===Parameters=== | ||
{{par begin}} | {{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 | + | {{par cmp|comp|t1=T}} |
− | + | ||
− | + | ||
− | + | ||
{{par end}} | {{par end}} | ||
===Return value=== | ===Return value=== | ||
− | @1 | + | @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 | + | @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=== | ===Complexity=== | ||
− | @1 | + | @1@ Exactly one comparison using {{c/core|operator<}}. |
− | @3 | + | @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=== | ===Possible implementation=== | ||
− | {{eq | + | {{eq impl |
− | + | |title1=minmax (1)|ver1=1|1= | |
− | template<class T> | + | 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::pair<const T&, const T&>(b, a) | return (b < a) ? std::pair<const T&, const T&>(b, a) | ||
: std::pair<const T&, const T&>(a, b); | : std::pair<const T&, const T&>(a, b); | ||
} | } | ||
− | + | |title2=minmax (2)|ver2=2|2= | |
− | template<class T, class Compare> | + | 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::pair<const T&, const T&>(b, a) | return comp(b, a) ? std::pair<const T&, const T&>(b, a) | ||
: std::pair<const T&, const T&>(a, b); | : std::pair<const T&, const T&>(a, b); | ||
} | } | ||
− | + | |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()); | auto p = std::minmax_element(ilist.begin(), ilist.end()); | ||
return std::pair(*p.first, *p.second); | return std::pair(*p.first, *p.second); | ||
} | } | ||
− | + | |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); | auto p = std::minmax_element(ilist.begin(), ilist.end(), comp); | ||
Line 100: | Line 90: | ||
===Notes=== | ===Notes=== | ||
− | For overloads {{ | + | 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= | {{source|1= | ||
int n = 1; | int n = 1; | ||
− | auto p = std::minmax(n, n+1); | + | auto p = std::minmax(n, n + 1); |
int m = p.first; // ok | int m = p.first; // ok | ||
int x = p.second; // undefined behavior | int x = p.second; // undefined behavior | ||
// Note that structured bindings have the same issue | // Note that structured bindings have the same issue | ||
− | auto [mm, xx] = std::minmax(n, n+1); | + | auto [mm, xx] = std::minmax(n, n + 1); |
xx; // undefined behavior | xx; // undefined behavior | ||
}} | }} | ||
Line 114: | Line 104: | ||
===Example=== | ===Example=== | ||
{{example | {{example | ||
− | + | |code= | |
− | + | ||
#include <algorithm> | #include <algorithm> | ||
+ | #include <cstdlib> | ||
+ | #include <ctime> | ||
#include <iostream> | #include <iostream> | ||
#include <vector> | #include <vector> | ||
− | |||
− | |||
int main() | 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::srand(std::time(0)); | ||
std::pair<int, int> bounds = std::minmax(std::rand() % v.size(), | std::pair<int, int> bounds = std::minmax(std::rand() % v.size(), | ||
std::rand() % v.size()); | std::rand() % v.size()); | ||
− | + | ||
std::cout << "v[" << bounds.first << "," << bounds.second << "]: "; | 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 << v[i] << ' '; | ||
− | |||
std::cout << '\n'; | std::cout << '\n'; | ||
} | } | ||
− | + | |p=true | |
+ | |output= | ||
v[2,7]: 4 1 5 9 2 | v[2,7]: 4 1 5 9 2 | ||
}} | }} | ||
Line 141: | Line 130: | ||
===See also=== | ===See also=== | ||
{{dsc begin}} | {{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/dsc minmax_element}} |
− | {{dsc inc | cpp/algorithm/ranges/dsc minmax}} | + | {{dsc inc|cpp/algorithm/ranges/dsc minmax}} |
{{dsc end}} | {{dsc end}} | ||
{{langlinks|de|es|fr|it|ja|pt|ru|zh}} | {{langlinks|de|es|fr|it|ja|pt|ru|zh}} |
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, |
(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, |
(4) | (since C++11) (constexpr since C++14) |
Returns the lowest and the greatest of the given values.
T
is not LessThanComparable, the behavior is undefined.T
is not LessThanComparable, the behavior is undefined.Contents |
[edit] Parameters
a, b | - | the values to compare |
ilist | - | initializer list with the values to compare |
comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1& a, const Type2& b); 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) |
[edit] Return value
[edit] Complexity
3N |
2 |
3N |
2 |
[edit] Possible implementation
minmax (1) |
---|
minmax (2) |
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
#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
returns the smaller of the given values (function template) | |
returns the greater of the given values (function template) | |
(C++11) |
returns the smallest and the largest elements in a range (function template) |
(C++20) |
returns the smaller and larger of two elements (niebloid) |