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

履歴 編集

function
<map>

std::map::upper_bound

iterator upper_bound(const key_type& x);             // (1)

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

const_iterator upper_bound(const key_type& x) const; // (3)

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

概要

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

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

内部的に、map コンテナ内の全ての要素は常に比較オブジェクトで定義された基準に従って並ぶため、この関数が返す値に続く全ての要素は 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() について対数時間。

備考

#include <iostream>
#include <string>
#include <map>

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

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

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

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

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

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

出力

B,1
C,4
D,5

B,1
C,4
D,5

関連項目

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

参照