C++のvectorの再配置によるsegmentation faultの回避

目的

std::vectorは『連続して確保されたメモリ領域』を持っている．
push_backやresize等の操作によって確保済み容量を超過すると，新たに連続したメモリ領域を確保して，すべての要素を新しい領域にコピー，古いメモリ領域を破棄する．
この挙動をうっかり忘れると，プログラムの実行速度が若干遅くなる，segmentation faultを引き起こす等の問題が発生する．
以下では，segmentation faultの回避方法について書く．

確認環境

Wandbox C++ GCC 8.1.0

g++ prog.cc -Wall -Wextra -I/opt/wandbox/boost-1.67.0/gcc-8.1.0/include -std=c++11

segmentation faultが発生する？

範囲外参照を意図的に引き起こしてみる．
あるクラスがvectorの要素に参照を持つようなデータ構造は，普段から書いてしまいがちで，エラーの特定が難しい．

#include <bits/stdc++.h>
using namespace std;

struct Foo{
    int x;
    Foo(int x):x(x){}
};
struct Bar{
    const Foo& ref;
    Bar(const Foo& ref):ref(ref){}
    int get() const{return ref.x;}
};

int main(){

    vector<Foo> foos;
    vector<Bar> bars;

    //foos.reserve(40);
    //bars.reserve(40);

    for (int i = 0; i < 32; ++i){
        foos.emplace_back(i);
        bars.emplace_back(foos.back());
    }

    for (auto& bar : bars){
        cout << bar.get() << endl;
    }

    // foosとbarsは同時に破棄すると仮定

    return 0;
}

reserveのコメントアウトを外すと，reserve以降のメモリの再確保が行われずに済み，正常に動作する．

解決策

いずれの解決策も，参照先のメモリの再確保を防ぐ方法である．

reserveで予め十分大きな領域を確保しておく

『十分大きな領域』のサイズが分かっているなら有用．具体的には，競技プログラミングなど．
確保した領域を超えてpush_backする危険性は残っているため，書き捨てのコード以外では避けるべき．

メモリの再確保を行わないコンテナを使う

listなど．
上の例では，vector<Foo>をlist<Foo>に書き換えるだけで問題は解決する．

別の場所にデータを書き込み，vectorにはポインタを格納する

listはランダムアクセスが出来ないので，どうしてもvectorに格納したい．
new Foo()でvectorとは別の場所に確保しておき，そのポインタをvectorに格納すれば，ランダムアクセス性は維持できる．

#include <bits/stdc++.h>
using namespace std;

struct Foo{
    int x;
    Foo(int x):x(x){}
    ~Foo(){cout << "deleted:" << x << endl;}
};
struct Bar{
    const Foo& ref;
    Bar(const Foo& ref):ref(ref){}
    int get() const{return ref.x;}
};

int main(){

    vector<Foo*> foos;
    vector<Bar> bars;

    for (int i = 0; i < 32; ++i){
        foos.emplace_back(new Foo(i));
        bars.emplace_back(*foos.back());
    }

    for (auto& bar : bars){
        cout << bar.get() << endl;
    }

    // ポインタはこれが面倒！！
    for (auto& foo : foos){ delete foo; }

    return 0;
}

デストラクタを決して書き忘れないスマートなプログラマは存在しない．
生ポインタは極力避け，デストラクタ処理も行うスマートポインタを使うべきである．

#include <bits/stdc++.h>
using namespace std;

struct Foo{
    int x;
    Foo(int x):x(x){}
    ~Foo(){cout << "deleted:" << x << endl;}
};
struct Bar{
    const Foo& ref;
    Bar(const Foo& ref):ref(ref){}
    int get() const{return ref.x;}
};

int main(){

    vector<unique_ptr<Foo>> foos;
    vector<Bar> bars;

    for (int i = 0; i < 32; ++i){
        foos.emplace_back(new Foo(i));
        bars.emplace_back(*foos.back());
    }

    for (auto& bar : bars){
        cout << bar.get() << endl;
    }

    return 0;
}

参考URL