บทที่ 20 set map และ priority queue
จบบทนี้ น้องจะใช้โครงสร้างข้อมูลสำเร็จรูปของ C++ ที่เพิ่ม ลบ และค้นหาได้ใน O(log N) ได้คล่อง ทั้ง set ที่เก็บค่าไม่ซ้ำและเรียงให้ตลอดเวลา map ที่นับความถี่ของค่าที่ใหญ่ถึง 109 หรือของคำได้โดยไม่ต้องมีอาเรย์ใหญ่ และ priority_queue ที่หยิบค่ามากสุดหรือน้อยสุดออกมาได้ทันที โจทย์ค่าย 2 และ TOI จำนวนมากที่ข้อมูลเปลี่ยนไปเรื่อยๆ ระหว่างที่ต้องตอบคำถาม เช่น ที่นั่งว่างตัวถัดไป สถานีที่ใกล้ที่สุด ร้านที่ว่างเร็วที่สุด หรือค่ามัธยฐานของข้อมูลที่ไหลเข้า จะเปลี่ยนจาก O(N2) ที่ไม่ทัน เป็น O(N log N) ที่ทันสบาย บทนี้สอนแค่การใช้งาน ส่วนข้างในที่เป็นต้นไม้และ heap จะได้เรียนในบทที่ 26
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 20.1 set เก็บของไม่ซ้ำ | insert erase count find วนตามลำดับ iterator ค่าน้อยสุดมากสุด และลบตัวซ้ำเทียบกับ vector และ sort |
| 20.2 ค้นหาใน set และ multiset | lower_bound upper_bound ของ set หาค่าที่ใกล้ที่สุด เห็นกับตาว่า std::lower_bound กับ set ช้ามาก และ multiset กับการลบทีละตัว |
| 20.3 map จับคู่คีย์กับค่า | นับความถี่ของค่าที่ใหญ่เกินอาเรย์ map<string, int> นับคำที่พบบ่อยที่สุด และกับดักวงเล็บเหลี่ยมสร้างคีย์เอง |
| 20.4 unordered_map และ unordered_set | ตารางแฮช เร็วกว่า map แค่ไหน กรณีแย่ที่สุดที่ช้ากว่าหลายร้อยเท่า และจับคู่ผลรวมเท่ากับ K สี่วิธี |
| 20.5 priority_queue | ดึงค่ามากสุด น้อยสุดด้วย greater เก็บ pair จำลองเหตุการณ์ตามเวลา รวม k รายการ และค่ามัธยฐานด้วยสอง heap |