C/C++のデータ構造

C・C++の動的配列とstd::vector

このレッスンでは、要素を追加すると自動で大きくなる動的配列をCで実装し、C++のstd::vectorと比べます。

はじめに

動的配列（dynamic array）は、必要に応じて大きくなる配列です。今入っている要素の数（size）と確保済みの容量（capacity）という2つの考え方を区別します。配列がいっぱいになると、プログラムはより大きな（たいていは2倍の）メモリ領域を確保し、データをそこへ移します。

大切なポイント

操作を書く前に、データ構造で常に成り立つべき条件（不変条件、invariant）を決めましょう。
空のとき、満杯のとき、メモリ確保に失敗したときもきちんと処理しましょう。
各操作の計算量とメモリ管理を、あわせて評価しましょう。

動きで理解する

push_backを何度も押しましょう。配列がいっぱいになると、2倍の大きさの領域を確保してすべてをコピーします。

CとC++のコード例

実行 →

main.c

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t size = 0, capacity = 2;
    int *values = malloc(capacity * sizeof *values);
    if (!values) return 1;
    for (int value = 1; value <= 5; ++value) {
        if (size == capacity) {
            capacity *= 2;
            int *grown = realloc(values, capacity * sizeof *values);
            if (!grown) {
                free(values);
                return 1;
            }
            values = grown;
        }
        values[size++] = value * value;
    }
    printf("size=%zu capacity=%zu last=%d\n",
           size, capacity, values[size - 1]);
    free(values);
}

実行結果

size=5 capacity=8 last=25

C++

実行 →

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values;
    for (int value = 1; value <= 5; ++value) {
        values.push_back(value * value);
    }
    std::cout << "size=" << values.size()
              << " last=" << values.back() << '\n';
}

実行結果

size=5 last=25

CとC++の比較

Cのバージョンでは、sizeがcapacityに達するとcapacityを2倍にし、reallocを呼んでメモリを広げます。reallocの結果は一時的なポインタgrownに入れるので、確保に失敗しても古いメモリを解放できます。C++のstd::vectorはこの成長の仕方をそのまま包み込み、さらにメモリを自動で解放し、イテレーターに対応し、例外が起きても安全です。

データ（struct）と操作は分かれていて、メモリは手作業で確保・解放します。

C++

クラスとコンテナが、データの正しさを守り、リソースを自分で管理します。

発展問題

両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。

空の状態と、容量の上限に達したときのテストを追加しましょう。
メモリを解放する処理を書き、メモリリークがないか確認しましょう。
標準ライブラリの対応するコンテナと計算量を比べましょう。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ