この記事のポイント

  • lower_bound・upper_boundの正しい使い方をレビューアー視点で整理
  • 境界条件・前提条件（ソート済み）を設計責任として理解
  • よくある誤用・見逃されるバグを事前にレビューで検出する視点を学べる

そもそもlower_bound・upper_boundとは

C++標準ライブラリのlower_bound・upper_boundは、ソート済み区間に対する二分探索アルゴリズムです。
std::algorithmに含まれ、次のように動作します。

関数 目的 戻り値
lower_bound(first, last, value) value >= 要素 の先頭位置 最初のvalue以上のイテレータ
upper_bound(first, last, value) value > 要素 の先頭位置 最初のvalueより大きいイテレータ
  • ソート済みであることが利用前提
  • 二分探索により O(logN) 時間で探索可能
  • 境界値含有有無の制御ができる

なぜこれをレビューするのか

レビューアー視点

lower_bound/upper_boundは極めて強力ですが、以下のような前提条件設計責任が発生します。

  • ソート保証責任の所在
    → 誰がソート済み保証を持つかを明文化しているか

  • 比較関数統一責任
    → ソート時と探索時の比較関数が一致しているか

  • 境界条件バグの温床
    → lower/upperを混同して off-by-one を誘発していないか

  • 二分探索を隠蔽する責務整理
    → 汎用アルゴリズム責務をドメイン層に持ち込んでいないか

開発者視点

  • ソート前提を軽視
  • 比較関数ズレに気付かない
  • lower/upperの使い分け曖昧
  • end()到達後の処理設計が甘い
  • 重複要素存在下で想定外の結果を得る

レビューアーはこれらのアルゴリズム前提責任漏れを検出します。

良い実装例

ユースケース：APIリクエスト時刻の一定期間抽出

良い実装例：lower_bound/upper_boundの正確活用 
#include <vector>
#include <string>
#include <algorithm>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    int64_t requestedAt;
};

class RequestLogIndex {
public:
    void add(const ApiRequestLog& log) {
        logs_.push_back(log);
    }

    void sortByTime() {
        std::sort(logs_.begin(), logs_.end(), [](const auto& a, const auto& b) {
            return a.requestedAt < b.requestedAt;
        });
    }

    std::vector<ApiRequestLog> findInRange(int64_t from, int64_t to) const {
        auto comp = [](const ApiRequestLog& log, int64_t t) {
            return log.requestedAt < t;
        };

        auto lower = std::lower_bound(logs_.begin(), logs_.end(), from, comp);
        auto upper = std::upper_bound(logs_.begin(), logs_.end(), to, comp);

        return std::vector<ApiRequestLog>(lower, upper);
    }

private:
    std::vector<ApiRequestLog> logs_;
};
  • ソート保証責任がクラス内に閉じている
  • 比較関数が統一され型安全
  • 境界条件が明確整理

レビュー観点

  • ソート保証責任が明文化されているか
  • 比較関数の一致性を設計時に確認しているか
  • 境界条件の意図（以上/より大/未満）が正しく伝達されているか
  • end()到達ケースへの防御設計がなされているか
  • 複合キーソート時の比較責務整理が行われているか

良くない実装例: ケース1

以下はソート前提保証が欠如しているケースです。

ソート保証欠如例 
std::vector<ApiRequestLog> findInRange(int64_t from, int64_t to) const {
    auto lower = std::lower_bound(logs_.begin(), logs_.end(), from,
        [](const ApiRequestLog& log, int64_t t) {
            return log.requestedAt < t;
        });

    auto upper = std::upper_bound(logs_.begin(), logs_.end(), to,
        [](const ApiRequestLog& log, int64_t t) {
            return log.requestedAt < t;
        });

    return std::vector<ApiRequestLog>(lower, upper);
}

@Reviewer
ソート保証が無いままlower_boundを使用しています。事前にsortByTime実行が必須です。

問題点

  • ソート保証責任を呼び出し側に丸投げ
  • ソート忘れバグの温床

改善例

修正例：内部で自動ソート保証 
void prepare() {
    std::sort(logs_.begin(), logs_.end(), [](const auto& a, const auto& b) {
        return a.requestedAt < b.requestedAt;
    });
}
  • ソート実行契機をレビュー時に明示
  • 自動整理 or API契約で強制保証

良くない実装例: ケース2

次は比較関数の統一性を欠いている例です。

比較関数ズレ例 
auto lower = std::lower_bound(logs_.begin(), logs_.end(), from,
    [](const ApiRequestLog& log, int64_t t) { return log.requestedAt <= t; });

@Reviewer
比較関数がズレています。lower_boundは「strict weak ordering」で比較一致が必要です。<比較を使用してください。

問題点

  • <= を使うと境界位置が壊れる
  • 標準ライブラリ契約を破壊

改善例

修正例：strict weak ordering徹底 
[](const ApiRequestLog& log, int64_t t) {
    return log.requestedAt < t;
}
  • lower_bound比較関数は常に<演算を用いるのが正道

良くない実装例: ケース3

次はlower/upperの使い分けを誤って off-by-one バグになる例です。

境界条件混同例 
auto upper = std::lower_bound(logs_.begin(), logs_.end(), to,
    [](const ApiRequestLog& log, int64_t t) { return log.requestedAt < t; });

@Reviewer
終端条件にupper_boundではなくlower_boundを誤使用しています。範囲抽出が壊れます。

問題点

  • 「以上」と「超え」の混同
  • 結果件数が設計とズレる

改善例

修正例：範囲抽出整理 
auto lower = std::lower_bound(...);
auto upper = std::upper_bound(...);

PlantUMLで責任構造整理

UML Diagram

観点チェックリスト

まとめ

lower_bound/upper_boundはソート済み前提という前提条件を強く要求するAPIです。
レビューアーは表面的な動作だけでなく、

  • ソート保証の所在
  • 比較関数の一致性
  • 境界条件の明文化
  • API契約責任

これら設計論点を徹底的にレビュー対象として読み解きます。
レビュー現場では「バグ温床の二分探索」を設計責務化していく視点が不可欠です。