20.2 ค้นหาใน set และ multiset

set เรียงค่าไว้ให้ตลอดเวลา จึงถามได้มากกว่าแค่ว่ามีหรือไม่มี เช่น รถเมล์คันถัดไปออกกี่โมง สถานีที่ใกล้บ้านที่สุดอยู่ตรงไหน หนังสือเล่มแพงที่สุดที่ราคาไม่เกินงบคือเล่มไหน คำถามแบบนี้ในหน้า 19.2 ตอบด้วย lower_bound บน vector ที่เรียงแล้ว แต่ vector เรียงครั้งเดียวแล้วต้องอยู่นิ่ง ถ้ามีการเพิ่มหรือลบแทรกระหว่างคำถาม ต้องใช้ set ส่วนครึ่งหลังของหน้าเป็นเรื่อง multiset สำหรับงานที่ค่าซ้ำได้

lower_bound และ upper_bound ของ set

ตารางรถเมล์บอกเวลาออกเป็นนาทีนับจากเที่ยงคืน เช่น 430 คือ 7 โมง 10 นาที ผู้โดยสารมาถึงป้ายเวลา now อยากรู้ว่าคันแรกที่ยังไม่ออกไปคือคันไหน รถที่ออกเวลาเดียวกับที่มาถึงพอดียังทัน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    set<int> departures;
    for (int i = 0; i < n; i++) {
        int minute;
        cin >> minute;
        departures.insert(minute);
    }
    for (int i = 0; i < q; i++) {
        int now;
        cin >> now;
        auto it = departures.lower_bound(now);
        if (it == departures.end()) {
            cout << now << ": no more buses\n";
        } else {
            cout << now << ": next bus at " << *it << '\n';
        }
    }
    return 0;
}

6 4
430 360 545 395 480 610
400
430
611
0

400: next bus at 430
430: next bus at 430
611: no more buses
0: next bus at 360

departures.lower_bound(now) คืน iterator ของค่าแรกที่ มากกว่าหรือเท่ากับ now ความหมายเดียวกับ lower_bound ของ vector ในหน้า 19.2 แต่เขียนเป็นคำสั่งของ set เอง เรียกผ่านจุดหลังชื่อ set และส่งแค่ค่าที่หา ถ้าไม่มีค่าไหนผ่านเงื่อนไข จะได้ end() ซึ่งต้องเช็กก่อนอ่านค่าทุกครั้ง

คู่ของมันคือ upper_bound(x) ค่าแรกที่ มากกว่า x อย่างเดียว ไม่นับที่เท่ากัน ส่วนคำถามฝั่งตรงข้าม เช่น คันล่าสุดที่ออกไปแล้ว ใช้ prev ถอยหลังหนึ่งก้าวจากผลของสองคำสั่งนี้

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> departures = {360, 395, 430, 480, 545, 610};
    cout << *departures.lower_bound(430) << '\n';
    cout << *departures.upper_bound(430) << '\n';
    auto it = departures.upper_bound(500);
    cout << *prev(it) << '\n';
    return 0;
}

430
480
480

บรรทัดที่ 9 กับ 10 หาคันสุดท้ายที่ออกไม่เกินเวลา 500 ค่าแรกที่มากกว่า 500 คือ 545 ถอยกลับหนึ่งก้าวได้ 480 สี่คำถามที่เจอบ่อยสรุปได้แบบนี้

อยากได้	เขียน	ไม่มีคำตอบเมื่อ
ค่าน้อยสุดที่ ≥ x	`s.lower_bound(x)`	ได้ `s.end()`
ค่าน้อยสุดที่ > x	`s.upper_bound(x)`	ได้ `s.end()`
ค่ามากสุดที่ ≤ x	`prev(s.upper_bound(x))`	`s.upper_bound(x)` เป็น `s.begin()`
ค่ามากสุดที่ < x	`prev(s.lower_bound(x))`	`s.lower_bound(x)` เป็น `s.begin()`

ถอยหลังจาก begin() ไม่ได้ เพราะไม่มีตัวก่อนหน้าแล้ว จึงต้องเช็กก่อนเรียก prev ทุกครั้ง

ค่าที่ใกล้ที่สุด

ทางหลวงมีสถานีชาร์จรถไฟฟ้าที่ทยอยเปิดเพิ่ม + km คือเปิดสถานีที่กิโลเมตรนั้น ? km คือมีคนอยู่ที่กิโลเมตรนั้นถามว่าสถานีที่ใกล้ที่สุดห่างไปกี่กิโลเมตร ข้างหน้าหรือข้างหลังก็ได้

สถานีที่ใกล้ที่สุดต้องเป็นหนึ่งในสองตัว คือตัวแรกที่อยู่ที่ km หรือเลยไปข้างหน้า กับตัวสุดท้ายที่อยู่ข้างหลัง ตัวอื่นไกลกว่าสองตัวนี้แน่นอน ทั้งสองตัวอยู่ติดกันใน set พอดี

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    set<int> stations;
    for (int i = 0; i < q; i++) {
        char op;
        int km;
        cin >> op >> km;
        if (op == '+') {
            stations.insert(km);
            continue;
        }
        if (stations.empty()) {
            cout << "none\n";
            continue;
        }
        int best = INT_MAX;
        auto it = stations.lower_bound(km); // (1)!
        if (it != stations.end()) {
            best = min(best, *it - km);
        }
        if (it != stations.begin()) { // (2)!
            best = min(best, km - *prev(it));
        }
        cout << best << '\n';
    }
    return 0;
}

สถานีแรกที่อยู่ที่ km พอดีหรือข้างหน้า ถ้าเป็น end() แปลว่าข้างหน้าไม่มีสถานีเลย
ตัวก่อนหน้า it คือสถานีสุดท้ายที่อยู่ข้างหลัง มีได้ก็ต่อเมื่อ it ไม่ใช่ตัวแรกของ set ถ้า it เป็น end() แต่ set ไม่ว่าง prev(it) ก็คือตัวสุดท้ายพอดี ใช้ได้

none
70
20
45
280

คำถามที่ km 75 อยู่กึ่งกลางระหว่าง 30 กับ 120 ได้ 45 ทั้งสองทาง ส่วนคำถามที่ km 400 ไม่มีสถานีข้างหน้า it เป็น end() จึงเหลือแค่ตัวข้างหลังคือ 120 INT_MAX คือค่ามากสุดของ int จาก climits ใช้เป็นค่าเริ่มต้นที่อะไรก็น้อยกว่า

แต่ละคำถามใช้ lower_bound หนึ่งครั้งกับ prev หนึ่งครั้ง จึงเป็น O(log N) ถ้าเก็บสถานีใน vector แล้วไล่ดูทุกสถานี จะเป็น O(N) ต่อคำถาม มีสถานีหนึ่งแสนกับคำถามหนึ่งแสนก็เป็นงาน 10¹⁰ ก้าว ไม่ทันแน่นอน แบบฝึกหัดข้อ 5 ให้ลองวัดเอง

อย่าใช้ std::lower_bound กับ set

ในบทที่ 19 เขียน lower_bound(v.begin(), v.end(), x) กับ vector จนชินมือ เลยเผลอเขียนแบบเดียวกันกับ set ซึ่งคอมไพล์ผ่าน ไม่มีคำเตือน และได้คำตอบถูกทุกข้อ แต่ช้ามาก โปรแกรมนี้ใส่ค่าสุ่ม n ค่าลง set แล้วถาม n ครั้งด้วยสองวิธี จับเวลาแยกกัน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    mt19937 rng(2569);
    set<int> s;
    for (int i = 0; i < n; i++) {
        s.insert(rng() % 1000000000);
    }
    vector<int> queries(n);
    for (int i = 0; i < n; i++) {
        queries[i] = rng() % 1000000000;
    }

    clock_t start = clock();
    long long total1 = 0;
    for (int x : queries) {
        auto it = s.lower_bound(x);
        if (it != s.end()) {
            total1 += *it;
        }
    }
    clock_t middle = clock();
    long long total2 = 0;
    for (int x : queries) {
        auto it = lower_bound(s.begin(), s.end(), x);
        if (it != s.end()) {
            total2 += *it;
        }
    }
    clock_t end = clock();

    cout << total1 << ' ' << total2 << '\n';
    cout << fixed << setprecision(3);
    cout << "s.lower_bound:    " << (double)(middle - start) / CLOCKS_PER_SEC << " seconds\n";
    cout << "std::lower_bound: " << (double)(end - middle) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

mt19937 เป็นตัวสุ่มของ C++ ที่ให้เลขได้ถึงราว 4 × 10⁹ ต่างจาก rand() บน Windows ที่ให้ได้แค่ 32767 เลข 2569 ในวงเล็บคือจุดเริ่ม รันกี่ครั้งก็ได้ชุดเดิม total1 กับ total2 พิมพ์ไว้ยืนยันว่าสองวิธีได้คำตอบเดียวกัน

วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 แรม 32 GB ระบบ Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks ตัวเลขเป็นวินาที ช่องที่ N ไม่เกิน 2 × 10⁴ เป็นค่ากลางของการรันสามครั้ง ช่อง std::lower_bound แบบ Code::Blocks ที่ N = 5 × 10⁴ รันครั้งเดียวเพราะนานเกือบสองนาที

N	`s.lower_bound` แบบ -O2	`std::lower_bound` แบบ -O2	`std::lower_bound` แบบ Code::Blocks
10⁴	ไม่ถึง 0.001	0.957	1.062
2 × 10⁴	0.001	5.392	6.260
5 × 10⁴	0.005	84.2	104.1

ข้อมูลแค่ห้าหมื่นตัว วิธีที่ผิดใช้เวลาเกินนาที ส่วนวิธีที่ถูกใช้ไม่ถึงหนึ่งในร้อยวินาที ทั้งที่ได้คำตอบเดียวกันทุกข้อ

ทำไมต่างกันขนาดนี้ std::lower_bound คือ binary search ที่ต้องกระโดดไปตรงกลางช่วงได้ทันที ซึ่งทำได้กับ vector เพราะช่องเรียงติดกัน แต่ iterator ของ set เดินได้ทีละก้าวตามที่เห็นในหน้า 20.1 การกระโดดไปตรงกลางจึงกลายเป็นเดินทีละก้าวครึ่งเซต เทียบค่าแค่ราว log N ครั้งก็จริง แต่เดินรวมราว N ก้าวต่อคำถาม คำถาม N ครั้งจึงเป็น O(N²) ส่วน s.lower_bound(x) เดินลงตามกิ่งของต้นไม้ตรงๆ แค่ O(log N)

จำง่ายๆ

กับ set multiset และ map ให้เรียก s.lower_bound(x) s.upper_bound(x) s.count(x) s.find(x) แบบมีจุดหลังชื่อเสมอ ฟังก์ชันชื่อเดียวกันที่รับ begin() กับ end() ใช้กับ vector อาเรย์ และ string

multiset เก็บค่าซ้ำได้

ราคาสินค้า คะแนนสอบ ความสูงของนักเรียน ซ้ำกันได้เสมอ ถ้าใช้ set จะหายไปเงียบๆ แบบที่เห็นในหน้า 20.1 multiset คือ set ที่ยอมให้ค่าซ้ำ ยังเรียงให้ และใช้คำสั่งชุดเดียวกันทุกอย่าง แต่มีสองจุดที่ทำงานต่างไป

#include <bits/stdc++.h>
using namespace std;

int main()
{
    multiset<int> scores = {72, 85, 60, 85, 91, 85};
    for (int s : scores) {
        cout << s << ' ';
    }
    cout << '\n';
    cout << "size " << scores.size() << '\n';
    cout << "count 85: " << scores.count(85) << '\n';

    scores.erase(scores.find(85));
    cout << "after erasing one 85: count " << scores.count(85) << ", size " << scores.size() << '\n';

    scores.erase(85);
    cout << "after erase(85): count " << scores.count(85) << ", size " << scores.size() << '\n';
    return 0;
}

60 72 85 85 85 91
size 6
count 85: 3
after erasing one 85: count 2, size 5
after erase(85): count 0, size 3

count(x) คืนจำนวนตัวที่เท่ากับ x ซึ่งมากกว่า 1 ได้ ใช้เวลา O(log N + k) เมื่อ k คือจำนวนตัวที่นับได้ ถ้ามี x ซ้ำเป็นแสนตัว count ก็ช้าตาม ถ้าแค่อยากรู้ว่ามีไหม ใช้ find(x) != end() เร็วกว่า
erase(x) ลบ ทุกตัวที่เท่ากับ x ถ้าอยากลบตัวเดียว ต้องหา iterator ด้วย find(x) แล้วส่ง iterator นั้นให้ erase และถ้าไม่แน่ใจว่ามี x ต้องเช็กว่า find ไม่ได้คืน end() ก่อน เพราะลบ end() ทำให้โปรแกรมพัง บนเครื่องที่เขียนเอกสารนี้ได้ Process returned -1073740940 (0xC0000374) ทันที

ค่าน้อยสุด ค่ามากสุด lower_bound และ upper_bound ใช้ได้เหมือน set ทุกอย่าง ถ้ามีค่า x ซ้ำหลายตัว lower_bound(x) ชี้ตัวแรกในกลุ่ม และ upper_bound(x) ชี้ตัวแรกที่เลยกลุ่มไปแล้ว

งานที่ multiset ทำได้ดีคือ "หยิบตัวที่ดีที่สุดที่เข้าเงื่อนไขออกไปหนึ่งตัว" เช่น ลูกค้ามีงบ b บาท จะซื้อของชิ้นที่แพงที่สุดที่ไม่เกินงบ หาได้ด้วย prev(ms.upper_bound(b)) แล้วลบชิ้นนั้นทิ้งด้วย erase(it) ทั้งหมดเป็น O(log N) แบบฝึกหัดข้อ 8 เป็นโจทย์แนวนี้

คำสั่งของ set และ multiset	เวลา
`lower_bound(x)` `upper_bound(x)` `find(x)`	O(log N)
`erase(it)` ลบตัวที่ iterator ชี้	O(log N)
`count(x)` และ `erase(x)` ของ multiset	O(log N + k) เมื่อ k คือจำนวนตัวที่เท่ากับ x
`lower_bound(s.begin(), s.end(), x)` กับ set	O(N) ต่อครั้ง ห้ามใช้

ลองทำให้พัง

แบบที่ 1 erase ด้วยค่าใน multiset

ชั้นวางมีสินค้าหลายชิ้นราคาเท่ากัน ลูกค้าซื้อไปทีละชิ้น แต่ใช้ erase(price)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    multiset<int> shelf;
    for (int i = 0; i < n; i++) {
        int price;
        cin >> price;
        shelf.insert(price);
    }
    for (int i = 0; i < q; i++) {
        int price;
        cin >> price;
        shelf.erase(price);
        cout << "sold " << price << ", left " << shelf.size() << '\n';
    }
    return 0;
}

6 2
35 20 35 35 50 20
35
20

sold 35, left 3
sold 20, left 1

ขายไปสองชิ้น ของบนชั้นควรเหลือ 5 กับ 4 แต่เหลือ 3 กับ 1 เพราะขายชิ้นราคา 35 ไปชิ้นเดียว ชิ้นราคา 35 หายไปทั้งสามชิ้น ไม่มีคำเตือนใดๆ แก้เป็น

auto it = shelf.find(price);
if (it != shelf.end()) {
    shelf.erase(it);
}

แบบที่ 2 อ่านค่าจาก end()

ในโปรแกรมรถเมล์ ลืมเช็กว่า lower_bound ได้ end() หรือเปล่า แล้วผู้โดยสารมาถึงตอนรถคันสุดท้ายออกไปแล้ว

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set<int> departures = {360, 395, 430, 480, 545, 610};
    int now;
    cin >> now;
    cout << "next bus at " << *departures.lower_bound(now) << '\n';
    return 0;
}

คอมไพล์ผ่านโดยไม่มีคำเตือน และโปรแกรมไม่พัง บนเครื่องที่เขียนเอกสารนี้พิมพ์ next bus at 6 ทุกครั้ง ทั้งแบบ Code::Blocks และแบบ -O2 เลข 6 ไม่ใช่เวลารถ end() ไม่ได้ชี้ค่าในเซต สิ่งที่อ่านได้จึงเป็นข้อมูลอื่นที่อยู่ตรงนั้นในหน่วยความจำ ซึ่งบังเอิญเท่ากับจำนวนค่าในเซตพอดี เครื่องอื่นหรือ compiler อื่นอาจได้ค่าอื่นหรือพังเลย อันตรายตรงที่ดูเหมือนคำตอบปกติ ทุกครั้งที่ได้ iterator จาก lower_bound upper_bound หรือ find ต้องเช็กกับ end() ก่อนใส่ *

สรุป

s.lower_bound(x) ค่าแรกที่ ≥ x s.upper_bound(x) ค่าแรกที่ > x ไม่มีคำตอบได้ end()
ค่ามากสุดที่ ≤ x คือ prev(s.upper_bound(x)) เช็กก่อนว่าไม่ใช่ begin()
ค่าที่ใกล้ x ที่สุด ดูแค่ lower_bound(x) กับตัวก่อนหน้า
lower_bound(s.begin(), s.end(), x) กับ set ได้คำตอบถูกแต่เป็น O(N) ต่อครั้ง ใช้แบบมีจุด s.lower_bound(x) เท่านั้น
multiset เก็บค่าซ้ำได้ erase(x) ลบทุกตัว ลบตัวเดียวใช้ erase(find(x)) หลังเช็กว่าไม่ใช่ end()