บทที่ 16 vector pair และ sort
จบบทนี้ น้องจะไม่ต้องเดาขนาดอาเรย์อีก เพราะ vector จองขนาดตามข้อมูลเข้าตอนรันและยืดได้เอง จะเก็บข้อมูลเป็นคู่หรือเป็นชุดด้วย pair และ tuple และจะเรียงข้อมูลได้ในบรรทัดเดียวด้วย sort ทั้งเรียงธรรมดา มากไปน้อย และหลายเงื่อนไข ซึ่งในบทที่ 13 ต้องเขียนฟังก์ชันเปรียบเทียบของ qsort ยาวเป็นสิบบรรทัด ท้ายบทมีฟังก์ชันสำเร็จรูปที่ใช้บ่อย เช่น ตัดค่าซ้ำ หาค่ามากสุด ไล่ทุกลำดับ และ lower_bound ที่ตอบคำถามกับข้อมูลที่เรียงแล้วได้ทันที โจทย์ค่าย 1 ช่วงท้ายและค่าย 2 ช่วงต้นจำนวนมากคือ "เรียงก่อน แล้วใช้ข้อมูลที่เรียงแล้วตอบ" เช่น นับคู่ที่ผลรวมไม่เกินงบ นับของในช่วง หรือหาจังหวะที่คนแน่นที่สุด ซึ่งวิธีเทียบทุกคู่ไม่ทันเมื่อข้อมูลเป็นแสน
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 16.1 vector อาเรย์ที่ยืดได้ | push_back size ขนาดและค่าเริ่มต้น [] กับ at() range-for คัดลอกและเทียบทั้งก้อน และกับดักของ size() ที่เป็น unsigned |
| 16.2 vector สองมิติและความเร็ว | ตารางที่ขนาดมาจากข้อมูลเข้า แถวยาวไม่เท่ากัน ส่ง vector ให้ฟังก์ชัน และวัดจริงว่า push_back กับการลืม & ใช้เวลาเท่าไร |
| 16.3 sort และ lambda | เรียง vector อาเรย์ ข้อความ มากไปน้อย เงื่อนไขของเราเองด้วย lambda เทียบเวลากับ qsort และกติกาที่ทำผิดแล้วโปรแกรมพัง |
| 16.4 pair tuple และเรียงหลายเงื่อนไข | pair tuple การเทียบตามลำดับช่อง เคล็ดลับค่าติดลบ เรียง struct ด้วย lambda และ stable_sort |
| 16.5 ฟังก์ชันใน algorithm ที่ใช้บ่อย | reverse max_element accumulate count unique กับ erase next_permutation และ lower_bound upper_bound |