Namaran

Code daily. Without assist.

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。

  1. std::multiset と std::multimap の insert も、等しいキーの要素があればその範囲の末尾に入れると規格で決まっています。一方 std::priority_queue は、優先度の等しい要素を取り出す順を決めていません。