16.4 pair tuple และเรียงหลายเงื่อนไข

ข้อมูลในโจทย์มักมาเป็นคู่หรือเป็นชุด เช่น ชื่อกับคะแนน เวลาเริ่มกับเวลาจบ ตำแหน่งกับหมายเลข ในบทที่ 11 เราสร้าง struct ทุกครั้ง C++ มี pair สำหรับเก็บสองค่าคู่กัน และ tuple สำหรับสามค่าขึ้นไป ที่สำคัญคือทั้งสองเทียบกันเองได้ตามลำดับช่อง sort จึงเรียงได้หลายเงื่อนไขโดยไม่ต้องเขียนฟังก์ชันเปรียบเทียบเลย หน้านี้ปิดด้วยการเรียง struct หลายเงื่อนไขด้วย lambda เทียบกับ qsort ในหน้า 13.4 และ stable_sort สำหรับโจทย์ที่ค่าเท่ากันต้องอยู่ตามลำดับเดิม

pair เก็บสองค่าคู่กัน

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

int main()
{
    pair<string, int> best = {"ploy", 92}; // (1)!
    cout << best.first << ' ' << best.second << '\n'; // (2)!
    best.second += 3;
    pair<int, int> start = make_pair(7, 30); // (3)!
    cout << best.second << ' ' << start.first << ':' << start.second << '\n';
    return 0;
}

ชนิดของสองช่องเขียนในวงเล็บแหลม คั่นด้วยจุลภาค สองช่องเป็นคนละชนิดได้ กำหนดค่าด้วยปีกกาเรียงตามช่อง
ช่องแรกชื่อ first ช่องที่สองชื่อ second ใช้เหมือนตัวแปรธรรมดา อ่าน แก้ บวกได้หมด
make_pair(7, 30) สร้าง pair จากสองค่าโดยเดาชนิดให้ ได้ผลเหมือน {7, 30} โค้ดเก่าๆ ใช้แบบนี้บ่อย

ploy 92
95 7:30

pair ก็คือ struct ที่มีสองช่องชื่อ first กับ second ที่ C++ เตรียมไว้ให้ ไม่ต้องประกาศเอง ข้อเสียคือชื่อช่องไม่บอกความหมาย อ่านโค้ดยาวๆ แล้วต้องจำว่า first คืออะไร

pair เทียบกันอย่างไร

pair เทียบด้วย < > == ได้ โดยเทียบ first ก่อน ถ้า first เท่ากันจึงเทียบ second เหมือนเทียบคำในพจนานุกรมที่ดูตัวอักษรแรกก่อน

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

int main()
{
    pair<int, int> a = {3, 9};
    pair<int, int> b = {5, 1};
    pair<int, int> c = {3, 4};
    cout << (a < b) << '\n';
    cout << (c < a) << '\n';
    cout << (a == c) << '\n';
    pair<int, int> smallest = min({a, b, c});
    cout << smallest.first << ' ' << smallest.second << '\n';
    return 0;
}

a < b จริง เพราะ first 3 น้อยกว่า 5 ไม่ต้องดู second เลย แม้ 9 จะมากกว่า 1
c < a จริง เพราะ first เท่ากัน จึงตัดสินด้วย second 4 น้อยกว่า 9
min ที่ใส่หลายค่าในปีกกาหาค่าน้อยสุดของทั้งหมด และใช้กับ pair ได้เพราะ pair เทียบกันได้

เรียง vector ของ pair

กติกาการเทียบนี้คือ "เรียงตาม first ถ้าเท่ากันเรียงตาม second" พอดี sort vector ของ pair จึงได้การเรียงสองเงื่อนไขทันที เคล็ดลับคือเอาค่าที่ใช้เรียงเป็นอันดับแรกไว้ใน first งานวิ่งการกุศลบันทึกชื่อกับเวลาเป็นนาทีของนักวิ่ง ให้พิมพ์จากคนที่ใช้เวลาน้อยที่สุด ถ้าเวลาเท่ากันเรียงตามชื่อ

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, string>> runner(n);
    for (auto &r : runner) {
        cin >> r.second >> r.first;
    }
    sort(runner.begin(), runner.end());
    for (const auto &r : runner) {
        cout << r.first << ' ' << r.second << '\n';
    }
    return 0;
}

5
mint 52
beam 47
ploy 52
earth 61
fah 47

47 beam
47 fah
52 mint
52 ploy
61 earth

ข้อมูลเข้าให้ชื่อก่อนเวลา แต่บรรทัดที่ 10 อ่านชื่อใส่ second และเวลาใส่ first เพราะอยากให้เรียงตามเวลาก่อน auto จากบทที่ 15 ช่วยให้ไม่ต้องเขียน pair<int, string> ซ้ำ

เงื่อนไขหนึ่งมากไปน้อย อีกเงื่อนไขน้อยไปมาก

ถ้าโจทย์ให้เรียงคะแนนจากมากไปน้อย แต่คะแนนเท่ากันให้เรียงชื่อจากน้อยไปมาก จะใช้ greater ไม่ได้ เพราะชื่อจะกลับด้านไปด้วย เคล็ดลับคือเก็บคะแนนติดลบไว้ใน first คะแนนมากกลายเป็นค่าน้อย จึงขึ้นก่อนเมื่อเรียงจากน้อยไปมาก ตอนพิมพ์ค่อยกลับเครื่องหมาย

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, string>> list(n);
    for (auto &p : list) {
        int score;
        cin >> p.second >> score;
        p.first = -score;
    }
    sort(list.begin(), list.end());
    for (const auto &p : list) {
        cout << p.second << ' ' << -p.first << '\n';
    }
    return 0;
}

5
somchai 85
malee 92
anan 85
kanya 92
preeda 70

kanya 92
malee 92
anan 85
somchai 85
preeda 70

เคล็ดลับนี้ใช้ได้กับจำนวนเต็มที่ไม่ใกล้ค่าติดลบที่สุดของ int คะแนน เวลา ระยะทาง ใช้ได้หมด ถ้าค่าอาจเป็น -2147483648 ได้ การกลับเครื่องหมายจะล้นตามหน้า 1.3 ให้ใช้ lambda แทน

tuple เมื่อมีสามค่าขึ้นไป

tuple คือ pair ที่มีกี่ช่องก็ได้ เทียบกันแบบเดียวกัน คือดูช่องแรกก่อน เท่ากันค่อยดูช่องถัดไป ช่องของ tuple ไม่มีชื่อ หยิบด้วย get<0>(t) get<1>(t) ตามเลขช่อง หรือแตกออกเป็นตัวแปรหลายตัวในบรรทัดเดียวด้วย auto [a, b, c] = t; ซึ่งเรียกว่า structured binding ใช้กับ pair ได้ด้วย

ตัวอย่างนี้คือการแข่งตอบคำถามในหน้า 13.4 คะแนนมากก่อน คะแนนเท่ากันเวลาน้อยก่อน เท่ากันอีกเรียงตามชื่อ สามเงื่อนไขพอดีกับสามช่องของ tuple

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

int main()
{
    int n;
    cin >> n;
    vector<tuple<int, int, string>> list;
    for (int i = 0; i < n; i++) {
        string name;
        int score, minutes;
        cin >> name >> score >> minutes;
        list.push_back({-score, minutes, name}); // (1)!
    }
    sort(list.begin(), list.end());
    cout << "top: " << get<2>(list[0]) << '\n'; // (2)!
    int rank = 1;
    for (auto [neg_score, minutes, name] : list) { // (3)!
        cout << rank << ". " << name << ' ' << -neg_score << ' ' << minutes << '\n';
        rank++;
    }
    return 0;
}

ช่องแรกคะแนนติดลบ ให้คะแนนมากขึ้นก่อน ช่องที่สองเวลา ช่องที่สามชื่อ ลำดับช่องคือลำดับความสำคัญของเงื่อนไข
get<2> หยิบช่องที่ 2 นับจาก 0 คือชื่อ เลขในวงเล็บแหลมต้องเป็นค่าคงที่ จะใช้ตัวแปรแทนไม่ได้
แตก tuple แต่ละตัวเป็นตัวแปรสามตัวตามลำดับช่อง ตั้งชื่ออะไรก็ได้ อ่านง่ายกว่า get มาก

6
somchai 85 40
malee 92 55
anan 85 35
kanya 92 55
preeda 70 20
boonmee 85 40

top: kanya
1. kanya 92 55
2. malee 92 55
3. anan 85 35
4. boonmee 85 40
5. somchai 85 40
6. preeda 70 20

ผลตรงกับโปรแกรม ranking ในหน้า 13.4 ทุกบรรทัด แต่ไม่มีฟังก์ชันเปรียบเทียบเลยสักบรรทัด

เรียง struct ด้วย lambda

pair และ tuple สะดวกเมื่อข้อมูลมีสองสามช่อง แต่ถ้ามีหลายช่อง หรือช่องที่ใช้เรียงไม่ได้เรียงตามลำดับในข้อมูล struct ที่มีชื่อช่องชัดเจนอ่านง่ายกว่า ใน C++ ประกาศ struct แล้วใช้ชื่อเป็นชนิดได้เลย ไม่ต้องเขียนคำว่า struct นำหน้าทุกครั้งแบบภาษา C

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

struct Contestant {
    string name;
    int score;
    int minutes;
};

int main()
{
    int n;
    cin >> n;
    vector<Contestant> list(n);
    for (Contestant &c : list) {
        cin >> c.name >> c.score >> c.minutes;
    }
    sort(list.begin(), list.end(), [](const Contestant &a, const Contestant &b) {
        if (a.score != b.score) {
            return a.score > b.score;
        }
        if (a.minutes != b.minutes) {
            return a.minutes < b.minutes;
        }
        return a.name < b.name;
    });
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ". " << list[i].name << ' ' << list[i].score << ' ' << list[i].minutes << '\n';
    }
    return 0;
}

6
somchai 85 40
malee 92 55
anan 85 35
kanya 92 55
preeda 70 20
boonmee 85 40

1. kanya 92 55
2. malee 92 55
3. anan 85 35
4. boonmee 85 40
5. somchai 85 40
6. preeda 70 20

โครงของ lambda เหมือนฟังก์ชัน compare_rank ในหน้า 13.4 ทุกอย่าง ไล่ดูทีละเงื่อนไข เงื่อนไขแรกที่ต่างกันเป็นตัวตัดสิน สิ่งที่หายไปคือ

qsort ในหน้า 13.4	sort ในหน้านี้
รับ `const void ` แล้วแปลงเป็น `const struct contestant ` เอง	รับ `const Contestant &` ใช้ได้ทันที
`a->score`	`a.score`
คืน -1 0 1 เช่น `a->score > b->score ? -1 : 1`	คืนจริงเท็จ `a.score > b.score`
ชื่อเทียบด้วย `strcmp`	ชื่อเป็น `string` เทียบด้วย `<`
บอก `sizeof(list[0])` เอง	ไม่ต้องบอก

พารามิเตอร์ของ lambda เป็น const Contestant & ด้วยเหตุผลเดียวกับหน้า 16.2 ถ้ารับแบบสำเนา ทุกครั้งที่ sort เทียบสองคน จะคัดลอกทั้ง struct รวมชื่อด้วย ซึ่งเกิดขึ้นหลายล้านครั้งเมื่อข้อมูลเป็นแสน

stable_sort รักษาลำดับของค่าที่เท่ากัน

หน้า 13.4 เห็นแล้วว่า qsort ไม่สัญญาว่าค่าที่เท่ากันจะอยู่ตามลำดับเดิม sort ก็ไม่สัญญาเช่นกัน ตัวอย่างนี้ให้นักเรียนเลขที่ 1 ถึง 20 ได้คะแนน 5 กับ 7 สลับกัน เรียงตามคะแนนจากมากไปน้อยอย่างเดียว แล้วพิมพ์เป็น เลขที่:คะแนน

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> list(n);
    for (int i = 0; i < n; i++) {
        cin >> list[i].first;
        list[i].second = i + 1;
    }
    sort(list.begin(), list.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
        return a.first > b.first;
    });
    for (int i = 0; i < n; i++) {
        cout << list[i].second << ':' << list[i].first << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

20
5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7

2:7 20:7 18:7 16:7 14:7 12:7 10:7 8:7 6:7 4:7 9:5 7:5 11:5 13:5 5:5 15:5 17:5 3:5 19:5 1:5

นี่คือผลบนเครื่องที่เขียนเอกสารนี้ ตัวอย่างนี้จึงไม่มีการตรวจผลอัตโนมัติ คะแนนเรียงถูก แต่เลขที่กระจัดกระจาย และที่น่ากลัวกว่านั้นคือ ถ้าลองกับนักเรียนแปดคนแบบในหน้า 13.4 จะได้ 2:7 4:7 6:7 8:7 1:5 3:5 5:5 7:5 ซึ่งดูเหมือนรักษาลำดับ เพราะ sort ของ g++ ใช้วิธีเรียงอีกแบบกับข้อมูลไม่เกิน 16 ตัว ลองกับตัวอย่างเล็กแล้วผ่าน ไม่ได้แปลว่าชุดใหญ่จะผ่าน

เปลี่ยน sort ในบรรทัดที่ 13 เป็น stable_sort ซึ่งรับค่าแบบเดียวกันทุกอย่าง แต่สัญญาว่าค่าที่ฟังก์ชันเปรียบเทียบบอกว่าเท่ากัน จะอยู่ตามลำดับเดิมเสมอ

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> list(n);
    for (int i = 0; i < n; i++) {
        cin >> list[i].first;
        list[i].second = i + 1;
    }
    stable_sort(list.begin(), list.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
        return a.first > b.first;
    });
    for (int i = 0; i < n; i++) {
        cout << list[i].second << ':' << list[i].first << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

20
5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7 5 7

2:7 4:7 6:7 8:7 10:7 12:7 14:7 16:7 18:7 20:7 1:5 3:5 5:5 7:5 9:5 11:5 13:5 15:5 17:5 19:5

ใช้ stable_sort เมื่อโจทย์บอกว่า "ถ้าเท่ากันให้เรียงตามลำดับที่รับเข้ามา" หรือเมื่อเรียงหลายรอบด้วยเงื่อนไขต่างกันแล้วต้องการให้รอบหลังไม่ทำลายผลของรอบก่อน อีกทางที่ได้ผลเท่ากันคือเก็บลำดับที่รับเข้ามาไว้เป็นเงื่อนไขสุดท้ายแบบหน้า 13.4 ซึ่งในตัวอย่างนี้ทำได้ง่ายๆ โดยไม่ใช้ lambda เลย คือเก็บ (-คะแนน, เลขที่) แล้ว sort ธรรมดา

ลองทำให้พัง

แบบที่ 1 พิมพ์ pair ทั้งก้อน

ในโปรแกรม pair-basic ถ้าเพิ่มบรรทัด cout << start << '\n'; ไว้ก่อน return 0; เพื่อพิมพ์ pair ทั้งตัว

pair.cpp:11:10: error: no match for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and 'std::pair<int, int>')
   11 |     cout << start << '\n';
      |     ~~~~ ^~ ~~~~~
      |     |       |
      |     |       std::pair<int, int>
      |     std::ostream {aka std::basic_ostream<char>}

นี่คือหกบรรทัดแรก ข้อความจริงยาวทั้งหมด 581 บรรทัด ส่วนที่เหลือเกือบทั้งหมดเป็นรายการ note: candidate คือ << ทุกแบบที่ compiler ลองจับคู่แล้วใช้ไม่ได้ ไม่ต้องอ่านต่อ บรรทัดแรกบอกครบแล้วว่า cout ไม่รู้วิธีพิมพ์ pair<int, int> ให้พิมพ์ first กับ second ทีละตัวเอง error ของ C++ ที่ยาวเป็นหน้าๆ ให้อ่านบรรทัดที่มีชื่อไฟล์ของเราและคำว่า error ก่อนเสมอ

แบบที่ 2 sort struct โดยไม่บอกวิธีเทียบ

ในโปรแกรม struct-sort ถ้าลบ lambda ออก เหลือแค่ sort(list.begin(), list.end()); คิดว่า sort จะเรียงตามช่องแรกให้เอง ข้อความยาว 129 บรรทัด และ error เดียวกันขึ้นซ้ำสามจุดจากส่วนต่างๆ ข้างใน sort ข้างล่างตัดมาเฉพาะจุดแรก ส่วนที่ต้องหาคือบรรทัดที่มีชื่อไฟล์ของเรา กับ error บรรทัดแรก

ranking.cpp:18:9:   required from here
   18 |     sort(list.begin(), list.end());
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
C:/Program Files/CodeBlocks/MinGW/include/c++/14.2.0/bits/predefined_ops.h:45:23: error: no match for 'operator<' (operand types are 'Contestant' and 'Contestant')
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~

required from here ชี้บรรทัดในโค้ดของเราที่เป็นต้นเหตุ ส่วน error บอกว่าข้างใน sort พยายามเทียบ Contestant สองตัวด้วย < แต่ไม่มีใครบอกว่า struct นี้เทียบกันอย่างไร pair กับ tuple มี < มาให้ แต่ struct ที่เราสร้างเองไม่มี ต้องส่ง lambda ให้ sort ทุกครั้ง

สรุป

pair<A, B> เก็บสองค่า ใช้ .first .second สร้างด้วย {a, b} หรือ make_pair(a, b)
pair และ tuple เทียบช่องแรกก่อน เท่ากันค่อยดูช่องถัดไป sort vector ของ pair จึงเรียงหลายเงื่อนไขได้โดยไม่ต้องเขียน lambda
เงื่อนไขที่ต้องการมากไปน้อย เก็บค่าติดลบไว้ในช่องนั้น
tuple มีกี่ช่องก็ได้ หยิบด้วย get<i>(t) หรือ auto [a, b, c] = t;
struct เรียงด้วย lambda ที่รับ const T & ไล่เงื่อนไขทีละข้อ เงื่อนไขแรกที่ต่างกันเป็นตัวตัดสิน
sort ไม่รักษาลำดับของค่าที่เท่ากัน ใช้ stable_sort หรือใส่ลำดับที่รับเข้ามาเป็นเงื่อนไขสุดท้าย และอย่าเชื่อผลที่ทดลองกับข้อมูลไม่ถึง 17 ตัว