イテレータ無効化ルール

イテレータは容易に無効化されます。

例えばvectorはコンテナサイズよりも要素が増えた場合、要素が取り除かれた場合にイテレータは無効化されます。
なので、基本的にイテレータが無効化される操作とされない操作を明確に分離して考える事で危険を減らすと良いと思います。

const性とイテレータ無効化ルール

const vectorは一切の変更を認めませんが、イテレータ無効化ルールは要素の増減が無ければ変更を許します。
const vectorは変更をコンパイルエラーにしてくれますが、イテレータ無効化ルールは要素の増減に対してエラーを出してくれません。

そこで、イテレータ無効化を避ける方法としてSTLのalgorithmを使います。
algorithmは明示的に破壊しなければイテレーション中にイテレータは無効化されない為です。

イテレーション

基本的にできる限りイテレータを触れない様にすべきです。
何故ならイテレータへの操作はうっかりした破壊が発生しやすい上に、そのミスが分かりにくいからです。

基本的にrange based forが見た目も優れているので使うべきなのですが、イテレーション中のコンテナに触れてしまう問題があるので、心配な場合はfor_eachでも良いかもしれません

std::vector<int> v;
std::for_each(v.cbegin(), v.cend(), [](int number){
    // ここだと明示的にしなければvに触れない
});

// 明示的にイテレータを破壊する
std::for_each(v.cbegin(), v.cend(), [&v](int number){
    // 正しくイテレートできなくなる
    v.push_back(number);
});

イテレーション中にコンテナを触れない認識が共有されている場合は、値を書き換えする意図があるのかを明示します。

// 値は参照のみと明示
for(const auto &item: v){
    // itemは参照のみ可
}

// 変更を行うと明示
for(auto &&item: v){
    // moveした場合コピーコストが減るので&&で受ける
}

もし、イテレータを見えるようにしつつもread onlyにしたい場合は cbeginやcendを使います。こっちをデフォルトで使っていく気持ちが大事です。

要素の追加

要素の追加はreserveしていなかった場合にイテレータが壊れる可能性があります。
なので、基本的に追加した場合にイテレータが壊れると考えた方が安全です。

// イテレータが壊され正常に表示されない
std::vector<int> v = {1, 2, 3, 4};
for(const auto &item: v){
    std::cout << item << std::endl;
    v.push_back(item);
}

また要素の追加の際のコンストラクトコストを考えるとemplace_backを使うべきです。

std::vector<Foo> foos;
// Foo構築後Fooのコピーコンストラクタによって渡されFooは破棄される
foos.push_back(Foo());
// 直接構築するので無駄なオブジェクト生成が行われない
foos.emplace_back();

また、追加の際にメモリの再確保が行われると大量のコピーが発生します。

クラスをSTLコンテナにいれると恐ろしい事が起こるぞ！ - 神様なんて信じない僕らのために

reserveとemplaceが意識共有されていない間はshared_ptrやunique_ptrを使うと良いと思います。
コピーについて認識が薄い内はunique_ptrがmoveしないとコピーできなくて不思議に思うかもしれませんが、オーナーシップを知る良い機会だと思います。

要素の削除

// 最悪。いくらでもバグが入り込む余地があり、なおかつ分かりにくい
std::vector<int> v(10);
for(int i = 0; i < 10; ++i){
    if(v[i] == 5){
        // 範囲外アクセスしてても気付きにくい
        for(int j = i; j < 10; ++j){
            v[j] = v[j + 1];
        }
    }
}

// イテレータへの深い理解が必要なので積極的に使うべきではない
std::vector<int> v(10);
for(auto it = v.begin(); it != v.end();){
    if(*it == 5){
        // イテレーション中にvにアクセスする事は危険
        it = v.erase(it);
        // eraseの戻り値をインクリメントせずにチェックする必要があるが忘れそう
        continue;
    }
    ++it;
}

以下がオススメの記述です。
イテレータの無効化範囲が明確で間違いが少なくなります。

// 明示的に破壊しなければイテレータは壊れない
auto remove_begin = std::remove_if(v.begin(), v.end(), [](int number){
    return number == 5;
});
// コンテナの要素数を変更するメソッドはイテレータを無効化する
v.erase(remove_begin, v.end());
// これ以降はイテレータは無効化されている

サイズ管理

何度も説明に出て来た様に想定限界数を設定し、reserveする事が大事です。

しかし、データを全部読み込んでそれ以降サイズを変更しないという場合にはメモリがもったいないです。そんな時はshrink_to_fitを使いましょう。

std::vector<int> v;
// reserveは必要
v.reserve(100);
v.emplace_back();
v.emplace_back();
v.emplace_back();
// vの確保メモリがint３つ分になる
v.shrink_to_fit();

戻り値としてのstd::vector

NRVOとかmove semanticsがあるので、現代のまともなコンパイラでは参照やポインタを経由せずに返してもコストがありません。

// 戻り値を参照やポインタにしなくても良い
std::vector<int> DefaultList(){
    std::vector<int> v;
    v.reserve(2);
    v.emplace_back(1);
    v.emplace_back(2);
    return v;
}

ぷろみん

プログラミング的な内容を扱ってます

std::vectorの正しい使い方