Comparator dan Custom Ordering

Banyak algoritma STL (sort, priority_queue, set, map) butuh aturan ordering — cara membandingkan dua elemen. Default memakai std::less<T> (yaitu operator<). Namun untuk tipe buatan sendiri, atau bila kita ingin urutan berbeda (descending, by-second-field, multi-key), kita harus menyediakan comparator custom. Pada Chapter ini kita akan membedah tiga cara menyatakan ordering — operator<, functor comparator, dan lambda — serta aturan strict weak ordering yang wajib dipenuhi agar STL bekerja dengan benar.

Tiga Cara Menyatakan Ordering #

Comparator wajib mengembalikan true bila a harus dianggap lebih kecil dari b. Untuk priority_queue, true berarti a diletakkan di bawah b (jadi std::greater<T> menghasilkan min-heap).

Mekanisme: Strict Weak Ordering #

Comparator yang valid harus memenuhi empat sifat:

1. Irreflexive: cmp(a, a) == false.
2. Asymmetric: bila cmp(a, b) true, maka cmp(b, a) harus false.
3. Transitive: bila cmp(a, b) dan cmp(b, c), maka cmp(a, c).
4. Transitivity of equivalence: bila !cmp(a,b) && !cmp(b,a) (setara) dan !cmp(b,c) && !cmp(c,b), maka !cmp(a,c) && !cmp(c,a).

Melanggar salah satu menyebabkan undefined behavior — std::sort bisa crash, std::set bisa kehilangan elemen, std::priority_queue bisa menghasilkan urutan aneh.

Kode: Lima Skenario Comparator #

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>

struct Point {
    int x, y;
    // operator< default — bandingkan x dulu lalu y
    bool operator<(const Point& o) const {
        if (x != o.x) return x < o.x;
        return y < o.y;
    }
};

// Comparator lexicographic by (y, x)
struct CmpByYX {
    bool operator()(const Point& a, const Point& b) const {
        if (a.y != b.y) return a.y < b.y;
        return a.x < b.x;
    }
};

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3};

    // 1) Default ascending
    std::sort(v.begin(), v.end());
    std::cout << "asc  : ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    // 2) std::greater<int> — descending
    std::sort(v.begin(), v.end(), std::greater<int>());
    std::cout << "desc : ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    // 3) Lambda comparator — sort by parity lalu nilai
    std::vector<int> w = {1, 2, 3, 4, 5, 6, 7, 8};
    std::sort(w.begin(), w.end(), [](int a, int b) {
        int pa = a % 2, pb = b % 2;
        if (pa != pb) return pa < pb;   // genap dulu (0 < 1)
        return a < b;                    // lalu naik
    });
    std::cout << "parity: ";
    for (int x : w) std::cout << x << ' ';
    std::cout << '\n';

    // 4) Custom operator< pada struct
    std::vector<Point> pts = {{3, 1}, {1, 2}, {3, 0}, {2, 5}};
    std::sort(pts.begin(), pts.end());
    std::cout << "by operator< (x,y):\n";
    for (const auto& p : pts) std::cout << "  (" << p.x << ',' << p.y << ")\n";

    // 5) Custom comparator untuk std::set
    std::set<Point, CmpByYX> ptsByYX = {{3, 1}, {1, 2}, {3, 0}, {2, 5}};
    std::cout << "set by (y, x):\n";
    for (const auto& p : ptsByYX) std::cout << "  (" << p.x << ',' << p.y << ")\n";

    // 6) Strict weak ordering check — operator< valid?
    // Comparator harus: irreflexive (a<a false), asymmetric, transitive
    auto cmp = [](int a, int b) { return a < b; };
    bool ok = !cmp(5, 5) && (cmp(3, 5) != cmp(5, 3)) && !(cmp(3, 5) && cmp(5, 3));
    std::cout << "strict weak ordering? " << std::boolalpha << ok << '\n';

    // 7) Comparator untuk priority_queue — min-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;
    for (int x : {4, 10, 3, 5, 1}) minpq.push(x);
    std::cout << "min-heap: ";
    while (!minpq.empty()) { std::cout << minpq.top() << ' '; minpq.pop(); }
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

asc  : 1 2 3 5 8 9 
desc : 9 8 5 3 2 1 
parity: 2 4 6 8 1 3 5 7 
by operator< (x,y):
  (1,2)
  (2,5)
  (3,0)
  (3,1)
set by (y, x):
  (3,0)
  (3,1)
  (1,2)
  (2,5)
strict weak ordering? true
min-heap: 1 3 4 5 10 

Bedah Kode Baris-per-Baris #

1. struct Point::operator<: default comparator untuk Point. Bandingkan x dulu; bila sama, bandingkan y. Hasilnya urutan lexicographic (x, y). STL akan otomatis memakai ini pada std::sort tanpa comparator eksplisit dan pada std::set<Point>.
2. struct CmpByYX: functor comparator dengan urutan berbeda — (y, x) lexicographic. Memakai pattern yang sama seperti operator< tetapi urutan field dibalik.
3. std::sort(v.begin(), v.end()): tanpa argumen comparator → memakai std::less<int> (yaitu operator<). Ascending.
4. std::sort(v.begin(), v.end(), std::greater<int>()): std::greater adalah functor yang mengembalikan a > b — menghasilkan urutan descending. Setara dengan lambda [](int a, int b) { return a > b; }.
5. std::sort(w.begin(), w.end(), [](int a, int b) {...}): lambda comparator multi-kriteria. Genap dulu (0 < 1), lalu naik per nilai. Output {2,4,6,8,1,3,5,7} — genap naik, lalu ganjil naik.
6. std::sort(pts.begin(), pts.end()): tanpa comparator → pakai Point::operator<. Output (1,2), (2,5), (3,0), (3,1) — urut x naik, lalu y naik untuk x=3.
7. std::set<Point, CmpByYX>: std::set menerima comparator sebagai parameter template kedua (default std::less<Point>). Dengan CmpByYX, urutan iterasi menjadi (y, x) ascending. Output (3,0), (3,1), (1,2), (2,5).
8. Pengecekan strict weak ordering: tiga tes sederhana — irreflexive (!cmp(5,5)), asymmetric (cmp(3,5) != cmp(5,3)), dan tidak keduanya benar (!(cmp(3,5) && cmp(5,3))). Tes ini tidak lengkap (tidak cek transitive), tetapi cukup untuk menangkap bug umum.
9. std::priority_queue<int, std::vector<int>, std::greater<int>>: tiga template parameter. std::greater<int> membuat elemen kecil berada di top → min-heap. Output pop: 1, 3, 4, 5, 10 (ascending).

Pemilihan Cara #

Komparator Multi-Kriteria yang Aman #

Pattern idiomatik untuk multi-kriteria (cepat dan jelas):

struct Cmp {
    bool operator()(const Item& a, const Item& b) const {
        if (a.priority != b.priority) return a.priority < b.priority;
        if (a.deadline != b.deadline)  return a.deadline  < b.deadline;
        return a.name < b.name;
    }
};

Bila urutan field banyak, pertimbangkan std::tie:

bool operator<(const Item& o) const {
    return std::tie(priority, deadline, name)
         < std::tie(o.priority, o.deadline, o.name);
}

std::tie membuat tuple referensi lalu membandingkan secara lexicographic — sintaks ringkas dan minim bug.

Ringkasan #

• Tiga cara comparator: operator< member, functor, lambda.
• Comparator wajib strict weak ordering: irreflexive, asymmetric, transitive, transitivity of equivalence.
• Selalu pakai < (strict less), jangan <= — <= melanggar irreflexive dan menyebabkan UB.
• Default std::less<T> setara dengan operator<; std::greater<T> untuk descending/min-heap.
• Untuk std::set/std::map/std::priority_queue, comparator adalah parameter template — gunakan functor.
• Multi-kriteria: pattern if (a.x != b.x) return a.x < b.x; atau std::tie.