自分で書いたものの、なぜこれで正常に動くのかわからないので解説をお願いします

Question

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct itn {
    int num;
    int place;
};

int main() {
    
    vector<itn> array;
    srand(unsigned(time(NULL)));
    
    for (int i=0; i<10; i++) {
        array.push_back({rand()%2,i});
    }
    
    for (auto a : array) {
        cout << a.place << "    "<< a.num << endl;
    }
    
    
    for (int j=0; j<10; j++) {
        cout << "-";
    }
    
    cout << "" << endl;
    
    /**ここのforの部分についてです。**/
    for (auto a = array.end(); a != --array.begin(); a--) {
        if (a->num == 1) {
            array.erase(a);
        }
    }
    
    for (auto a : array) {
        cout << a.place << "    "<< a.num << endl;
    }
    
    return 0;
}

##内容

itnのvector配列においてint.numが１の場合削除するというプログラムを組んでいます。元々はfor(range)で作っていたのですがeraseが使えないような内容が書かれていたため完成しませんでした。そこで、通常のforを使用して書き始めたものの色々あってエラー等が起きない形が上記の内容のようなものになりました。

##知りたいこと

・タイトル通りなぜ、このプログラムが正常に動くのか

・forでarray.begin()スタートの場合どのように書けば良いのか

・for(range)で書ける場合はどのように書けば良いのか

Answer 1

・タイトル通りなぜ、このプログラムが正常に動くのか

正しいコードではありません。たまたま動いているに過ぎません。
auto a = array.end(); で a のイテレータが指しているのは最後尾要素の次（ゴミ）です。
これに対して a->num == 1 がたまたま成り立てば
array.erase(a);
という恐ろしい動作を行ってしまいます。

・forでarray.begin()スタートの場合どのように書けば良いのか

    for (auto a = array.begin(); a != array.end();) {
        if (a->num == 1) {
            a = array.erase(a);
        } else {
            ++a;
        }
    }

または

    for (auto a = array.begin(); a != array.end(); ++a) {
        if (a->num == 1) {
            a = array.erase(a);
            --a;
        }
    }

ですね。

・for(range)で書ける場合はどのように書けば良いのか

for(range) 内で要素を削除するのは、たぶん不可能でしょうね。

10/2 追記

    for (auto a = array.end(); a != --array.begin(); a--) {
        if (a->num == 1) {
            array.erase(a);
        }
    }

auto a = array.end(); の a 利用以外に問題がないわけではありません。

array.erase(a); 実行後にイテレータ a を使用してはいけません。
C++11/C++14
23.3.6.5 vector modifiers
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
Effects: Invalidates iterators and references at or after the point of the erase.
規格上は vector の erase を実行したら iterator は無効です。

Answer 2

(最初の内容に誤りがありましたm(__)m)

シンプルに考えるとよいかと思います。

for (auto a = array.end(); a != --array.begin(); a--)は、

auto a = array.end();
a != --array.begin();
a--
の3つの式で構成されます。

まず初めに、auto a = array.end();で、
1番終わり次の要素へのアクセスを得ます。
vectorの要素数が例えば3個(0〜2)であれば、
3が入る事をイメージしてください。
(実際にはIteratorなので配列のように直接添字が入る訳ではないですが)

次に、a != --array.begin();で、
継続が判定されます。
array.begin()は、先頭へのアクセスなので、
0が得られると思ってください(これもイメージです)
それを、--するので、a!=-1みたいなものです。

この後、forの内部が実行されてaの中にアクセスするのですが、
1周目の時点ではaはvectorの範囲外を指しているため、問題になります。
たまたま、ifの条件が成立しなかったため問題になっていなかっただけのようです。
auto a = --array.end();等として、一番最後の要素から始めるようにしないといけません。

そこは飛ばして、現在、本来の最終の要素である、2をイテレータが指しているとします。
これが条件に合致して、2の要素が削除されたとします。
要素数が減るので、--array.end()は1に変化します。

しかし、for文の初期化文は最初の一度しか実行されない為、
ループ内でいくつ要素が削除されてarray.end()がいくつになろうとも、aの値には影響しません。

そして、array.begin()は先頭なので後ろでいくつ要素が削除されようと変化しません。

更にその後、a--で、要素は一つ前に進み1になります。
つまり、今削除した2には、もうアクセスしないので、問題も起きません。

この繰り返しなので問題は起きません。

このパターンに当てはめて考えてみれば、beginスタートはうまく行かないことがわかると思います。
削除してしまうと、その分前に詰まるので、毎回イテレータを進めると、削除した次の要素を飛ばしてしまいます。
その為には、削除したときはイテレータを進めない等の対策が必要になり、ロジックがちょっと複雑になります。

Answer 3

--array.begin() はエラーにはならないけれど、
イテレータは begin() より前を指してはいけないので未定義動作。

a = array.end() のとき a->num もエラーにはならないけれど、
イテレータは最後の要素の次を指しているので未定義動作。

if (a->num == 0) に書き換えて、num が 0 のものを削除しようとすると
Segmentation fault で落ちるかもしれません。

逆順に削除するなら、次のように書けばよいでしょう。

    for (auto a = array.end(); a != array.begin(); ) {
		--a;
        if (a->num == 1) a = array.erase(a);
	}

追記
array.erase(a); についてコメントをいただいたので、a = を追加しました。

Comments

[SHOMI]

>if (a->num == 1) array.erase(a);
if (a->num == 1) a = array.erase(a);
としておかないとerase後のaが不正に…

[kazuma-s]

array が list だったらそうですが、vector なのでその実装を推察すれば、おそらく大丈夫でしょう。しかし、ご指摘の通り、不正というか危ういコードだと思います。ご指摘ありがとうございました。

[SHOMI]

vectorの要素はメモリ上連続しているので動くでしょうけれど、VCのDebugビルドだとチェックされて例外が発生しますね。
あるかわかりませんが、将来的にvector以外に書き換えた場合にも問題になりうるので…

[lehshell]

C++11/C++14
23.3.6.5 vector modifiers
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
Effects: Invalidates iterators and references at or after the point of the erase.
規格上は vector の erase を実行したら iterator は無効です。
正しくないコードでしかありません。実装頼みのダメコードを書くべきではありません。

Answer 4

えーと配列の削除の話ね

for (auto a = array.end(); a != --array.begin(); a--) {
    if (a->num == 1) {
        array.erase(a);
    }
}

ポイントは配列は削除するとサイズが減るという事
つまり

for (int i=0; i < array.end(); i++) {
}

と書く事ができません。
なぜか
例を考えるとまず
array[0] = 0
array[1] = 0
array[2] = 1
array[3] = 2
array[4] = 3
とします
iは0から順番に見ますから

array[0] = 0　(i = 0) 削除なし
array[1] = 0　(i = 1) 削除なし
array[2] = 1　(i = 2) 削除対象なので配列から削除

そうするとこの様に配列が変化します
array[0] = 0
array[1] = 0
array[2] = 2
array[3] = 3
でもiは次に進んでしまいます
array[3] = 3　(i = 3) array[3]はもともとarray[4]
そうすると
array[2] = 2 の判定ができなくなります。
この為思った結果にならないのです。

それでは同じ値で逆に見ていくと
array[4] = 3　(i = 4) 削除なし
array[3] = 2　(i = 3) 削除なし
array[2] = 1　(i = 2) 削除対象なので配列から削除

そうするとこの様に配列が変化します
array[0] = 0
array[1] = 0
array[2] = 2
array[3] = 3

iが減っても
array[1] = 0　(i = 1) 削除なし
array[0] = 0　(i = 0) 削除なし

問題なく動きます

配列を削除する時は後ろから検索というのはどんな言語でもいっしょですので
覚えておいて下さい。

Answer 5

参考：要素の削除　

std::vector<int> v{ 1, 1, 2, 2, 3, 3 };
int value_to_remove = 2;
v.erase(std::remove(v.begin(), v.end(), value_to_remove), v.end()); // v becomes {1, 1, 3, 3}

forループで前方から削除しながらだと途中で削除した場合に削除した部分より後方が１つ前にズレることでうまくいかなかったのではないかと推察します。
後ろから削除する場合はそういったズレが影響しないということかと思います。
気になるようでしたら前方から削除する過程をデバッグで観察すると配列サイズが減るので一目瞭然かと思います。
ループの途中で恐らく範囲外アクセス関連のエラーが出るはずです。（未検証）