std::partition dan stable_partition

Sering kali kita tidak butuh data terurut penuh, cukup terbagi dua: invoice yang jatuh tempo di depan, sisanya di belakang; mahasiswa yang remedial terpisah dari yang lulus; angka genap digilir ke kiri. Menyortir penuh O(n log n) terasa boros untuk kebutuhan seperti itu. std::partition menjawabnya dengan O(n): semua elemen yang lolos predikat dipindah ke depan rentang, sisanya ke belakang, dan iterator batas dikembalikan. Chapter ini membahas std::partition beserta versi stabilnya stable_partition, kapan harus memilih yang mana, dan partition_point untuk menemukan kembali batas pada rentang yang sudah terpartisi.

Konsep Partisi dan Predikat #

Partisi memakai predikat — fungsi satu argumen yang mengembalikan bool. Setelah pemanggilan, dijamin: semua elemen yang membuat predikat true berada sebelum semua elemen yang false. Itulah satu-satunya jaminan urutan dari std::partition; bagaimana elemen saling berdesakan di dalam masing-masing kelompok tidak diatur standar. Versi std::stable_partition menambah jaminan: urutan relatif di dalam tiap kelompok dipertahankan sebagaimana rentang aslinya.

#include <algorithm>
#include <iostream>
#include <vector>

void cetak(const std::vector<int>& v) {
    for (std::size_t i = 0; i < v.size(); ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << v[i];
    }
    std::cout << '\n';
}

int main() {
    std::vector<int> data = {5, 2, 9, 4, 7, 6, 1};

    // stable_partition: genap di depan, ganjil di belakang,
    // urutan relatif dalam tiap kelompok dipertahankan
    auto batas = std::stable_partition(data.begin(), data.end(),
                                       [](int x) { return x % 2 == 0; });

    std::cout << "Hasil partisi : ";
    cetak(data);
    std::cout << "Indeks batas  : " << (batas - data.begin()) << "\n";
    std::cout << "Elemen di batas: " << *batas << "\n";

    // partition_point: mencari batas pada rentang yang SUDAH terpartisi
    auto titik = std::partition_point(data.begin(), data.end(),
                                      [](int x) { return x % 2 == 0; });
    std::cout << "partition_point: indeks " << (titik - data.begin()) << "\n";
    return 0;
}

Output yang Dihasilkan:

Hasil partisi : 2 4 6 5 9 7 1
Indeks batas  : 3
Elemen di batas: 5
partition_point: indeks 3

Bedah baris demi baris:

1. Baris 15-17 (std::stable_partition(...)): predikat x % 2 == 0 memilah genap ke depan. Karena memakai versi stabil, urutan asal 2, 4, 6 dan 5, 9, 7, 1 tetap terjaga — hasilnya 2 4 6 5 9 7 1.
2. Baris 19-21: stable_partition mengembalikan iterator ke elemen pertama kelompok kedua (pertama yang false). Indeksnya 3, dan elemen di batas adalah 5.
3. Baris 24-26 (std::partition_point(...)): mencari batas itu lagi pada rentang yang sudah terpartisi. Hasilnya indeks 3, konsisten dengan iterator yang dikembalikan di atas.

Demonstrasi sengaja memakai stable_partition agar output-nya dijamin oleh standar. Dengan std::partition biasa, pembagian kelompoknya tetap pasti — genap selalu di depan — tetapi urutan di dalam kelompok boleh berbeda antar implementasi, sehingga mengklaim urutan spesifiknya tidak aman. Perbedaan biayanya juga perlu diingat: partition bekerja in-place tanpa memori tambahan, sedangkan stable_partition bisa mengalokasikan buffer sementara bila memori cukup tersedia (bila tidak, algoritma cadangan yang lebih mahal dipakai).

partition_point: Mencari Batas Kembali #

Skenario umumnya begini: rentang sudah dipartisi sejak awal (hasil run sebelumnya, atau data yang memang disimpan terpartisi), dan sekarang kita hanya perlu tahu batasnya. std::partition_point(first, last, predikat) menjawabnya dengan pencarian biner O(log n) — syaratnya, rentang memang harus sudah terpartisi menurut predikat yang sama. Iterator yang dikembalikan menunjuk elemen pertama kelompok false, dan bila semua elemen lolos, kembaliannya last.

Kombinasi keduanya membentuk pola kerja yang efisien: partisikan sekali saat data berubah, lalu gunakan partition_point berkali-kali untuk membaca batas tanpa memeriksa seluruh data. Menariknya, partition_point adalah fondasi dari lower_bound dan upper_bound yang kita bahas sebelumnya — binary search pada dasarnya partition point dengan predikat “lebih kecil dari nilai yang dicari”.

Partisi juga jadi alat bantu algoritma lain: std::sort implementasinya memakai partisi pada tahap quicksort-nya, dan std::nth_element — algoritma untuk mendapatkan elemen ke-n terkecil tanpa sortir penuh — bekerja di atas pemartisian berulang.

Sekarang arah kita berbalik dari pengelompokan ke agregasi: menjumlahkan seluruh elemen menjadi satu nilai dengan std::accumulate dan std::reduce.

Rujukan resmi: std::partition , std::stable_partition , dan std::partition_point .