配列 （データ構造）

序文

配列に関する些細なことを書き留める. 誰でも知っていると言われそうだが, 社内教育用のノートにするつもり.
以下は主にゲーム開発における見解である, と予防線を張っておく.

静的配列については特に言うこともない. C++11のPOD判定はチェックとして使えそうか,
自動で切り替えるためよりチェックミス用に.
vector, list, arrayなど呼び方は様々. どれも間違ってはいないが,
日本においてはvectorは幾何ベクトルで教わるのでイメージし辛い.

動的配列について

概要

要素数可変, 又は自動で拡縮してくれる配列のこと. 縮小する実装を私は知らない.
範囲外アクセスは, assertか例外に捕まる.
実装する際は, 実際にメモリを確保しているサイズ, 容量と, 使っているサイズを保持する.
C++の場合, 要素の型がPODかどうかでオブジェクトの生成・コピー・破壊の扱いが異なるので注意する.
とりあえず汎用にしたいなら, PODでないとして処理すればよい.

容量を設定できる実装が多く, メモリ再確保の回数を削減するために利用する.
また, リサイズによって縮小した場合, メモリが解放されるとは限らない.
コピー&スワップによって望みのサイズにフィットさせることができる場合がある.

    //STLの場合
    std::vector<int> v0;
    for(int i=0; i<100; ++i) v0.push_back(i);
    std::cout << "size: " << v0.size() << ", capacity: " << v0.capacity() << std::endl;
    std::vector<int>(v0).swap(v0);
    std::cout << "size: " << v0.size() << ", capacity: " << v0.capacity() << std::endl;
    std::vector<int>().swap(v0);
    std::cout << "size: " << v0.size() << ", capacity: " << v0.capacity() << std::endl;

拡張戦略

容量が足りない場合"どのように拡大するか"について, いくつか戦略がある.
要素数が高々1000ぐらいなら元の倍, "倍々戦略"がよく使われるし, 良く動く.
用途が明確な場合, 固定値拡張を検討する. C++のtemplateではオーバーヘッドなくカスタマイザブルにできるだろう.
特殊ケースとして, 近傍の素数に繰り上げする場合がある. 私はHashMap用でしか見かけないが,
剰余演算で, 衝突を少なくハッシュ値をインデックスにマッピングするためである.

速度・メモリについて

2017年の平均的パーソナルコンピュータなら, リンクリストより多くのケースで高速・省メモリになる.
配列で足りない場合に他のデータ構造を検討すべき. 二分木より, 配列のソートと二分探索で十分な場合もある.
CPUのキャッシュ機構の仕組みは簡単にでも知っておくべきだろう.
悲しいことに, 以下のif文elseブロックのようなプログラムは時々見かける.

int main(int argc, char** argv)
{
    if(argc<4){
        return 0;
    }
    timespec start, end;
    int width = atoi(argv[1]);
    int height = atoi(argv[2]);
    int flag = atoi(argv[3]);
    typedef unsigned char u8;
    u8* pixels = new u8[width*height*4];
    if(flag){
        clock_gettime(CLOCK_REALTIME, &start);
        for(int i=0; i<height; ++i){
            for(int j=0; j<width; ++j){
                int index = (i*width+j)*4;
                pixels[index+0] = 0;
                pixels[index+1] = 1;
                pixels[index+2] = 2;
                pixels[index+3] = 3;
            }
        }
        clock_gettime(CLOCK_REALTIME, &end);
    }else{
        clock_gettime(CLOCK_REALTIME, &start);
        for(int i=0; i<width; ++i){
            for(int j=0; j<height; ++j){
                int index = (j*width+i)*4;
                pixels[index+0] = 0;
                pixels[index+1] = 1;
                pixels[index+2] = 2;
                pixels[index+3] = 3;
            }
        }
        clock_gettime(CLOCK_REALTIME, &end);
    }
    long long sec,nsec;
    if(end.tv_nsec<start.tv_nsec){
        nsec = 1000000000LL-start.tv_nsec+end.tv_nsec;
        sec = end.tv_sec-start.tv_sec-1;
    }else{
        nsec = end.tv_nsec-start.tv_nsec;
        sec = end.tv_sec-start.tv_sec;
    }
    std::cout << "sec: " << sec << ", nsec: " << nsec << std::endl;

    std::ofstream file("test.bytes", std::ios::binary);
    file.write(reinterpret_cast<const char*>(pixels), 4*width*height);
    file.close();
    delete[] pixels;
    return 0;
}