Debugging C++

Bug pada algoritma DSA sering muncul hanya pada input tertentu — ukuran tertentu, nilai tertentu, atau urutan tertentu. Tanpa strategi isolasi yang sistematis, kita akan terjebak menambah cout di banyak tempat dan kehilangan jejak akar masalah. Pada Chapter ini kita akan mempraktikkan empat teknik debugging inti: print debugging terstruktur (pisahkan stderr dari stdout), assert precondition/postcondition, trace iterasi binary search, dan binary search pada input minimum untuk menemukan ukuran terkecil yang memunculkan bug. Tujuan akhirnya: ketika bug muncul, kita tahu langkah isolasi pertama yang harus dilakukan sebelum membuka GDB.

Aturan: Pisahkan Log Debug dari Output Jawaban #

Pada kompetisi pemrograman, jawaban dicetak ke stdout dan diverifikasi otomatis oleh judge. Bila kita menambah print debug ke stdout, jawaban tercemar → Wrong Answer. Aturan emas: debug ke stderr (std::cerr), jawaban ke stdout (std::cout).

Stream	Tujuan	Diverifikasi oleh Judge?
`std::cout`	Jawaban akhir	Ya — harus persis sesuai format
`std::cerr`	Log debug, trace, profil	Tidak — diabaikan judge
`std::clog`	Log aplikasi (buffered)	Tidak — sama seperti `cerr`

Mekanisme: Empat Teknik Debugging #

Print debugging terstruktur: tambah cerr << "[DBG] ..." pada setiap iterasi. Pisahkan per iterasi (loop) dan per kategori (pre, body, post).
Assert precondition/postcondition: gunakan assert() dari <cassert> untuk memverifikasi asumsi. Misalnya assert(std::is_sorted(...)) sebelum binary search.
Trace iterasi: cetak lo, hi, mid, value di setiap iterasi binary search. Bug off-by-one biasanya langsung terlihat.
Binary search pada input minimum: bila bug muncul pada n = 10^5 tetapi tidak pada n = 10, lakukan binary search pada n untuk menemukan n minimum yang memunculkan bug — biasanya 1–10 trial.

Kode: Empat Teknik Berdampingan #

cpp
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <string>

// ---------- Fungsi target: lower_bound (pertama a[i] >= threshold) ----------
int lower_bound_ok(const std::vector<int>& a, int threshold) {
    if (a.empty()) return -1;
    int lo = 0, hi = (int)a.size() - 1;
    int ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= threshold) { ans = mid; hi = mid - 1; }
        else                     { lo = mid + 1; }
    }
    return ans;
}

int main() {
    // Strategi 1: print manual untuk verifikasi cepat.
    std::vector<int> v = {1, 3, 5, 7, 9, 11};
    std::cout << "Input array: ";
    for (int x : v) std::cout << x << ' ';
    std::cout << "\n\n";

    std::cout << "=== Query lower_bound ===\n";
    for (int T : {1, 4, 7, 11, 12}) {
        std::cout << "T=" << T << "  lower_bound_ok(v, T) = "
                  << lower_bound_ok(v, T) << '\n';
    }

    // Strategi 2: assert untuk precondition & postcondition.
    std::cout << "\n=== Assert precondition dan postcondition ===\n";
    std::vector<int> sorted = {2, 4, 6, 8, 10};
    assert(std::is_sorted(sorted.begin(), sorted.end()) && "PRE: input harus sorted");
    int idx = lower_bound_ok(sorted, 5);
    assert((idx == -1 || (idx >= 0 && idx < (int)sorted.size())) && "POST: idx dalam rentang");
    assert((idx == -1 || sorted[idx] >= 5) && "POST: sorted[idx] >= threshold");
    std::cout << "lower_bound_ok(sorted, 5) = " << idx << " (asserts OK)\n";

    // Strategi 3: trace iterasi binary search ke stderr.
    std::cout << "\n=== Trace iterasi binary search (ke stderr) ===\n";
    {
        std::vector<int> test = {2, 4, 6, 8, 10, 12, 14};
        int lo2 = 0, hi2 = (int)test.size() - 1;
        int T = 9;
        int iter = 0;
        while (lo2 <= hi2) {
            int mid = lo2 + (hi2 - lo2) / 2;
            ++iter;
            std::cerr << "[DBG] iter=" << iter
                      << " lo=" << lo2 << " hi=" << hi2 << " mid=" << mid
                      << " value=" << test[mid] << " target=" << T << '\n';
            if (test[mid] >= T) hi2 = mid - 1;
            else                lo2 = mid + 1;
        }
        std::cout << "Final: lower_bound index = " << lo2 << '\n';
    }

    // Strategi 4: binary search untuk isolasi bug pada input minimum.
    std::cout << "\n=== Simulasi: binary search pada ukuran input minimum ===\n";
    auto has_bug_at_n = [](int n) { return n >= 5; };
    int lo = 1, hi = 100, first_bug = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (has_bug_at_n(mid)) { first_bug = mid; hi = mid - 1; }
        else                  { lo = mid + 1; }
    }
    std::cout << "Smallest n where bug appears: " << first_bug << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Input array: 1 3 5 7 9 11 

=== Query lower_bound ===
T=1  lower_bound_ok(v, T) = 0
T=4  lower_bound_ok(v, T) = 2
T=7  lower_bound_ok(v, T) = 3
T=11  lower_bound_ok(v, T) = 5
T=12  lower_bound_ok(v, T) = -1

=== Assert precondition dan postcondition ===
lower_bound_ok(sorted, 5) = 2 (asserts OK)

=== Trace iterasi binary search (ke stderr) ===
Final: lower_bound index = 4

=== Simulasi: binary search pada ukuran input minimum ===
Smallest n where bug appears: 5

Pesan stderr (tidak diverifikasi judge, hanya untuk debugging):

text
[DBG] iter=1 lo=0 hi=6 mid=3 value=8 target=9
[DBG] iter=2 lo=4 hi=6 mid=5 value=12 target=9
[DBG] iter=3 lo=4 hi=4 mid=4 value=10 target=9

Bedah Kode Baris-per-Baris #

std::cerr << "[DBG] iter=...": log debug ke stderr. Stream ini tidak diverifikasi oleh judge, sehingga trace tidak mencemari jawaban. [DBG] prefix memudahkan filter: ./prog 2>&1 | grep DBG.
assert(std::is_sorted(...)): precondition — input harus sorted sebelum binary search. Bila invariant dilanggar, program abort dengan pesan assertion. Compile dengan -DNDEBUG untuk menonaktifkan assertion di build final.
assert((idx == -1 || ...) && "POST: idx dalam rentang"): postcondition — indeks hasil valid. String setelah && adalah idiom C++ untuk menambahkan pesan deskriptif pada assertion failure.
int mid = lo2 + (hi2 - lo2) / 2;: idiom binary search aman dari overflow. Trace iterasi memverifikasi bahwa mid selalu di rentang [lo, hi].
auto has_bug_at_n = [](int n) { return n >= 5; };: lambda mensimulasikan “apakah bug muncul pada ukuran n”. Dalam praktik nyata, has_bug_at_n menjalankan program pada input ukuran n dan membandingkan dengan oracle. Binary search menemukan n minimum dalam O(log hi) trial.

GDB: Dasar-Dasar untuk DSA #

Untuk bug yang sulit ditangkap print debugging, GDB (GNU Debugger) adalah alat berikutnya. Empat perintah inti:

Perintah GDB	Fungsi
`break main.cpp:42`	Set breakpoint di baris 42
`break lower_bound_ok`	Set breakpoint di awal fungsi
`run` atau `r`	Jalankan program dari awal
`next` atau `n`	Step over (lewati function call)
`step` atau `s`	Step into (masuk ke function call)
`print a` atau `p a`	Cetak nilai variabel `a`
`print a[0]@5`	Cetak 5 elemen pertama array
`backtrace` atau `bt`	Tampilkan call stack
`watch a[i]`	Hentikan saat `a[i]` berubah
`continue` atau `c`	Lanjutkan sampai breakpoint berikutnya

Sesi GDB khas untuk bug binary search:

text
$ g++ -g -std=c++17 -O0 -o solusi solusi.cpp
$ gdb ./solusi
(gdb) break lower_bound_ok
Breakpoint 1 at 0x...
(gdb) run
Breakpoint 1, lower_bound_ok (...) at solusi.cpp:10
10          int lo = 0, hi = (int)a.size() - 1;
(gdb) print a.size()
$1 = 7
(gdb) print threshold
$2 = 9
(gdb) next
11          while (lo <= hi) {
(gdb) next
12              int mid = lo + (hi - lo) / 2;
(gdb) print mid
$3 = 3
(gdb) continue

Compile dengan -g untuk simbol debug dan -O0 (tanpa optimisasi) agar baris-baris tidak dirombak.

Strategi Isolasi Bug Bertingkat #

flowchart TD A[Bug dilaporkan] --> B{Reproduksi lokal?} B -- Tidak --> C[Buat test case minimal yang memunculkan] B -- Ya --> D{Bug konsisten pada input?} D -- Ya --> E[Print debug + trace] D -- Tidak --> F[Binary search pada ukuran input] E --> G[Akar masalah ditemukan?] F --> G G -- Ya --> H[Fix + tambahkan regression test] G -- Tidak --> I[Buka GDB: breakpoint + watch] I --> H

Ringkasan #

Pisahkan log debug (std::cerr) dari jawaban (std::cout) — judge hanya memverifikasi stdout.
assert() dari <cassert> memverifikasi precondition dan postcondition secara otomatis. Bungkus dengan -DNDEBUG untuk build produksi.
Trace iterasi binary search: cetak lo, hi, mid, value di setiap iterasi — bug off-by-one langsung terlihat.
Binary search pada ukuran input minimum menemukan n terkecil yang memunculkan bug dalam O(log hi) trial.
GDB menyediakan breakpoint, step, print, dan backtrace untuk bug yang sulit ditangkap print debugging.
Strategi isolasi bertingkat: reproduksi → minimalisasi → print/trace → binary search → GDB.