ฟังก์ชัน multimap::upper_bound() ใน C++ STL

Multimap ใน C++ STL คืออะไร?

Multimap เป็น associative container ที่คล้ายกับ map แต่อนุญาตให้มีหลายค่าผูกกับคีย์เดียวกันได้ ข้อมูลจัดเรียงอัตโนมัติตามคีย์

ฟังก์ชัน multimap::upper_bound() คืออะไร?

ฟังก์ชัน multimap::upper_bound() ประกาศอยู่ใน header <map> คืนค่า iterator ชี้ไปยังองค์ประกอบแรกที่มีคีย์ มากกว่า (strictly greater than) คีย์ที่กำหนด (k) กล่าวคือ ตำแหน่งหลังสุดของช่วงข้อมูลที่มีคีย์เท่ากับ k

รูปแบบไวยากรณ์ (Syntax)

map_name.upper_bound(key& k);

พารามิเตอร์

• k - คีย์ที่ต้องการค้นหา

ค่าที่ส่งคืน (Return Value)

คืนค่า iterator ชี้ไปยังองค์ประกอบแรกที่มีคีย์ > k หากไม่พบ จะคืนค่า end()

ตัวอย่างการใช้งาน

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

int main() {
    // สร้าง multimap
    multimap<int, int> mul;
    mul.insert({2, 10});
    mul.insert({1, 20});
    mul.insert({1, 30});
    mul.insert({3, 40});
    mul.insert({3, 50});
    mul.insert({4, 60});
    
    // upper bound ของ 1
    auto i = mul.upper_bound(1);
    cout << "Upper bound of key 1 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    
    // upper bound ของ 2
    i = mul.upper_bound(2);
    cout << "Upper bound of key 2 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    
    // upper bound ของ 3
    i = mul.upper_bound(3);
    cout << "Upper bound of key 3 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    
    return 0;
}

ผลลัพธ์

Upper bound of key 1 is: 2 10
Upper bound of key 2 is: 3 40
Upper bound of key 3 is: 4 60

การใช้งานร่วมกับ lower_bound() - Equal Range

การรวม lower_bound() และ upper_bound() จะได้ช่วงขององค์ประกอบทั้งหมดที่มีคีย์เท่ากับค่าที่กำหนด:

auto range = mul.equal_range(key);
// หรือ
auto lower = mul.lower_bound(key);
auto upper = mul.upper_bound(key);

// วนลูปแสดงข้อมูลทั้งหมดที่มีคีย์ = key
for (auto it = lower; it != upper; ++it) {
    cout << it->first << ": " << it->second << endl;
}

สรุป

upper_bound() เป็นฟังก์ชันสำคัญสำหรับการค้นหาช่วงข้อมูล (range queries) ใน multimap โดยเฉพาะเมื่อต้องการดึงข้อมูลทั้งหมดที่มีคีย์เฉพาะค่า ร่วมกับ lower_bound() จะได้ช่วงข้อมูลครบถ้วน มี time complexity เป็น O(log n)