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

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

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

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

ฟังก์ชัน multimap::lower_bound() ประกาศอยู่ใน header <map> คืนค่า iterator 指向第一个不小于给定键的元素 (first element not less than the given key) กล่าวคือ ตำแหน่งแรกที่คีย์ที่กำหนดสามารถแทรกได้โดยไม่ละลายลำดับการจัดเรียง

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

multi.lower_bound(key& k);

พารามิเตอร์

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

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

คืนค่า iterator ชี้ไปยังองค์ประกอบแรกที่มีคีย์ไม่ น้อยกว่า k (greater than or equal to 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});
    
    // lower bound ของ 1
    auto i = mul.lower_bound(1);
    cout << "Lower bound of key 1 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    
    // lower bound ของ 2
    i = mul.lower_bound(2);
    cout << "Lower bound of key 2 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    
    // lower bound ของ 3
    i = mul.lower_bound(3);
    cout << "Lower bound of key 3 is: ";
    cout << (*i).first << " " << (*i).second << endl;
    
    return 0;
}

ผลลัพธ์

Lower bound of key 1 is: 1 20
Lower bound of key 2 is: 2 10
Lower bound of key 3 is: 3 40

ความแตกต่างระหว่าง lower_bound และ upper_bound

สรุป

lower_bound() มีประโยชน์สำหรับการค้นหาช่วงข้อมูล (range queries) การหาตำแหน่งแทรกข้อมูลใหม่ และการ implement binary search บน multimap โดยมี time complexity เป็น O(log n)