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