Banyak struktur data STL butuh comparator untuk menentukan urutan elemen: std::sort mengurutkan, std::priority_queue menentukan prioritas, std::set/std::map menjaga key terurut. Untuk tipe primitif, default std::less<T> cukup. Tetapi untuk struct user-defined atau urutan non-default (descending, multi-kriteria, density-based), kita harus menyediakan comparator sendiri. Pada Chapter ini kita akan membandingkan tiga pendekatan — operator< overload, functor comparator, dan lambda — serta mendemonstrasikan comparator stateful dan strategi anti-overflow via perkalian silang.

Tiga Pendekatan Comparator #

PendekatanKapan dipakaiKelebihanKekurangan
operator< member of TUrutan “natural” defaultOtomatis dipakai semua STL; ringkasHanya satu urutan default
Functor struct CmpReusable, dipakai banyak tempatEfisien (inline); parameter templateVerbose
Lambda [](a,b) {...}Sekali pakai, inlineRingkas; capture fleksibelTidak reusable tanpa decltype

Mekanisme: Strict Weak Ordering #

Semua comparator STL wajib strict weak ordering: irreflexive (cmp(a,a) == false), asymmetric, transitive, transitivity of equivalence. Untuk priority_queue, cmp(a, b) == true berarti a harus berada di bawah b — sehingga std::greater<T> menghasilkan min-heap (elemen kecil naik ke top).

Kode: Enam Skenario Comparator #

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

// 1) Comparator untuk std::sort — lambda vs functor
struct Point {
    int x, y;
};

// 2) operator< overload — default ordering untuk struct
struct Task {
    int priority;
    std::string name;

    bool operator<(const Task& o) const {
        // priority rendah = didahulukan (min-priority)
        if (priority != o.priority) return priority < o.priority;
        return name < o.name;
    }
};

// 3) Functor comparator — fleksibel, reusable
struct TaskByPriorityDesc {
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority > b.priority;  // desc
        return a.name < b.name;
    }
};

// 4) Custom comparator untuk std::priority_queue
struct Item {
    int weight;
    int value;
};

struct ItemByValueDensityDesc {
    bool operator()(const Item& a, const Item& b) const {
        // value/weight descending — gunakan perkalian untuk hindari float
        return (long long)a.value * b.weight < (long long)b.value * a.weight;
    }
};

// 5) Comparator stateful
struct ThresholdCmp {
    int threshold;
    explicit ThresholdCmp(int t) : threshold(t) {}
    bool operator()(int a, int b) const {
        // Elemen >= threshold duluan, lalu naik
        bool a_hi = a >= threshold, b_hi = b >= threshold;
        if (a_hi != b_hi) return a_hi > b_hi;  // hi lebih dulu
        return a < b;
    }
};

int main() {
    // 1) std::sort dengan lambda
    std::vector<Point> pts = {{3, 1}, {1, 5}, {3, 0}, {2, 2}};
    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    std::cout << "sort by (x,y) asc:\n";
    for (const auto& p : pts) std::cout << "  (" << p.x << ',' << p.y << ")\n";

    // 2) Default operator< — tidak perlu comparator eksplisit
    std::vector<Task> tasks = {
        {3, "deploy"}, {1, "fix-bug"}, {2, "patch"}, {1, "alert"}
    };
    std::sort(tasks.begin(), tasks.end());
    std::cout << "tasks sorted by operator< (priority asc, name asc):\n";
    for (const auto& t : tasks) std::cout << "  P" << t.priority << ' ' << t.name << '\n';

    // 3) Functor untuk urutan berbeda
    std::sort(tasks.begin(), tasks.end(), TaskByPriorityDesc{});
    std::cout << "tasks sorted desc by priority:\n";
    for (const auto& t : tasks) std::cout << "  P" << t.priority << ' ' << t.name << '\n';

    // 4) priority_queue custom
    std::priority_queue<Item, std::vector<Item>, ItemByValueDensityDesc> pq;
    pq.push({10, 60});
    pq.push({5, 50});
    pq.push({20, 40});
    std::cout << "pq by value density desc (value/weight):\n";
    while (!pq.empty()) {
        const auto& it = pq.top();
        std::cout << "  w=" << it.weight << " v=" << it.value
                  << " ratio=" << (double)it.value / it.weight << '\n';
        pq.pop();
    }

    // 5) std::set dengan comparator custom
    std::set<int, ThresholdCmp> s{ThresholdCmp{5}};
    for (int x : {3, 8, 1, 10, 4, 7, 2}) s.insert(x);
    std::cout << "set (>=5 duluan, lalu naik):\n";
    for (int x : s) std::cout << "  " << x << '\n';

    // 6) Comparator stateful dengan lambda capture
    int thr = 5;
    std::vector<int> v = {3, 8, 1, 10, 4, 7, 2};
    std::sort(v.begin(), v.end(), [thr](int a, int b) {
        bool a_hi = a >= thr, b_hi = b >= thr;
        if (a_hi != b_hi) return a_hi > b_hi;
        return a < b;
    });
    std::cout << "vector (>=5 duluan, lalu naik): ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

text 
sort by (x,y) asc:
  (1,5)
  (2,2)
  (3,0)
  (3,1)
tasks sorted by operator< (priority asc, name asc):
  P1 alert
  P1 fix-bug
  P2 patch
  P3 deploy
tasks sorted desc by priority:
  P3 deploy
  P2 patch
  P1 alert
  P1 fix-bug
pq by value density desc (value/weight):
  w=5 v=50 ratio=10
  w=10 v=60 ratio=6
  w=20 v=40 ratio=2
set (>=5 duluan, lalu naik):
  7
  8
  10
  1
  2
  3
  4
vector (>=5 duluan, lalu naik): 7 8 10 1 2 3 4

Bedah Kode Baris-per-Baris #

  1. Lambda comparator [](const Point& a, const Point& b): comparator inline untuk std::sort. Multi-kriteria: bandingkan x dulu, lalu y. Lambda tanpa capture bisa dikonversi ke function pointer.
  2. Task::operator<: default ordering untuk Task. Priority naik (1, 2, 3) lalu name ascending. Saat std::sort(tasks.begin(), tasks.end()) tanpa comparator eksplisit, STL otomatis memakai operator<.
  3. TaskByPriorityDesc functor: comparator alternatif — priority descending. Dipakai via std::sort(tasks.begin(), tasks.end(), TaskByPriorityDesc{}). Satu struct bisa punya beberapa comparator alternatif — fleksibel.
  4. ItemByValueDensityDesc untuk priority_queue: menghitung density value/weight tanpa pembagian — pakai perkalian silang (a.value * b.weight) < (b.value * a.weight). Mencegah pembulatan float dan overflow int (cast ke long long). Hasil: item dengan density tertinggi (10, 6, 2) di top.
  5. ThresholdCmp comparator stateful: functor dengan member threshold. Dibangun via ThresholdCmp{5}. Mengembalikan true bila a harus dianggap “lebih kecil” — elemen ≥ threshold didahulukan, lalu naik per nilai.
  6. std::set<int, ThresholdCmp> s{ThresholdCmp{5}}: std::set menerima comparator sebagai parameter template kedua. Konstruktor menerima instance comparator (dibutuhkan untuk comparator stateful). Iterasi set: 7, 8, 10, 1, 2, 3, 4 — elemen ≥ 5 duluan, lalu sisanya naik.
  7. Lambda dengan capture [thr]: lambda stateful untuk std::sort. Sama perilakunya dengan ThresholdCmp. Untuk priority_queue, lambda butuh decltype dan konstruktor — lebih verbose daripada functor.

Pemilihan Cara #

SkenarioCara terbaik
Urutan natural jelas (angka, tanggal, nama)operator< member
Satu urutan default + beberapa alternatifoperator< + functor untuk alternatif
Comparator sekali pakai di satu fungsiLambda
Comparator dipakai banyak tempatFunctor
Comparator untuk priority_queue/set/mapFunctor (parameter template)
Comparator statefulFunctor dengan member atau lambda capture

Pola Comparator Multi-Kriteria dengan std::tie #

Idiomatik untuk banyak field:

cpp 
struct Employee { int dept; int salary; std::string name; };

auto cmp = [](const Employee& a, const Employee& b) {
    return std::tie(a.dept, a.salary, a.name)
         < std::tie(b.dept, b.salary, b.name);
};

std::tie membuat tuple referensi lalu membandingkan secara lexicographic. Lebih ringkas dan minim bug dibanding penulisan if (a.x != b.x) return a.x < b.x; berulang.

Comparator untuk priority_queue — greater vs Custom #

Default std::priority_queue<T> memakai std::less<T> → max-heap. Untuk min-heap, pakai std::greater<T>:

cpp 
std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;

Untuk struct dengan comparator custom, gunakan functor sebagai parameter template ketiga:

cpp 
std::priority_queue<Item, std::vector<Item>, ItemByValueDensityDesc> pq;

Ringkasan #

  • Tiga pendekatan: operator< member, functor, lambda.
  • operator< otomatis dipakai semua STL; gunakan bila urutan natural jelas.
  • Functor reusable dan efisien (inline); cocok untuk parameter template set/map/priority_queue.
  • Lambda sekali pakai; bisa capture state untuk comparator stateful.
  • Untuk komparasi rasio, pakai perkalian silang (a*d < c*b) — hindari pembagian float.
  • Multi-kriteria: std::tie(a.x, a.y, a.z) < std::tie(b.x, b.y, b.z).
  • Comparator wajib strict weak ordering (irreflexive, asymmetric, transitive).