92321


下記のコードをDarwin環境で  
`c++ -std=c++17 -g3 -fsanitize=address main.cc && ./a.out` として実行すると、heap-
buffer-overflow となってしまいます。  
色々試してみたところ、おそらく `G[A].push_back(B);` でその現象が起きているっぽいです。  
どなたかバグの原因を教えていただけると助かります。  
また問題とテストコードも下に置いておきます。

<https://atcoder.jp/contests/abc278/tasks/abc278_c>

**入力例:**

[code]

    3 9
    1 1 2
    3 1 2
    1 2 1
    3 1 2
    1 2 3
    1 3 2
    3 1 3
    2 1 2
    3 1 2
    
[/code]

**現状のコード:**

[code]

    #include <bits/stdc++.h>
    
    using namespace std;
    
    void solve() {
        int N, Q;
        cin >> N >> Q;
        vector<vector<int>> G(N);
        for (int i = 0; i < Q; i++) {
            int T, A, B;
            cin >> T >> A >> B;
            if (T == 1) {
                auto itr = find(G[A].begin(), G[A].end(), B);
                if (itr == G[A].end()) {
                    G[A].push_back(B);
                }
            }
            if (T == 2) {
                auto itr = find(G[A].begin(), G[A].end(), B);
                if (itr != G[A].end()) {
                    G[A].erase(itr);
                }
            }
            if (T == 3) {
                bool AhaveB = false;
                for (int A_friend: G[A]) {
                    if (A_friend == B) {
                        AhaveB = true;
                    }
                }
                bool BhaveA = false;
                for (int B_friend: G[B]) {
                    if (B_friend == A) {
                        BhaveA = true;
                    }
                }
                if (AhaveB && BhaveA) {
                    cout << "Yes" << endl;
                } else {
                    cout << "No" << endl;
                }
            }
        }
    }
    
    int main() {
    //  setup();
        solve();
    }
    
[/code]


CC BY-SA 4.0
2022-11-19T22:58:41.420
92319
2022-11-20T05:39:25.730
2022-11-20T05:39:25.730
3060
55503
question
c++
隣接リストを実装しようとした時に heap-buffer-overflow が発生してしまう


原因は、`G[A]`における、添え字の範囲外アクセスです。

[code]

    vector<vector<int>> G(N);
    
[/code]

`G`は上のように定義しているので、添え字の範囲は、0～N-1です。  
それに対し、`A`の範囲は、問題によると1～Nです。  
よって、`G[A]`と書いた場合、`A`がNだと範囲外アクセスになります。

g++なら、コンパイル時のコマンドライン引数に`-D_GLIBCXX_DEBUG`を追加することで、範囲外アクセスを検出してエラーメッセージを出してくれるようになります。ただ、Darwin環境だとやり方が違うかもしれません。


CC BY-SA 4.0
2022-11-19T23:44:11.943
92320
2022-11-20T01:04:34.250
2022-11-20T01:04:34.250
43506
43506
92319
answer


原因は actorbug さんの回答通りだと思います。

`std::vector`ですが、
[`operator[]`](https://cpprefjp.github.io/reference/vector/vector/op_at.html)
で

> この関数は、`at()`メンバ関数とちがって境界チェックを行うことが規定されない。標準ライブラリの実装によっては`assert(n <
> size())`による境界チェックが行われる場合がある

と説明されているように、
[`at()`](https://cpprefjp.github.io/reference/vector/vector/at.html)
を使えば実行時に範囲チェックを行うことができます。


CC BY-SA 4.0
2022-11-20T00:11:06.763
92321
2022-11-20T00:11:06.763
4236
92319
answer