Skip to content

Latest commit

 

History

History
128 lines (100 loc) · 4.62 KB

upper_bound.md

File metadata and controls

128 lines (100 loc) · 4.62 KB

upper_bound

  • flat_map[meta header]
  • std[meta namespace]
  • flat_multimap[meta class]
  • function[meta id-type]
  • cpp23[meta cpp]
iterator upper_bound(const key_type& x);           // (1) C++23
constexpr iterator upper_bound(const key_type& x); // (1) C++26

template <class K>
iterator upper_bound(const K& x);           // (2) C++23
template <class K>
constexpr iterator upper_bound(const K& x); // (2) C++26

const_iterator upper_bound(const key_type& x) const;           // (3) C++23
constexpr const_iterator upper_bound(const key_type& x) const; // (3) C++26

template <class K>
const_iterator upper_bound(const K& x) const;           // (4) C++23
template <class K>
constexpr const_iterator upper_bound(const K& x) const; // (4) C++26

概要

x より大きいキーを持つコンテナ内の最初の要素を指すイテレータを返す（コンテナの比較オブジェクトを使う）。

lower_bound() と異なり、このメンバ関数は x と等しいときは要素へのイテレータを返さず、それは大きい場合にのみ要素へのイテレータを返す。

内部的に、flat_multimap コンテナ内の全ての要素は常に比較オブジェクトで定義された基準に従って並ぶため、この関数が返す値に続く全ての要素は x より大きいことに注意。

  • (1) : key_type型のキーを受け取り、そのキーより大きい最初の要素へのイテレータを取得する。
  • (2) : key_typeと比較可能なK型のキーを受け取り、そのキーより大きい最初の要素へのイテレータを取得する。
  • (3) : constな*thisオブジェクトにおいて、key_type型のキーを受け取り、そのキーより大きい最初の要素へのイテレータを取得する。
  • (4) : constな*thisオブジェクトにおいて、key_typeと比較可能なK型のキーを受け取り、そのキーより大きい最初の要素へのイテレータを取得する。

戻り値

  • (1), (3) : キーxより大きい最初の要素へのイテレータを返す。そのような要素がない場合は、end()を返す。
  • (2), (4) : key_compare型の関数オブジェクトをc、コンテナ内の各要素が持つキーをkとして、キーが小さくないか判定する式c(x, k)がtrueとなる要素へのイテレータを返す。そのような要素がない場合は、end() を返す。

計算量

size() について対数時間。

備考

  • (2), (4) : この関数がオーバーロード解決に参加する条件は、find()メンバ関数の備考欄を参照。

例

#include <flat_map>
#include <iostream>
#include <string>

int main()
{
  // (1)
  {
    std::flat_multimap<std::string, int> fm = {
      {"A", 3},
      {"B", 1},
      {"C", 4},
      {"D", 5}
    };

    // B以上D以下の範囲を取得
    decltype(fm)::iterator it = fm.lower_bound("B");
    decltype(fm)::iterator last = fm.upper_bound("D");

    while (it != last) {
      std::cout << it->first << ',' << it->second << std::endl;
      ++it;
    }
    std::cout << std::endl;
  }

  // (2)
  {
    std::flat_multimap<std::string, int, std::less<>> fm = {
      {"A", 3},
      {"B", 1},
      {"C", 4},
      {"D", 5}
    };

    // std::lessのvoidに対する特殊化を使用することで、
    // 文字列リテラルをlower_bound()関数の引数として渡した際に、
    // std::string型の一時オブジェクトが生成されない。
    decltype(fm)::iterator it = fm.lower_bound("B");
    decltype(fm)::iterator last = fm.upper_bound("D");

    while (it != last) {
      std::cout << it->first << "," << it->second << std::endl;
      ++it;
    }
  }
}
  • upper_bound[color ff0000]
  • fm.lower_bound[link lower_bound.md]
  • std::less[link /reference/functional/less.md]

出力

B,1
C,4
D,5

B,1
C,4
D,5

関連項目

名前 説明
lower_bound 与えられた値よりも小さくない最初の要素へのイテレータを返す
equal_range 指定したキーにマッチする要素範囲を返す
find 指定したキーで要素を探す
count 指定したキーにマッチする要素の数を返す

参照