java.util.ArrayListとstd::vectorとかローカル変数の型とか

Java C++

ArrayList vs Vector (vs LinkedList) - odz bufferとかvectorとlistのメモリ効率 - 神様なんて信じない僕らのためにとか色々から。


とりあえず、JDKについてるsrc.zipでのArrayListの実装と、gcc4.1.2のvectorの実装を見てみた。


まずJavaから。
JavaのArrayListは内部にObject型の配列を持っていて、この配列のサイズがキャパシティとなる。addやaddAllといった、要素を追加するメソッドでは、ensureCapacityメソッドが呼ばれて必要ならばキャパシティを増やす。
このメソッドは最低限これだけは必要なキャパシティを引数に取り、addメソッドでは現在のサイズ*1+1を、addAllメソッドでは現在のサイズ+追加しようとしているコレクションのサイズを渡す。
で、ensureCapacityメソッドでは現在のキャパシティが引数で指定されたものより小さい場合、キャパシティを増やす。この際、現在のキャパシティの1.5倍+1を計算し、それが引数で指定されたキャパシティより小さければ引数を、そうでなければ計算値を新しいキャパシティとして設定する。
addでは現在のサイズ+1が引数として渡されるから、必ず1.5倍+1が新たなキャパシティとなるけど、addAllでは追加しようとしているコレクションのサイズが大きければ、指定値、つまり現在のサイズ+追加しようとしているコレクションのサイズが新たなキャパシティとなる。
また、ArrayListでは一度増えたキャパシティは減ることはない。


と、ここまで書いたけどコード載せたほうが早いな。

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

で、C++(というかgcc4.1.2)。
C++のvectorヘッダは

...
#include <bits/stl_vector.h>
#include <bits/stl_bvector.h> 

#ifndef _GLIBCXX_EXPORT_TEMPLATE
# include <bits/vector.tcc>
#endif
...

こんな感じになっていて、とりあえずbits/stl_vector.hのpush_backを見てみると、最後の要素が終端までいっていれば、処理を_M_insert_auxに投げている。
bits/stl_vector.hには宣言しかないので、bits/vector.tccを見てみると、_M_insert_auxを発見。
サイズを決定している部分は、

// When sizeof(value_type) == 1 and __old_size > size_type(-1)/2
// __len overflows: if we don't notice and _M_allocate doesn't
// throw we crash badly later.
size_type __len = __old_size != 0 ? 2 * __old_size : 1;

こうなっており、単純に2倍している。
vectorでキャパシティが減ることがあるかどうかは知らん、というか、今こんなことやってる場合じゃねー(ぇ


だめだ、ついつい現実逃避を・・・
大元となったローカル変数の型については、自分はnewした型をそのまま使うことが多いかも。そもそも、Collection Frameworkでこの手の議論をするのはどうなんだろう。任意のオペレーションだらけで、LSPもなにもあったもんじゃないという。
まぁ、引数は確かにインターフェイスで受け取ることのほうが多いけど、戻り値はそのメソッドの性質によりけりな気がする。
例えば自分でコレクションクラスを書いたとして、cloneメソッドの戻り値にはObjectでもCollectionでもなくて、そのクラス自身にしておく。1.4以前のことは知りませんw

*1:キャパシティではなく、実際に格納されているサイズ