vector/list のメモリ効率

C++

意外なところに食いつきが良くてびびった。
vector は(基本的に) capacity が減らないってのはあるんだろうけど、私が考えていたのはそこではない。Java のコンテナは参照を保持しているだけだけど、C++ は直接値を保持しているというところ。
例えば、SGI の STL 実装では vector は capacity 以上の要素を加えようとすると capacity を倍に拡大するので、129個追加すると、sizeof(T) * 256 の領域が必要となる。
対して、list の場合は各要素ごとに前後のノードへのポインタが必要なので、リストのノードの型を ListNode として、必要な領域は大体 (sizeof(T) + sizeof(ListNode *) * 2) * 129 と。
で、例えば以下のような構造体を要素とすることを考えてみればよい。

struct FilePath {
    char path[256];
    size_t len;
};