Array dua dimensi (matriks) adalah perluasan array satu dimensi untuk merepresentasikan data berbentuk tabel. Di C++, matriks disimpan sebagai blok memori tunggal dengan urutan row-major — baris demi baris. Pada Chapter ini kita akan membedah bagaimana layout memori memengaruhi kinerja traversal, mengapa urutan loop dapat berdampak 5–10× pada kecepatan, dan kapan std::vector<std::vector<T>> cocok dipakai. Pemahaman layout 2D menjadi fondasi untuk topik lanjutan seperti transpose matriks dan prefix sum 2D.

Deklarasi dan Akses #

C++ menyediakan beberapa cara mendeklarasikan matriks:

cpp 
// 1. C-style array 2D
int m1[3][4];

// 2. std::array 2D
std::array<std::array<int, 4>, 3> m2;

// 3. std::vector 2D (dinamis)
std::vector<std::vector<int>> m3(3, std::vector<int>(4, 0));

// 4. std::vector 1D dengan indexing manual (flat)
std::vector<int> m4(3 * 4, 0);     // akses: m4[i * 4 + j]

Pilihan terakhir sering dipakai di kompetitif programming karena lebih hemat memori dan lebih cepat — tidak ada pointer tambahan per baris.

Row-Major Order #

Mekanisme: Baris demi Baris #

C-style array 2D int m[R][C] disimpan sebagai blok kontigu berisi R * C elemen. Urutan: elemen baris 0 (kolom 0, 1, …, C-1), lalu baris 1, lalu baris 2, dan seterusnya. Alamat elemen m[i][j] dihitung dengan:

text 
addr(m[i][j]) = base + (i * C + j) * sizeof(T)

Konsekuensi penting: traversal sepanjang kolom (yaitu m[0][0], m[1][0], m[2][0], …) melompat C * sizeof(T) byte antar akses — tidak cache-friendly.

Kode: Verifikasi Layout dengan Offset #

cpp 
#include <iostream>
#include <cstdint>

int main() {
    int m[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };

    std::uintptr_t base = reinterpret_cast<std::uintptr_t>(&m[0][0]);
    std::cout << "Row-major offset (byte):\n";
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 4; ++j) {
            std::uintptr_t addr = reinterpret_cast<std::uintptr_t>(&m[i][j]);
            std::cout << ' ' << (addr - base);
        }
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Row-major offset (byte):
 0 4 8 12
 16 20 24 28
 32 36 40 44
  1. Baris int m[3][4] = {{1,2,3,4}, ...};: matriks 3 baris × 4 kolom. Total elemen 3 * 4 = 12. Setiap baris dideklarasikan dalam kurung kurawal sendiri.
  2. Baris reinterpret_cast<std::uintptr_t>(&m[i][j]): mengonversi alamat elemen ke integer untuk dihitung offsetnya.
  3. Pola offset: baris ke-0 menempati offset 0..12, baris ke-1 offset 16..28, baris ke-2 offset 32..44. Setiap baris menempati 4 * 4 = 16 byte. Inilah bukti langsung layout row-major.

Traversal: Baris vs Kolom #

Mekanisme: Cache-Friendly vs Cache-Hostile #

Bila kita traverse matriks baris demi baris (m[i][0], m[i][1], ..., m[i][C-1]), akses berturut-turut berada pada alamat yang berdekatan — satu cache line (64 byte = 16 int) dapat melayani 16 akses beruntun. Sebaliknya, traversal kolom demi kolom (m[0][j], m[1][j], ...) melompat C * 4 byte setiap akses — sering memicu cache miss.

Kode: Benchmark Row vs Column Traversal #

cpp 
#include <iostream>
#include <vector>
#include <chrono>

int main() {
    constexpr int N = 2000;
    std::vector<std::vector<int>> m(N, std::vector<int>(N, 1));

    // Row-major traversal
    volatile long long sum1 = 0;
    auto t0 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            sum1 += m[i][j];
    auto t1 = std::chrono::high_resolution_clock::now();

    // Column-major traversal
    volatile long long sum2 = 0;
    auto t2 = std::chrono::high_resolution_clock::now();
    for (int j = 0; j < N; ++j)
        for (int i = 0; i < N; ++i)
            sum2 += m[i][j];
    auto t3 = std::chrono::high_resolution_clock::now();

    auto ms_row = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count();
    auto ms_col = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();

    std::cout << "row-major: sum=" << sum1 << " waktu=" << ms_row << " ms\n";
    std::cout << "col-major: sum=" << sum2 << " waktu=" << ms_col << " ms\n";
    return 0;
}

Output yang Dihasilkan (waktu bervariasi):

text 
row-major: sum=4000000 waktu=4 ms
col-major: sum=4000000 waktu=20 ms
  1. Baris for (int i...) for (int j...) sum1 += m[i][j];: loop luar untuk baris, loop dalam untuk kolom. Akses m[i][j] berurutan dalam memori → cache-friendly.
  2. Baris for (int j...) for (int i...) sum2 += m[i][j];: loop luar untuk kolom, loop dalam untuk baris. Akses m[i][j] melompat N * 4 byte setiap iterasi → cache miss sering.
  3. Perbedaan waktu: row-major ~5× lebih cepat meskipun jumlah iterasi identik. Inilah alasan kuat untuk selalu memilih urutan loop yang sesuai dengan layout memori.

Flat 1D Vector sebagai Matriks #

Mekanisme: Menghindari Indirection #

std::vector<std::vector<int>> membutuhkan satu pointer per baris — overhead 8 byte per baris dan satu tingkat indirection saat akses. Untuk matriks besar (mis. 1000 × 1000), overhead mencapai 8 KB dan potensi cache miss tambahan. Alternatif: simpan sebagai std::vector<int> 1D dengan indexing manual m[i * cols + j].

Kode: Flat Vector dengan Helper #

cpp 
#include <iostream>
#include <vector>

class Matriks {
    int rows_, cols_;
    std::vector<int> data_;
public:
    Matriks(int r, int c, int init = 0)
        : rows_(r), cols_(c), data_(static_cast<std::size_t>(r) * c, init) {}

    int& at(int i, int j) { return data_[static_cast<std::size_t>(i) * cols_ + j]; }
    int  at(int i, int j) const { return data_[static_cast<std::size_t>(i) * cols_ + j]; }

    int rows() const { return rows_; }
    int cols() const { return cols_; }
};

int main() {
    Matriks m(2, 3);
    m.at(0, 0) = 1; m.at(0, 1) = 2; m.at(0, 2) = 3;
    m.at(1, 0) = 4; m.at(1, 1) = 5; m.at(1, 2) = 6;

    for (int i = 0; i < m.rows(); ++i) {
        for (int j = 0; j < m.cols(); ++j) {
            std::cout << m.at(i, j) << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
1 2 3
4 5 6
  1. Baris data_(static_cast<std::size_t>(r) * c, init): alokasi tunggal r * c elemen. Menghindari alokasi per baris.
  2. Baris int& at(int i, int j): akses elemen dengan rumus i * cols_ + j. Versi const untuk konteks read-only.
  3. Class wrapper menyembunyikan detail indexing dari pemanggil — kode pemanggil tetap ekspresif m.at(i, j) = v;.

Inisialisasi dan Konstruksi #

Pola Konstruksi yang Umum #

cpp 
#include <iostream>
#include <vector>

int main() {
    // Pola 1: 3x3 dengan nilai default 0
    std::vector<std::vector<int>> a(3, std::vector<int>(3, 0));

    // Pola 2: langsung dengan initializer list (C++11)
    std::vector<std::vector<int>> b = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // Pola 3: identitas (diagonal 1)
    int n = 3;
    std::vector<std::vector<int>> id(n, std::vector<int>(n, 0));
    for (int i = 0; i < n; ++i) id[i][i] = 1;

    std::cout << "a[1][2] = " << a[1][2] << '\n';
    std::cout << "b[2][0] = " << b[2][0] << '\n';
    std::cout << "id:\n";
    for (const auto& row : id) {
        for (int x : row) std::cout << ' ' << x;
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
a[1][2] = 0
b[2][0] = 7
id:
 1 0 0
 0 1 0
 0 0 1
  1. Baris std::vector<std::vector<int>> a(3, std::vector<int>(3, 0));: konstruktor vector-of-vector menerima jumlah baris (3) dan nilai inisialisasi per baris (vector 3 elemen bernilai 0).
  2. Baris for (const auto& row : id): range-based for dengan const auto& — menghindari copy seluruh baris. Inner loop for (int x : row) aman copy karena int murah.

Ringkasan #

  • Array 2D di C++ disimpan secara row-major: baris demi baris di blok memori kontigu.
  • Traversal row-major (m[i][j] dengan loop j terdalam) jauh lebih cepat daripada column-major karena cache friendly.
  • std::vector<std::vector<int>> fleksibel namun punya overhead pointer per baris.
  • Untuk matriks besar yang ukurannya diketahui, std::vector<int> 1D dengan indexing i * cols + j lebih hemat memori dan lebih cepat.
  • Bungkus indexing manual dalam class atau fungsi helper agar kode pemanggil tetap ekspresif.