2026-10-18
job_queue.cpp
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Job {
int prio;
std::string name;
};
int main() {
std::vector<Job> queue;
for (const Job& job : {Job{1, "mail"}, Job{2, "backup"}, Job{1, "alert"}}) {
auto at = std::ranges::lower_bound(queue, job.prio, {}, &Job::prio);
queue.insert(at, job);
}
for (const Job& job : queue) {
std::cout << job.name << '\n';
}
}
このコードは、届いたジョブを優先度の値 prio が小さい順に queue へ並べるもので、同じ優先度のジョブどうしは届いた順に並べる約束です。ジョブは main の初期化子リストの3つで、この順に届きます。いまの出力は alert、mail、backup の3行です。本来の出力は mail、alert、backup です。
Answer
Wrong
auto at = std::ranges::lower_bound(queue, job.prio, {}, &Job::prio);
lower_bound は、prio が job.prio 以上になる最初の位置を返します。同じ優先度のジョブが既にあれば、その位置はそれらの並びの先頭なので、新しいジョブは先に届いていたジョブの前に入ります。alert が届いた時点の queue は mail、backup で、lower_bound が mail の位置を返すため、alert が mail の前に入ります。
Right
auto at = std::ranges::upper_bound(queue, job.prio, {}, &Job::prio);
upper_bound は prio が job.prio より大きい最初の位置を返し、これは同じ優先度のジョブが並ぶ範囲のすぐ後ろです。新しいジョブはその範囲の末尾に付くので、同じ優先度の中では届いた順が保たれます。等しい値の範囲は lower_bound から upper_bound までで、どちらの端に入れるかによって、同じ優先度の中が先着順になるか後着順になるかが決まります1。
std::multisetとstd::multimapのinsertも、等しいキーの要素があればその範囲の末尾に入れると規格で決まっています。一方std::priority_queueは、優先度の等しい要素を取り出す順を決めていません。