4. equal_range

最終更新日時(UTC):
が更新

履歴 編集

function template
<algorithm>

std::equal_range

namespace std {
  template <class ForwardIterator, class T>
  pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last,
                const T& value);      // (1) C++03

  template <class ForwardIterator, class T>
  constexpr pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last,
                const T& value);      // (1) C++20

  template <class ForwardIterator, class T, class Compare>
  pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last,
                const T& value,
                Compare comp);        // (2) C++03

  template <class ForwardIterator, class T, class Compare>
  constexpr pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last,
                const T& value,
                Compare comp);        // (2) C++20
}

概要

lower_bound()とupper_bound()の結果を組で取得する。

要件

[first,last) の要素 e は e < value および !(value < e) 、あるいは comp(e, value) および !comp(value, e) によって区分化されていなければならない。

また、[first, last) の要素 e は全て暗黙に、e < value が !(value < e) または comp(e, value) が !comp(value, e) を意味している必要がある。

戻り値

計算量

最大で 2 * log2(last - first) + O(1) 回の比較を行う

例

#include <iostream>
#include <vector>
#include <algorithm>

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

  std::sort(v.begin(), v.end());

  // 3以上の要素と、3より大きい要素を二分探索で検索
  auto result = std::equal_range(v.begin(), v.end(), 3);

  std::cout << *result.first << std::endl;
  std::cout << *result.second << std::endl;
}

出力

3
4

参照