「cpp/algorithm/minmax element」の版間の差分

提供: cppreference.com

2019年2月1日 (金) 07:16時点における最新版

ヘッダ `<algorithm>` で定義
	(1)
template< class ForwardIt > std::pair<ForwardIt,ForwardIt> minmax_element( ForwardIt first, ForwardIt last );			(C++11以上) (C++17未満)
template< class ForwardIt > constexpr std::pair<ForwardIt,ForwardIt> minmax_element( ForwardIt first, ForwardIt last );			(C++17以上)
template< class ExecutionPolicy, class ForwardIt > std::pair<ForwardIt,ForwardIt> minmax_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );		(2)	(C++17以上)
		(3)
template< class ForwardIt, class Compare > std::pair<ForwardIt,ForwardIt> minmax_element( ForwardIt first, ForwardIt last, Compare comp );				(C++11以上) (C++17未満)
template< class ForwardIt, class Compare > constexpr std::pair<ForwardIt,ForwardIt> minmax_element( ForwardIt first, ForwardIt last, Compare comp );				(C++17以上)
template< class ExecutionPolicy, class ForwardIt, class Compare > std::pair<ForwardIt,ForwardIt> minmax_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare comp );			(4)	(C++17以上)

範囲 [first, last) 内の最も小さな要素と最も大きな要素を探します。

1) 要素は operator< を用いて比較されます。

3) 要素は指定された二項比較関数 comp を用いて比較されます。

2,4) (1,3) と同じですが、 policy に従って実行されます。これらのオーバーロードは、 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true でなければ、オーバーロード解決に参加しません。

first, last	-	調べる範囲を定義する前方イテレータ
policy	-	使用する実行ポリシー。詳細は実行ポリシーを参照してください
cmp	-	`a` が `b` より小さい場合に true を返す、比較関数オブジェクト (Compare の要件を満たすオブジェクト)。比較関数のシグネチャは以下と同等であるべきです。 bool cmp(const Type1 &a, const Type2 &b); シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関わらず `Type1` および `Type2` 型 (およびそれらの const 修飾された型) のすべての値を受理できなければなりません (そのため Type1 & は許されません。また Type1 に対してムーブがコピーと同等でなければ Type1 も許されません (C++11以上))。型 Type1 および Type2 は、どちらも ForwardIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。
型の要件
- `ForwardIt` は LegacyForwardIterator の要件を満たさなければなりません。

[編集] 戻り値

第1要素として最も小さな要素を指すイテレータを持ち第2要素として最も大きな要素を指すイテレータを持つペア。範囲が空の場合は std::make_pair(first, first) を返します。最も小さな同等な要素が複数ある場合は、最初のそのような要素を指すイテレータが返されます。最も大きな同等な要素が複数ある場合は、最後のそのような要素を指すイテレータが返されます。

[編集] 計算量

多くとも $max(floor((3/2)*(N-1)), 0)$ 回の述語の適用、ただし N = std::distance(first, last) です。

[編集] 例外

テンプレート引数 ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告します。

アルゴリズムの一部として呼び出された関数の実行が例外を投げ、 ExecutionPolicy が標準のポリシーのいずれかの場合は、 std::terminate が呼ばれます。それ以外のあらゆる ExecutionPolicy については、動作は処理系定義です。
アルゴリズムがメモリの確保に失敗した場合は、 std::bad_alloc が投げられます。

[編集] ノート

このアルゴリズムは std::make_pair(std::min_element(), std::max_element()) と異なります。効率性だけでなく、このアルゴリズムは最も大きな最後の要素を探しますが、 std::max_element は最も大きな最初の要素を探します。

[編集] 実装例

1つめのバージョン

template<class ForwardIt>
std::pair<ForwardIt, ForwardIt> 
    minmax_element(ForwardIt first, ForwardIt last)
{
    using value_type = typename std::iterator_traits<ForwardIt>::value_type;
    return std::minmax_element(first, last, std::less<value_type>());
}

2つめのバージョン

template<class ForwardIt, class Compare>
std::pair<ForwardIt, ForwardIt> 
    minmax_element(ForwardIt first, ForwardIt last, Compare comp)
{
    auto min = first, max = first;
 
    if (first == last || ++first == last)
        return {min, max};
 
    if (comp(*first, *min)) {
        min = first;
    } else {
        max = first;
    }
 
    while (++first != last) {
        auto i = first;
        if (++first == last) {
            if (comp(*i, *min)) min = i;
            else if (!(comp(*i, *max))) max = i;
            break;
        } else {
            if (comp(*first, *i)) {
                if (comp(*first, *min)) min = first;
                if (!(comp(*i, *max))) max = i;
            } else {
                if (comp(*i, *min)) min = i;
                if (!(comp(*first, *max))) max = first;
            }
        }
    }
    return {min, max};
}

[編集] 例

Run this code

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    const auto v = { 3, 9, 1, 4, 2, 5, 9 };
    const auto [min, max] = std::minmax_element(begin(v), end(v));
 
    std::cout << "min = " << *min << ", max = " << *max << '\n';
}

出力:

min = 1, max = 9

[編集] 関連項目

min_element	指定範囲の最も小さな要素を返します (関数テンプレート) [edit]
max_element	指定範囲の最も大きな要素を返します (関数テンプレート) [edit]

「https://ja.cppreference.com/mwiki/index.php?title=cpp/algorithm/minmax_element&oldid=44125」から取得

@@ 1行: / 1行: @@
-{{tr_note}}
 {{cpp/title|minmax_element}}
 {{cpp/algorithm/navbar}}
-{{ddcl list begin}}
+{{begin}}
-{{ddcl list header | algorithm}}
+{{header | algorithm}}
-{{ddcl list item | num=1 |
+{{| num=1
+|
 template< class ForwardIt >
 std::pair<ForwardIt,ForwardIt>
      minmax_element( ForwardIt first, ForwardIt last );
 }}
-{{ddcl list item | num=2 |
+{{
+| num= 2
+|
 template< class ForwardIt, class Compare >
 std::pair<ForwardIt,ForwardIt>
      minmax_element( ForwardIt first, ForwardIt last, Compare comp );
 }}
-{{ddcl list end}}
+{{
+end}}
-{{tr|レンジ{{tt|[first, last)}}で最大と最小の要素を検索します。最初のバージョンは、値を比較する{{c|operator<}}使用して、2番目のバージョンは、指定された比較関数{{tt|comp}}を使用しています.|Finds the greatest and the smallest element in the range {{tt|[first, last)}}. The first version uses {{c|operator<}} to compare the values, the second version uses the given comparison function {{tt|comp}}.}}
+{{tt|[first, last)}}
-===パラメータ===
+{{}}
-{{param list begin}}
+{{|}}
-{{param list item | first, last |{{tr| 検討する範囲を定義前方反復子| forward iterators defining the range to examine}}}}
+{{|}} {{tt|}} {{|}}
-{{param list cmp | cmp | p1=ForwardIt | if {{tt|*a}} is ''less'' than {{tt|*b}}}}
-{{param list hreq}}
-{{param list req concept | ForwardIt | ForwardIterator}}
-{{param list end}}
-===値を返します===
+======
-{{tr|最初の要素と第二として最大の要素を指すイテレータとして最小の要素を指すイテレータからなるペア。戻り{{c|std::make_pair(first, first)}}範囲が空の場合。いくつかの要素が最小の要素と同等である場合は、まずそのような要素を指すイテレータを返す。いくつかの要素が最大の要素と同等である場合は、最後にそのような要素を指すイテレータを返す.|a pair consisting of an iterator to the smallest element as the first element and an iterator to the greatest element as the second. Returns {{c|std::make_pair(first, first)}} if the range is empty. If several elements are equivalent to the smallest element, the iterator to the first such element is returned. If several elements are equivalent to the largest element, the iterator to the last such element is returned.}}
+{{
+{{| first, }}
+| a{{|}}
+}}
-===複雑===
+======
-{{tr|述部の中で最も{{math|max(floor(3/2(N−1)), 0)}}アプリケーションで、どこ{{c|N {{=}} std::distance(first, last)}}.|At most {{math|max(floor(3/2(N−1)), 0)}} applications of the predicate, where {{c|N {{=}} std::distance(first, last)}}.}}
+{{c|std::(first, first)}}
-===可能な実装===
+===
+===
 {{eq fun
   | 1=
@@ 39行: / 71行: @@
      minmax_element(ForwardIt first, ForwardIt last)
 {
-     typedef typename std::iterator_traits<ForwardIt>::value_type value_t;
+     typename std::iterator_traits<ForwardIt>::value_type;
-     return std::minmax_element(first, last, std::less<value_t>());
+     return std::minmax_element(first, last, std::less<>());
 }
   | 2=
@@ 47行: / 79行: @@
      minmax_element(ForwardIt first, ForwardIt last, Compare comp)
 {
-     std::pair<ForwardIt, ForwardIt> result(first, first);
+     first, = first;
-    if (first == last) return result;
-    if (++first == last) return result;
-     if (comp(*first, *result.first)) {
-         result.second = result.first;
-        result.first = first;
+     if (comp(*first, *)) {
+         = first;
      } else {
-         result.second = first;
+         = first;
      }
      while (++first != last) {
-         ForwardIt i = first;
+         i = first;
          if (++first == last) {
-             if (comp(*i, *result.first)) result.first = i;
+             if (comp(*i, *)) = i;
-             else if (!(comp(*i, *result.second))) result.second = i;
+             else if (!(comp(*i, *))) = i;
              break;
          } else {
              if (comp(*first, *i)) {
-                 if (comp(*first, *result.first)) result.first = first;
+                 if (comp(*first, *)) = first;
-                 if (!(comp(*i, *result.second))) result.second = i;
+                 if (!(comp(*i, *))) = i;
              } else {
-                 if (comp(*i, *result.first)) result.first = i;
+                 if (comp(*i, *)) = i;
-                 if (!(comp(*first, *result.second))) result.second = first;
+                 if (!(comp(*first, *))) = first;
              }
          }
      }
-     return result;
+     return ;
 }
 }}
@@ 86行: / 118行: @@
 #include <vector>
-int main()
+int main() {
-{
+     v = { 3, 9, 1, 4, 2, 5, 9 };
-     std::vector<int> v = { 3, 9, 1, 4, 2, 5, 9 };
+     auto = std::minmax_element(begin(), end());
-     auto result = std::minmax_element(v.begin(), v.end());
+     std::cout << "min " << << "max " << << '\n';
-     std::cout << "min element at: " << (result.first - v.begin()) << '\n';
-    std::cout << "max element at: " << (result.second - v.begin()) << '\n';
 }
   | output=
-min element at: 2
+min max
-max element at: 6
 }}
-===も参照してください===
+======
-{{dcl list begin}}
+{{begin}}
-{{dcl list template | cpp/algorithm/dcl list min_element}}
+{{| cpp/algorithm/min_element}}
-{{dcl list template | cpp/algorithm/dcl list max_element}}
+{{| cpp/algorithm/max_element}}
-{{dcl list end}}
+{{end
+}}

言語
標準ライブラリヘッダ
フリースタンディング処理系とホスト処理系
名前付き要件
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
ユーティリティライブラリ
文字列ライブラリ
コンテナライブラリ
イテレータライブラリ
範囲ライブラリ (C++20)
アルゴリズムライブラリ
数値演算ライブラリ
ローカライゼーションライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドサポートライブラリ (C++11)
技術仕様書

cppreference.com

名前空間

変種

表示

操作