std::set の lower_bound は、C++ の標準ライブラリの中でも非常に重要でありながら、直感だけで使うと誤解しやすい関数のひとつです。
表面的には単純に見えるものの、比較規則やコンテナの性質を正しく理解していないと、意図しない動作につながることがあります。
ここでは、lower_bound の意味、std::set 特有の挙動、upper_bound との違い、そして実務や競技プログラミングでの使いどころまでを、コードを使わずに丁寧に整理します。
std::set の前提知識
std::set は、要素を常に一定の順序で保持する連想コンテナです。
格納される値は自動的に整列され、同じ値を複数保持することはできません。
内部構造について C++ 標準は具体的な実装方式を規定していませんが、ほとんどの処理が対数時間で行われることが保証されています。
この計算量特性を満たすため、実装上は赤黒木などの平衡二分探索木が採用されることが一般的です。
std::set のイテレータは双方向イテレータであり、前後への移動は可能ですが、配列のようなランダムアクセスはできません。
lower_bound の基本的な意味
lower_bound は、「指定したキー以上の値が最初に現れる位置」を指し示すための関数です。
ここで重要なのは、「一致する要素を探す関数」ではなく、「境界となる位置を探す関数」であるという点です。
対象となる値がコンテナ内に存在しない場合でも、条件を満たす次の要素が返される点が、検索系関数との大きな違いです。
規格上の厳密な定義
lower_bound は、単純に数値の大小だけで動作しているわけではありません。
std::set では、要素の並び順は比較関数によって定義されており、lower_bound もその比較関数に基づいて判定されます。
規格上は、「指定したキーと比較したときに『小さい』と判定されなくなる最初の要素」を返す、という定義になります。
標準の昇順比較を用いている場合、この条件は直感どおり「キー以上の最初の要素」と一致します。
一方、降順などのカスタム比較を使っている場合には、直感的な「以上」「以下」という感覚が逆転することがあるため、比較規則を前提に考える必要があります。
見つからなかった場合の挙動
条件を満たす要素が存在しない場合、lower_bound はコンテナの末尾を示す位置を返します。
この位置は「最後の要素の次」を意味しており、実際の要素を指しているわけではありません。
そのため、返された位置をそのまま参照できるとは限らず、必ず有効な要素かどうかを確認する必要があります。
find との違い
find は完全一致する要素を探すための関数であり、存在しない場合は何も見つからないという結果になります。
一方、lower_bound は一致しなくても「条件を満たす最初の位置」を返します。
このため、境界値やしきい値を扱う処理では lower_bound が適しており、単純な存在確認には find の方が意図を表現しやすい場合があります。
upper_bound との関係
upper_bound は、指定したキーよりも「大きい」と判定される最初の位置を返します。
lower_bound が「境界の下限」を示すのに対し、upper_bound は「境界の上限」を示す関数です。
両者を組み合わせることで、特定の範囲に含まれる要素を効率よく扱うことができます。
実務・競技プログラミングでの典型的な用途
lower_bound は、次に使える最小の値を探す処理や、動的に変化する集合に対する境界検索で特に威力を発揮します。
配列のように事前に並びが固定されていない状況でも、要素を追加・削除しながら高速に境界検索が行える点が、std::set と lower_bound の組み合わせの強みです。
まとめ
std::set の lower_bound は、単なる検索関数ではなく、「順序付き集合における境界を求めるための道具」です。
比較関数、末尾の扱い、find や upper_bound との役割の違いを正しく理解することで、安全かつ意図どおりに使うことができます。
この関数を正確に理解しているかどうかは、C++ におけるコンテナ操作の理解度を測るひとつの指標とも言えるでしょう。
以上、C++のstd::set における lower_boundについてでした。
最後までお読みいただき、ありがとうございました。
