最終更新日時: 2026年04月13日 15時17分49秒 (JST)
teruyamato0731 が更新

履歴 編集

function template
<algorithm>

# std::minmax_element(C++11)

    namespace std {
      template<class ForwardIterator>
      pair<ForwardIterator, ForwardIterator>
        minmax_element(ForwardIterator first,
                       ForwardIterator last); // (1) C++11

      template<class ForwardIterator, class Compare>
      pair<ForwardIterator, ForwardIterator>
        minmax_element(ForwardIterator first,
                       ForwardIterator last,
                       Compare comp);         // (2) C++11

      template <class ExecutionPolicy, class ForwardIterator>
      pair<ForwardIterator, ForwardIterator>
        minmax_element(ExecutionPolicy&& exec,
                       ForwardIterator first,
                       ForwardIterator last); // (3) C++17

      template <class ExecutionPolicy, class ForwardIterator, class Compare>
      pair<ForwardIterator, ForwardIterator>
        minmax_element(ExecutionPolicy&& exec,
                       ForwardIterator first,
                       ForwardIterator last,
                       Compare comp);         // (4) C++17
    }

## 概要

イテレータ範囲`[first, last)`のうち、最小要素を指すイテレータと最大要素を指すイテレータの組を取得する。

この関数の戻り値となるイテレータの`pair`では、`first`に最小要素を指すイテレータ、`second`に最大要素を指すイテレータが代入される。

## 戻り値

`operator<` もしくは `comp` を比較基準とした際の、最小の要素を指すイテレータを `first`、最大の要素を指すイテレータを `second` に持つ `pair` オブジェクトを返す。

ただし、`first == last` の場合には、`make_pair(first, first)`を返す。

## 計算量

`n` を範囲の要素数とする場合、`max(floor(3(n - 1) / 2), 0)` 回の述語適用を行う。

## 備考

- `comp` は 2 引数の関数オブジェクトで、1 番目の引数が 2 番目の引数「より小さい」場合に `true` を、そうでない場合に `false` を返すものとして扱われる。
- 最小の要素が複数ある場合、`min_element` と同様、最も左側（`first` に近い方）にある要素を指すイテレータを返す。
  一方、最大の要素が複数ある場合、`max_element` と異なり、最も右側（`last` に近い方）にあるイテレータを返す。
- 最小の要素と最大の要素の両方が必要な場合には、`min_element` と `max_element` をそれぞれ呼び出すよりも本関数を呼び出した方が、計算量の点で効率的である。
  ただし、上記の通り最大の要素に関しては `max_element` と結果が異なる可能性があるため、注意する必要がある。

## 例

    #include <cassert>
    #include <algorithm>
    #include <vector>

    int main()
    {
      std::vector<int> v = {3, 1, 4};

      auto i = std::minmax_element(v.begin(), v.end());
      assert(*i.first == 1);
      assert(*i.second == 4);

      auto j = std::minmax_element(v.begin(), v.end(), [](int a, int b) {
                                    return a > b;
                                  });
      assert(*j.first == 4);
      assert(*j.second == 1);
    }

### 出力

## 実装例

    template <class ForwardIterator, class Compare>
    std::pair<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp)
    {
      // 結果用オブジェクト
      std::pair<ForwardIterator, ForwardIterator> result(first, first);

      // イテレータ範囲の要素数が 0 か 1 だったら、そのまま result を返す
      if (first != last && ++first != last) {
        // 最初の 2 個を比較して、小さい方を .first に、大きい方を .second に設定
        if (comp(*first, *result.first))
          result.first = first;
        else
          result.second = first;

        // 残りの要素を 2 個ずつ繰り返し
        while (++first != last) {
          ForwardIterator prev = first;

          // 残りの要素が 1 個しか無かったら、.first と .second の両方の要素と比較して、
          // 必要に応じて結果を更新後、ループを抜ける
          if (++first == last) {
            if (comp(*prev, *result.first))
              result.first = prev;
            else if (!comp(*prev, *result.second))
              result.second = prev;
            break;
          }

          // 残りの要素が 2 個以上あれば、まずその 2 個を比較してから、小さい方を .first と、
          // 大きい方を .second と比較して、必要に応じて結果を更新
          if (comp(*first, *prev)) {
            if (comp(*first, *result.first))
              result.first = first;
            if (!comp(*prev, *result.second))
              result.second = prev;
          } else {
            if (comp(*prev, *result.first))
              result.first = prev;
            if (!comp(*first, *result.second))
              result.second = first;
          }
        }
      }
      return result;
    }

    // operator< 用の関数オブジェクト（std::less は特殊化されているかもしれないので）
    struct less_inner {
      template <class T>
      bool operator()(const T& lhs, const T& rhs) const { return bool(lhs < rhs); }
    };

    template <class ForwardIterator>
    inline std::pair<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last)
    {
      return std::minmax_element(first, last, less_inner());
    }

## バージョン

### 言語

- C++11

### 処理系

- Clang: ??
- GCC: 4.7.0 ✅
- ICC: ??
- Visual C++: 2010 ✅, 2012 ✅, 2013 ✅, 2015 ✅

## 関連項目

- `ranges::minmax_element`

## 参照

- N1840 C++0x Proposal: Function template `std::minmax` and / or algorithm `std::minmax_element`
- N1990 Proposed Text for `minmax` (N1840)
- LWG Issue 715. `minmax_element` complexity is too lax