std :: vector <std :: vector <int>> push_backによりヒープバッファオーバーフローが発生する

Question

ハッカークランのeven tree taskを次のコードで解決しようとしています（std::cinは入力とプログラムを持つカスタム文字列データに置き換えられました）ここに一つの場所でコード）：

#include <iostream> 
#include <vector> 
#include <sstream> 

int main() 
{ 
    std::istringstream input("10 9\n2 1\n3 1\n4 3\n5 2\n6 1\n7 2\n8 6\n9 8\n10 8\n"); 
    std::cin.rdbuf(input.rdbuf()); 

    int n,m; 
    std::cin >> n >> m; 

    std::vector<std::vector<int>> v(n); 

    //std::vector<std::vector<int>> v(n, std::vector<int>(n, -1)); 

    int ui, vi; 
    while (m--) 
    { 
    std::cin >> ui >> vi; 
    v[ui].push_back(vi); 
    v[vi].push_back(ui); 
    } 
} 

秒数は、エッジ（その後の数ペア）の数になりますので、私は私が必要になりますどのように多くのベクトルの要素を予測することができます。

このコードは私に、次の消毒エラー（コメント行と同じエラー）を与える：

clang++-3.6 -g -Wall -fsanitize=address --std=c++11 main.cpp && ./a.out 
================================================================= 
==11606==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x611000009ff8 at pc 0x0000004e0beb bp 0x7ffd09cb9ab0 sp 0x7ffd09cb9aa8 
READ of size 8 at 0x611000009ff8 thread T0 
    #0 0x4e0bea (PATH/a.out+0x4e0bea) 
    #1 0x4dfa28 (PATH/a.out+0x4dfa28) 
    #2 0x7f407bd75ec4 (/lib/x86_64-linux-gnu/libc.so.6+0x21ec4) 
    #3 0x438227 (PATH/a.out+0x438227) 

0x611000009ff8 is located 8 bytes to the right of 240-byte region [0x611000009f00,0x611000009ff0) 
allocated by thread T0 here: 
    #0 0x4de672 (PATH/a.out+0x4de672) 
    #1 0x4ecf8a (PATH/a.out+0x4ecf8a) 
    #2 0x4eccd5 (PATH/a.out+0x4eccd5) 
    #3 0x4eca90 (PATH/a.out+0x4eca90) 
    #4 0x4ec70f (PATH/a.out+0x4ec70f) 
    #5 0x4ea89a (PATH/a.out+0x4ea89a) 
    #6 0x4e047a (PATH/a.out+0x4e047a) 
    #7 0x4df8f2 (PATH/a.out+0x4df8f2) 
    #8 0x7f407bd75ec4 (/lib/x86_64-linux-gnu/libc.so.6+0x21ec4) 

Shadow bytes around the buggy address: 
    0x0c227fff93a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff93b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff93c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff93d0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff93e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
=>0x0c227fff93f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fa[fa] 
    0x0c227fff9400: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff9410: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff9420: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff9430: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
    0x0c227fff9440: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 
Shadow byte legend (one shadow byte represents 8 application bytes): 
    Addressable:   00 
    Partially addressable: 01 02 03 04 05 06 07 
    Heap left redzone:  fa 
    Heap right redzone:  fb 
    Freed heap region:  fd 
    Stack left redzone:  f1 
    Stack mid redzone:  f2 
    Stack right redzone:  f3 
    Stack partial redzone: f4 
    Stack after return:  f5 
    Stack use after scope: f8 
    Global redzone:   f9 
    Global init order:  f6 
    Poisoned by user:  f7 
    Container overflow:  fc 
    Array cookie:   ac 
    Intra object redzone: bb 
    ASan internal:   fe 
    Left alloca redzone:  ca 
    Right alloca redzone: cb 
==11606==ABORTING 

は、私はここで何をしないのですか？

EDIT

[OK]をので、私はvにemplace_backにデフォルトstd::vector<int>だろう解決策の一つを発見した：

std::vector<std::vector<int>> v(n); 
for (int i = 0; i < n; ++i) v.emplace_back(); 

しかし、なぜそれがsize_typeとコンストラクタので、前に動作しませんでしたcppreference

3） Tは、デフォルトで挿入されたインスタンスをカウントします。コピーは作成されません。

Answer 1

このラインで

std::vector<std::vector<int>> v(n); 

あなたは、インデックスと[0,9]包括的に要素にアクセスすることができることを意味しており、10個の要素を持つベクトルを作成します。最後のデータでは、範囲外のアクセスにつながる10 8があります。あなたは10個の要素とstd::vectorを作成し、あなたがより有効になりループ、10個の要素を追加しますので、あなたのほかには、エラーを解消

v[ui-1].push_back(vi); 
v[vi-1].push_back(ui); 

PS：あなたのデータは[1,10]である場合は、インデックスを調整する必要がある範囲インデックス[0,19]。あなたは[1,10]の間隔（かかわらインデックス0の要素がまだ存在するでしょう）にインデックスを使用したい場合は、追加のループなし

std::vector<std::vector<int>> v(n+1); 

：あなたは、あなたのことで、コードを固定してもよいです。

あなたはstd::map<std::vector<int>>を使用して検討することとあなたがインデックスを心配する必要はありません。この場合は

#include <iostream> 
#include <vector> 
#include <map> 
#include <sstream> 

int main() 
{ 
    std::istringstream input("10 9\n2 1\n3 1\n4 3\n5 2\n6 1\n7 2\n8 6\n9 8\n10 8\n"); 
    std::cin.rdbuf(input.rdbuf()); 

    int n,m; 
    std::cin >> n >> m; 

    std::map<std::vector<int>> v; 

    int ui, vi; 
    while (m--) 
    { 
    std::cin >> ui >> vi; 
    v[ui].push_back(vi); 
    v[vi].push_back(ui); 
    } 
} 

をあなただけを使用したインデックスを使用してデータを持っていますが、インデックスで要素へのアクセスが大幅に遅くなります。データがコンテナ内でソートされているかどうか気にしない場合は、高速アクセス用にstd::unordered_mapと考えることもできます。