[解決済み] cでベクターを複製するには？

質問

c++やvector/listが登場する前の時代、より多くのデータを格納する必要があるとき、どのようにして配列のサイズを拡大していたのでしょうか？

どのように解決するのか？

ベクターとリストは、概念的にC++と結びついているわけではありません。同様の構造はC言語でも実装可能で、構文（とエラー処理）が異なるだけです。例えば LodePNG を実装しています。 動的配列 は、std::vector に非常に似た機能を持っています。使い方のサンプルは以下のようなものです。

uivector v = {};
uivector_push_back(&v, 1);
uivector_push_back(&v, 42);
for(size_t i = 0; i < v.size; ++i)
    printf("%d\n", v.data[i]);
uivector_cleanup(&v);

見てわかるように、使い方はやや冗長で、異なる型をサポートするためにコードを複製する必要があります。

ナッツ/ストーブ は、どのような型でも動作する、よりシンプルな実装を提供します。

double *v = 0;
arrpush(v, 1.0);
arrpush(v, 42.0);
for(int i = 0; i < arrlen(v); ++i)
    printf("%g\n", v[i]);
arrfree(v);

また、ハッシュマップも提供し、C言語のタイプセーフ・コンテナで使用するトリックは、他の汎用コンテナにも適用できる。

これらのメソッドのいずれでも、基礎となるストレージを拡張することができます。 realloc (下記参照)、または、新しいストレージを malloc で古いものを解放し free -- と同じです。 std::vector C++では、メモリが増加します。

しかし、C言語のコードの多くは、reallocで直接メモリを管理することに頼っています。

void* newMem = realloc(oldMem, newSize);
if(!newMem) {
    // handle error
}
oldMem = newMem;

なお realloc は失敗した場合、null を返しますが、古いメモリはまだ有効です。このような場合、この一般的な（そして間違った）使い方は、メモリをリークします。

oldMem = realloc(oldMem, newSize);
if(!oldMem) {
    // handle error
}

と比較すると std::vector と上述したC言語の同等品では、単純な realloc メソッドは、O(1) の償却保証を提供しません。 realloc メモリを移動させないようにすれば、より効率的な場合があります。