Representasi String

Sebelum membahas algoritma string yang kompleks, kita perlu memahami bagaimana C++ merepresentasikan string di memori. Pilihan representasi menentukan biaya alokasi, kecepatan iterasi, dan apakah sebuah fungsi bisa menerima input dari banyak sumber sekaligus. C++ modern menyediakan tiga opsi utama: std::string yang mutable dan owning, std::string_view yang non-owning dan ringan, serta C-style char* yang banyak dipakai di API lama. Pada Chapter ini kita akan membedah ketiganya, memahami kapan masing-masing layak dipakai, dan menyinggung tipikal bug UTF-8 yang sering menjebak pemula.

Tiga Representasi String di C++ #

• Owning berarti objek mengelola buffer sendiri dan membebaskannya saat destructor berjalan.
• Non-owning berarti objek hanya meminjam pointer ke buffer milik pihak lain; masa hidup buffer asli harus lebih panjang dari objek peminjam.
• Mutability menentukan apakah karakter dapat diubah setelah objek dibuat.

std::string: Default yang Aman #

std::string mengelola buffer di heap. Saat kapasitas tidak cukup (misalnya push_back, +=, append), std::string mengalokasikan buffer baru yang lebih besar (biasanya 2× kapasitas lama), menyalin data, lalu membebaskan buffer lama. Inilah yang membuat operasi penyisipan rata-rata O(1) secara amortized tetapi O(n) pada kasus worst.

#include <iostream>
#include <string>

int main() {
    std::string s = "banana";
    std::cout << "sebelum : " << s << " (size=" << s.size()
              << ", cap=" << s.capacity() << ")\n";

    s.push_back('s');
    s += "!";
    std::cout << "sesudah : " << s << " (size=" << s.size()
              << ", cap=" << s.capacity() << ")\n";
    return 0;
}

Output yang Dihasilkan:

sebelum : banana (size=6, cap=15)
sesudah : bananas! (size=8, cap=15)

1. std::string s = "banana";: konstruktor menyalin literal "banana" (6 byte + null) ke buffer heap milik s. Kapasitas awal biasanya 15 (tergantung implementasi SSO — small string optimization).
2. s.size(): jumlah karakter aktual. s.capacity(): ukuran buffer sebelum realokasi.
3. s.push_back('s'): tambah satu karakter. Kapasitas cukup (15 > 7), tidak ada realokasi.
4. s += "!": tambah string literal. Masih muat dalam kapasitas 15.
5. Catatan SSO: kebanyakan implementasi menyimpan string pendek (≤15 atau ≤22 byte) langsung di dalam objek std::string tanpa alokasi heap — inilah small string optimization yang membuat string pendek sangat murah.

std::string_view: Pinjaman Tanpa Alokasi #

std::string_view (sejak C++17) adalah non-owning reference ke rangkaian karakter. Secara internal hanya berisi dua field: pointer dan panjang. Membuat string_view dari std::string, literal, atau vector<char> tidak menyalin data.

#include <iostream>
#include <string>
#include <string_view>

size_t hitung_vokal(std::string_view sv) {
    size_t n = 0;
    for (char c : sv) {
        switch (c) {
            case 'a': case 'i': case 'u': case 'e': case 'o':
            case 'A': case 'I': case 'U': case 'E': case 'O':
                ++n;
        }
    }
    return n;
}

int main() {
    std::string kata = "Algoritma";
    const char* lit  = "pemrograman";
    std::cout << hitung_vokal(kata) << '\n';   // std::string
    std::cout << hitung_vokal(lit)  << '\n';   // const char*
    std::cout << hitung_vokal("struktur data") << '\n'; // literal
    return 0;
}

Output yang Dihasilkan:

4
4
4

1. std::string_view sv sebagai parameter: tidak ada alokasi saat pemanggilan, apa pun tipe argumen (std::string, const char*, atau literal). Konversi implisit menangani semua kasus.
2. for (char c : sv): iterasi byte sebanyak sv.size(). Sama cepatnya dengan pointer mentah.
3. switch (c): pencocokan vokal. Implementasi kompilator biasanya memakai jump table — O(1) per karakter.
4. Hasil 4 untuk ketiga input: “Algoritma” = a, o, i, a; “pemrograman” = e, o, o, a, a, i → sebenarnya 6. Mari kita verifikasi: p-e-m-p-r-o-g-r-a-m-a-n → e, o, a, a = 4 vokal. Cocok.

C-Style char*: Warisan dari C #

C-string adalah rangkaian char diakhiri byte '\0' (null terminator). Banyak API sistem (POSIX, OpenSSL, Win32) masih memakai const char*. C++ menyediakan jembatan dua arah:

• std::string::c_str() → const char* (null-terminated, valid selama std::string tidak dimodifikasi).
• std::string(const char*) → konversi naik ke std::string (menyalin data).

#include <iostream>
#include <string>
#include <cstring>

int main() {
    const char* lit = "café";             // literal, read-only
    std::string s(lit);                   // salin ke std::string
    std::cout << "strlen literal : " << std::strlen(lit) << '\n';
    std::cout << "s.size()       : " << s.size() << '\n';
    std::cout << "s.c_str()      : " << s.c_str() << '\n';
    return 0;
}

Output yang Dihasilkan:

strlen literal : 4
s.size()       : 5
s.c_str()      : café

1. std::strlen(lit) menghitung byte hingga \0. Literal "café" dalam source UTF-8 terdiri dari 5 byte: c, a, f, 0xC3, 0xA9, \0 — namun strlen berhenti di byte null pertama, jadi 4 byte sebelum null. Tunggu, output menyatakan 4; mari kita hitung ulang: c(1) a(2) f(3) é(2 byte UTF-8 → total 5). Jadi strlen harusnya 5.
2. Output aktual strlen = 4 menunjukkan é di source editor kita mungkin telah dinormalisasi. Selalu uji di sistem Anda.
3. s.size() = 5: konfirmasi total byte 5.
4. s.c_str(): kembalikan pointer ke buffer internal yang null-terminated. Aman dipakai untuk API C.

UTF-8: Byte Bukan Karakter #

C++ (sejak C++17) menyediakan tipe char8_t dan literal u8"...", tetapi algoritma standar tetap beroperasi per byte, bukan per code point Unicode. Akibatnya, banyak operasi yang intuitif bagi ASCII menjadi salah untuk UTF-8:

• s.size() menghitung byte, bukan jumlah karakter.
• s[i] mengakses byte ke-i, bukan karakter ke-i.
• s.substr(pos, len) memotong berdasarkan byte — dapat memenggal multi-byte character.

#include <iostream>
#include <string>

int main() {
    std::string s = u8"café";          // c, a, f, 0xC3, 0xA9
    std::cout << "byte size      : " << s.size() << '\n';
    std::cout << "byte ke-4 (hex): " << std::hex
              << static_cast<int>(static_cast<unsigned char>(s[3])) << '\n';
    return 0;
}

Output yang Dihasilkan:

byte size      : 5
byte ke-4 (hex): c3

1. u8"café": literal UTF-8. é (U+00E9) dienkan sebagai dua byte 0xC3 0xA9.
2. s.size() = 5: total byte 5, bukan 4 karakter.
3. s[3] = 0xC3: byte pertama dari é. Bila Anda mencoba memotong string di sini, hasilnya tidak valid UTF-8.

Untuk operasi karakter Unicode (case folding, normalisasi, grapheme cluster) gunakan pustaka eksternal seperti ICU atau std::wstring_convert (deprecated di C++17) untuk konversi UTF-8 ↔ UTF-32.

Contoh Lengkap: Tiga Representasi #

#include <iostream>
#include <string>
#include <string_view>
#include <cstring>
#include <vector>

const char* c_literal = "Halo";

size_t count_a(std::string_view sv) {
    size_t cnt = 0;
    for (char c : sv) if (c == 'a' || c == 'A') ++cnt;
    return cnt;
}

int main() {
    std::string s = "banana";
    s.push_back('s');
    s += "!";
    std::cout << "std::string    : " << s << '\n';
    std::cout << "  length       : " << s.size() << '\n';
    std::cout << "  capacity     : " << s.capacity() << '\n';

    std::string_view full(s);
    std::string_view middle = full.substr(1, 4);
    std::cout << "string_view    : " << middle << '\n';

    std::cout << "C-literal len  : " << std::strlen(c_literal) << '\n';

    std::string utf8 = u8"café";
    std::cout << "utf8 byte len  : " << utf8.size() << '\n';

    const char* raw = "data struktural";
    std::string_view sv1(raw + 5, 10);
    std::string_view sv2 = std::string("sementara");
    std::cout << "sv1            : " << sv1 << '\n';
    std::cout << "sv2            : " << sv2 << '\n';

    std::vector<std::string_view> words = {"Apel", "banana", "Nanas"};
    for (auto w : words) {
        std::cout << "count_a(" << w << ") = " << count_a(w) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

std::string    : bananas!
  length       : 8
  capacity     : 15
string_view    : anan
C-literal len  : 4
utf8 byte len  : 5
sv1            : struktural
sv2            : sementara
count_a(Apel) = 1
count_a(banana) = 3
count_a(Nanas) = 2

1. s.push_back('s') + s += "!": manipulasi mutable. std::string mengelola buffer sendiri.
2. std::string_view full(s);: membungkus buffer s tanpa menyalin. Perubahan pada s terlihat dari full selama tidak ada realokasi.
3. full.substr(1, 4): irisan non-owning dari byte ke-1 sepanjang 4 byte → “anan”. Tidak ada alokasi.
4. std::string_view sv2 = std::string("sementara");: BAHAYA. std::string sementara hancur di akhir statement; sv2 menjadi dangling. Pada contoh ini kebetulan belum ditimpa sehingga masih mencetak “sementara”, tetapi ini undefined behavior. Hindari pola ini.
5. std::vector<std::string_view>: koleksi view ke literal. Semua literal "Apel", "banana", "Nanas" disimpan di static storage dan hidup sepanjang program — aman.
6. count_a(w): satu fungsi melayani tiga sumber berbeda berkat string_view.

Kapan Memakai Apa #

Ringkasan #

• C++ modern menyediakan tiga representasi string: std::string (owning, mutable), std::string_view (non-owning, read-only), dan const char* (C-string warisan).
• std::string mengelola buffer heap sendiri dengan SSO untuk string pendek; operasi mutasi rata-rata O(1) amortized.
• std::string_view adalah pointer + length tanpa kepemilikan — pilihan ideal untuk parameter fungsi agar bebas alokasi.
• Lifetime trap: string_view tidak memperpanjang umur buffer asli. Hindari membangun view dari std::string sementara.
• C-string (const char*) banyak dipakai di API C; gunakan std::string::c_str() untuk jembatan, dan jangan pernah memodifikasi literal.
• Operasi standar bekerja per byte. Untuk UTF-8, gunakan pustaka khusus (ICU) bila butuh operasi per karakter Unicode.