multimap::find() ใน C++ STL

ภาพรวม multimap

std::multimap เป็น Associative Container ที่เก็บข้อมูลเป็นคู่ Key-Value คล้ายกับ map แต่ อนุญาตให้มี Key ซ้ำกันได้หลายค่า ข้อมูลจะถูกจัดเรียงตาม Key อัตโนมัติ

ฟังก์ชัน multimap::find()

find(key) ค้นหาและคืนค่า Iterator ชี้ไปยัง องค์ประกอบแรก ที่มี Key ตรงกับที่ระบุ

Syntax

iterator find(const Key& key);
const_iterator find(const Key& key) const;

Parameters

• key - ค่า Key ที่ต้องการค้นหา

Return Value

• Iterator ชี้ไปยังองค์ประกอบแรกที่มี Key ตรงกัน
• ถ้าไม่พบ คืนค่า end()

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

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    multimap mp;
    
    // เพิ่มข้อมูล (Key สามารถซ้ำได้)
    mp.insert({'A', 10});
    mp.insert({'B', 20});
    mp.insert({'A', 30});  // Key 'A' ซ้ำ
    mp.insert({'C', 40});
    mp.insert({'A', 50});  // Key 'A' ซ้ำอีก
    
    // ค้นหา Key 'A'
    auto it = mp.find('A');
    if (it != mp.end()) {
        cout << "Found: " << it->first << " -> " << it->second << endl;
        // Output: Found: A -> 10 (องค์ประกอบแรกที่มี Key 'A')
    } else {
        cout << "Not found" << endl;
    }
    
    return 0;
}

การวนลูปดูค่าทั้งหมดของ Key เดียวกัน

เนื่องจาก find() คืนค่าแค่ตัวแรก ต้องใช้ equal_range() หรือวนจาก iterator ที่ได้:

// วิธี 1: ใช้ equal_range() (แนะนำ)
auto range = mp.equal_range('A');
for (auto it = range.first; it != range.second; ++it) {
    cout << it->first << " -> " << it->second << endl;
}

// วิธี 2: วนจาก find() จนกว่า Key จะเปลี่ยน
auto it = mp.find('A');
for (; it != mp.end() && it->first == 'A'; ++it) {
    cout << it->first << " -> " << it->second << endl;
}

ตัวอย่างสมบูรณ์

#include <iostream>
#include <map>
#include <string>
using namespace std;

void printAll(const multimap& mp, char key) {
    cout << "All values for key '" << key << "':\n";
    auto range = mp.equal_range(key);
    for (auto it = range.first; it != range.second; ++it) {
        cout << "  " << it->first << " => " << it->second << endl;
    }
    if (range.first == range.second) {
        cout << "  (none)\n";
    }
}

int main() {
    multimap mp;
    mp.insert({'b', 23});
    mp.insert({'a', 46});
    mp.insert({'c', 78});
    mp.insert({'e', 11});
    mp.insert({'d', 34});
    mp.insert({'a', 99});  // Key 'a' ซ้ำ
    mp.insert({'b', 5});   // Key 'b' ซ้ำ
    
    cout << "Multimap contents (sorted by key):\n";
    for (const auto& p : mp) {
        cout << "  " << p.first << " => " << p.second << endl;
    }
    
    cout << endl;
    printAll(mp, 'a');
    printAll(mp, 'b');
    printAll(mp, 'c');
    printAll(mp, 'z');  // ไม่มี
    
    // ใช้ find() หาตัวแรก
    auto it = mp.find('c');
    if (it != mp.end()) {
        cout << "\nfind('c') -> first match: " << it->first << " => " << it->second << endl;
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Multimap contents (sorted by key):
  a => 46
  a => 99
  b => 23
  b => 5
  c => 78
  d => 34
  e => 11

All values for key 'a':
  a => 46
  a => 99
All values for key 'b':
  b => 23
  b => 5
All values for key 'c':
  c => 78
All values for key 'z':
  (none)

find('c') -> first match: c => 78

ฟังก์ชันเกี่ยวข้องที่ควรรู้

ความซับซ้อนของอัลกอริทึม

• เวลา: O(log n) โดย n = จำนวนองค์ประกอบทั้งหมด
• พื้นที่: O(1)

ข้อสังเกตสำคัญ

• find() คืนค่าแค่ องค์ประกอบแรก ของ Key นั้น ไม่ใช่ทั้งหมด
• ต้องใช้ equal_range() หรือวนลูปเองเพื่อดูค่าทั้งหมดของ Key เดียวกัน
• Key ต้องมีการสั่งลำดับ (Strict Weak Ordering) - โดยค่าเริ่มต้นใช้ std::less
• Iterator จาก find() เป็น Bidirectional Iterator