KAL
Menu

Algoritma esensial

sort, find, transform, accumulate, copy, dan idiom erase-remove.

Daftar isi

Topik ini membahas algoritma pustaka standar yang paling sering dipakai sehari-hari, yaitu std::sort, std::find, std::transform, std::accumulate, dan std::copy, ditambah idiom erase-remove untuk penghapusan berdasarkan nilai. Seluruh contohnya berjalan pada C++17 tanpa opsi kompilasi tambahan. Setelah membacanya, pekerjaan umum atas container dapat ditulis dengan algoritma siap pakai, bukan dengan perulangan buatan sendiri.

Pengurutan dengan std::sort#

std::sort mengurutkan elemen pada rentang yang diberikan secara menaik, di tempat aslinya, tanpa membuat container baru. Rentangnya ditulis sebagai pasangan iterator setengah terbuka, sehingga panggilan std::sort(nilai.begin(), nilai.end()) mencakup seluruh isi vector. Kompleksitas yang dijamin standar adalah O(nlog⁡n)O(n \log n) perbandingan, dan implementasi g++ memakai introsort, yaitu gabungan beberapa algoritma pengurutan untuk menjaga kasus terburuknya tetap cepat. Perhatikan pula bahwa std::sort tidak menjamin urutan dua elemen yang nilainya sama, sedangkan std::stable_sort menjaminnya dengan biaya memori tambahan. Kebutuhan itu muncul ketika data diurutkan berdasarkan satu kolom, tetapi urutan kolom lain masih perlu dipertahankan.

Urutan lain diperoleh lewat argumen ketiga, yaitu predikat (predicate), sebuah fungsi yang mengembalikan true bila elemen pertama harus ditempatkan sebelum elemen kedua. Untuk urutan menurun, pustaka standar menyediakan objek fungsi std::greater<int> yang dapat diteruskan apa adanya.

cpp sort-nilai.cpp 
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nilai = {85, 60, 90, 70, 75};

    std::sort(nilai.begin(), nilai.end());
    std::cout << "Menaik : ";
    for (int n : nilai) {
        std::cout << n << ' ';
    }
    std::cout << '\n';

    std::sort(nilai.begin(), nilai.end(), std::greater<int>());
    std::cout << "Menurun: ";
    for (int n : nilai) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}
text Keluaran 
Menaik : 60 70 75 85 90 
Menurun: 90 85 75 70 60

Keluaran diakhiri satu spasi karena setiap angka dicetak dengan pemisah spasi. Pengurutan berlangsung di tempat, sehingga isi vector berubah dan urutan semula tidak dapat dikembalikan kecuali salinannya disimpan. Kriteria yang lebih khusus, misalnya mengurutkan berdasarkan salah satu anggota struct, ditulis dengan lambda, yaitu fungsi tanpa nama yang mendefinisikan kriterianya langsung pada tempat pemanggilan.

Pencarian dengan std::find#

std::find menyusuri rentang dari awal dan mengembalikan iterator yang menunjuk kemunculan pertama dari nilai yang dicari. Apabila tidak ada yang cocok, hasilnya adalah iterator end(), sehingga keberadaan hasil selalu diuji terhadap end() sebelum dipakai. Posisi indeksnya dapat dihitung dengan std::distance antara begin() dan iterator hasil tersebut.

cpp find-nilai.cpp 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> antrean = {12, 7, 20, 5, 9};
    int cari = 20;

    auto posisi = std::find(antrean.begin(), antrean.end(), cari);
    if (posisi != antrean.end()) {
        std::cout << "Nilai " << cari << " ditemukan pada indeks "
                  << std::distance(antrean.begin(), posisi) << '\n';
    } else {
        std::cout << "Nilai " << cari << " tidak ada\n";
    }

    cari = 99;
    posisi = std::find(antrean.begin(), antrean.end(), cari);
    if (posisi == antrean.end()) {
        std::cout << "Nilai " << cari << " tidak ada\n";
    }
    return 0;
}
text Keluaran 
Nilai 20 ditemukan pada indeks 2
Nilai 99 tidak ada

Pola pengujian terhadap end() pada contoh terjadi dua kali, sekali untuk menyatakan hasil ditemukan dan sekali untuk menyatakan tidak ada. Bentuk pencarian lain memakai std::find_if, yang menerima predikat untuk kriteria yang tidak dapat dinyatakan sebagai satu nilai, misalnya mencari nilai di bawah ambang tertentu. Hasil kembalian std::find berupa iterator, bukan indeks, sehingga pola yang sama berlaku untuk semua container tanpa memandang cara elemennya disimpan.

Pengubahan dan agregasi dengan transform dan accumulate#

std::transform menerapkan satu fungsi pada setiap elemen rentang lalu menyimpan hasilnya, baik pada tempat yang sama maupun pada rentang tujuan yang lain. Fungsi agregasi std::accumulate dari header <numeric> menjumlahkan seluruh elemen mulai dari nilai awal yang diberikan. Keduanya sering berpasangan, karena pengubahan per elemen biasanya diikuti perhitungan ringkas atas hasilnya. Fungsi yang diteruskan ke std::transform dipanggil sekali untuk setiap elemen dan tidak boleh mengubah struktur container yang sedang dioperasikan, karena algoritma hanya menuntut rentang yang sah selama pemrosesannya berlangsung.

cpp transform-accumulate.cpp 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int kurvaLima(int n) {
    return n + 5;
}

int main() {
    std::vector<int> nilai = {70, 85, 90, 60};

    // mengubah setiap elemen di tempatnya: kurva 5 poin
    std::transform(nilai.begin(), nilai.end(), nilai.begin(), kurvaLima);

    int total = std::accumulate(nilai.begin(), nilai.end(), 0);

    std::cout << "Nilai terkurva: ";
    for (int n : nilai) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    std::cout << "Total : " << total << '\n';
    std::cout << "Rerata: " << total / static_cast<double>(nilai.size()) << '\n';
    return 0;
}
text Keluaran 
Nilai terkurva: 75 90 95 65 
Total : 325
Rerata: 81.25

Contoh di atas menaikkan setiap nilai ujian dengan kurva lima poin melalui fungsi kurvaLima, lalu menjumlahkan hasilnya dengan nilai awal 0. Parameter nilai awal pada std::accumulate menentukan tipe akumulatornya. Pemanggilan dengan 0 menghitung pada tipe int, sedangkan 0.0 menghitung pada tipe double, sehingga pembagian rerata yang mengikuti tidak memotong bagian desimalnya secara tidak sengaja. Bentuk lain dari std::transform menerima dua rentang sekaligus dan menjalankan operasi biner atas pasangan elemennya, misalnya menjumlahkan dua vector elemen demi elemen.

Penyalinan dengan copy dan idiom erase-remove#

std::copy menyalin seluruh elemen rentang sumber ke iterator tujuan, dan dipakai ketika isi container perlu diduplikasi atau dipindahkan antarstruktur. Tujuannya harus cukup besar bila berupa iterator elemen yang sudah ada, sehingga untuk vector yang masih kosong tujuannya dibungkus std::back_inserter agar elemen baru otomatis ditambahkan.

cpp copy-back-inserter.cpp 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> sumber = {10, 20, 30};
    std::vector<int> tujuan;

    // back_inserter menambahkan elemen baru pada vector yang masih kosong
    std::copy(sumber.begin(), sumber.end(), std::back_inserter(tujuan));

    std::cout << "Tujuan: " << tujuan.size() << " elemen\n";
    for (int n : tujuan) {
        std::cout << n << '\n';
    }
    return 0;
}
text Keluaran 
Tujuan: 3 elemen
10
20
30

Penghapusan berdasarkan nilai memiliki perilaku yang sering tidak diperkirakan. Fungsi std::remove tidak menyusutkan container, melainkan hanya menggeser elemen yang dipertahankan ke depan lalu mengembalikan iterator ke batas logisnya. Elemen di belakang batas itu masih tertinggal dan size() tidak berubah, sehingga std::remove wajib diikuti erase() dengan rentang dari batas logis sampai end().

cpp erase-remove.cpp 
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> stok = {12, 7, 20, 7, 5, 7};

    // remove menggeser elemen yang dipertahankan ke depan
    auto akhirLogis = std::remove(stok.begin(), stok.end(), 7);

    std::cout << "Bagian logis : ";
    for (auto it = stok.begin(); it != akhirLogis; ++it) {
        std::cout << *it << ' ';
    }
    std::cout << "| size masih " << stok.size() << '\n';

    // erase menyusutkan container sampai batas logis
    stok.erase(akhirLogis, stok.end());
    std::cout << "Setelah erase: ";
    for (int n : stok) {
        std::cout << n << ' ';
    }
    std::cout << "| size " << stok.size() << '\n';
    return 0;
}
text Keluaran 
Bagian logis : 12 20 5 | size masih 6
Setelah erase: 12 20 5 | size 3

Pemanggilan std::remove pada contoh memindahkan nilai 7 keluar dari bagian logis, tetapi size masih enam karena belum ada elemen yang dihapus sungguhan. Pemanggilan erase() menyusutkan vector sampai batas logisnya, dan pola gabungan inilah yang dikenal sebagai idiom erase-remove. Sejak C++20, kedua langkah tersebut dipersingkat menjadi std::erase(stok, 7) dan bentuk berkriteria std::erase_if, yang tersedia untuk vector, string, dan beberapa container standar lainnya.

Kesalahan umum#

Empat kesalahan berikut paling sering muncul ketika algoritma-algoritma ini dipraktikkan.

  1. Lupa menyertakan header yang tepat. std::accumulate berada di <numeric>, sedangkan std::sort dan algoritma lainnya berada di <algorithm>, sehingga kompilasi dapat gagal walaupun pemanggilannya tampak benar. Periksa header setiap algoritma yang baru dipakai.
  2. Mengabaikan hasil std::find tanpa menguji terhadap end(). Dereference terhadap end() adalah undefined behavior. Selalu uji iteratornya sebelum isinya dibaca.
  3. Memakai std::remove tanpa erase() karena mengira container sudah menyusut. Bagian logisnya memang benar, tetapi size tetap sebesar semula. Gabungkan keduanya atau ganti dengan std::erase.
  4. Mengurutkan ulang seluruh vector hanya untuk mengambil elemen terbesar. std::max_element dan std::min_element menyelesaikannya dalam satu penyusuran tanpa mengubah urutan data.

Ringkasan#

  • std::sort mengurutkan di tempat dengan kompleksitas O(nlog⁡n)O(n \log n) perbandingan, dan arah urutannya diatur lewat predikat seperti std::greater<int>.
  • std::find mengembalikan iterator kemunculan pertama atau end(), sehingga hasilnya selalu diuji terhadap end() sebelum dipakai.
  • std::transform mengubah elemen lewat fungsi, std::accumulate merangkumnya mulai dari nilai awal, dan std::copy menduplikasi rentang dengan bantuan std::back_inserter bila tujuannya masih kosong.
  • Idiom erase-remove memadukan std::remove yang menggeser dan erase() yang menyusutkan, sedangkan C++20 menyingkatnya menjadi std::erase dan std::erase_if.

Referensi#