C/C++のデータ構造

動的配列とstd::vector

Dynamic arrayはlogical sizeとcapacityを分け、幾何級数的に成長します。

動的配列とstd::vectorとは？

Dynamic arrayはlogical sizeとcapacityを分け、幾何級数的に成長します。

追加時に連続storageを拡張します。

重要なポイント

操作より先にinvariantを定義します。
空・満杯・allocation失敗を処理します。
計算量とownershipを一緒に評価します。

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はrealloc失敗とcapacityを管理します。std::vectorは成長、破棄、iterator、exception safetyをまとめます。

構造体と操作は分離され、allocationは明示的です。

C++

classとcontainerがinvariantとresourceを管理します。

練習課題

両方を実行して変更し、言語ごとの保証を確認します。

空と容量境界をテストします。
cleanupを実装しleakを確認します。
standard containerと比較します。