Namaran

Code daily. Without assist.

2026-10-15

events_at.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using Entry = std::pair<int, std::string>;

int main() {
    std::vector<Entry> log = {{9, "boot"}, {10, "login"}, {10, "mail"}, {11, "exit"}};
    Entry key{10, ""};
    auto lo = std::lower_bound(log.begin(), log.end(), key);
    auto hi = std::upper_bound(log.begin(), log.end(), key);
    for (auto it = lo; it != hi; ++it) {
        std::cout << it->second << '\n';
    }
}

log は(時刻, 出来事)の組を時刻の順に並べた記録で、このコードは時刻 10 の出来事を1行に1つずつ出力するつもりのものです。実行すると、いまは何も出力されません。本来の出力は login と mail の2行です。

Answer

Wrong

Entry key{10, ""};
auto lo = std::lower_bound(log.begin(), log.end(), key);
auto hi = std::upper_bound(log.begin(), log.end(), key);

std::pair どうしの < は、first を比べて等しければ second を比べます。辞書の見出しと同じこの並べ方を辞書式順序(lexicographic order)といいます。空文字列はどの文字列よりも前に来るので、key は (9, "boot") より大きく、(10, "login") より小さくなります。

lower_bound が返す key 以上の最初の要素は (10, "login") で、upper_bound が返す key より大きい最初の要素も (10, "login") です。lo と hi が同じ位置なのでループは1回も回りません。second まで比べる < にとって、(10, "") と等しい要素は log に1つも無いからです。

Right

auto [lo, hi] = std::ranges::equal_range(log, 10, {}, &Entry::first);

std::ranges::equal_range は lower_bound と upper_bound の位置を組で返します。4つ目の引数は射影(projection)と呼ばれ、比べる前に各要素から &Entry::first で時刻だけを取り出します。比べるのが時刻と 10 だけになるので、時刻 10 の2つの要素が [lo, hi) に入ります1。

  1. 射影を使わずに直すなら、first だけを比べる比較関数 [](const Entry& a, const Entry& b) { return a.first < b.first; } を、lower_bound と upper_bound の両方に4つ目の引数として渡します。片方にだけ渡すと、2つの位置が別の順序で求められてしまいます。