std :: vector <std :: vector <int>> push_back gibt Heap-Pufferüberlauf

Question

Ich versuche hackerrank die even tree task mit dem folgenden Code zu lösen, um die Eingabe zu lesen (std::cin mit benutzerdefinierten String-Daten ersetzt Eingang und Programm haben Code an einem Ort hier):

#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); 
    } 
} 

die zweite Zahl wird die Anzahl der Kanten (nachfolgende Zahlenpaar) sein, so kann ich vorhersagen, wie viele Elemente in dem Vektor muß ich.

Dieser Code gibt mir die folgenden Sanitizer Fehler (den gleichen Fehler mit der kommentierten Zeile):

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 

Was ich hier fehle?

EDIT

Ok, so habe ich eine der Lösungen gefunden, die zu emplace_back eine Standard std::vector<int> auf v wäre:

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

Aber warum hat es nicht funktioniert, bevor sie mit size_type seit Konstruktor cppreference

3) Konstruiert die enthalten ähm mit der Anzahl der standardmäßig eingefügten Instanzen von T. Es werden keine Kopien erstellt.

Answer 1

In dieser Zeile

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

Sie erstellen einen Vektor mit 10 Elementen, das heißt, Sie Elemente mit dem Index [0,9] inklusive zugreifen können. In den letzten Daten haben Sie 10 8, was zu einem Zugriff außerhalb des Bereichs führen würde. Wenn Ihre Daten in [1.10] ist im Bereich müssen Sie einstellen Index:

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

PS Ihr Zusatz Fehler beseitigt, weil Sie std::vector mit 10 Elementen erstellen und fügen Sie dann 10 Elemente mehr in der Schleife, die gültig macht Index [0,19]. Sie können Ihren Code beheben, indem Sie:

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

ohne zusätzliche Schleife, wenn Sie in [1,10] Intervall verwenden Indizes wollen (0 Element mit dem Index würde existiert immer noch da, obwohl).

können Sie betrachten std::map<std::vector<int>> verwenden und Sie müssen nicht über Indizes Sorge:

#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); 
    } 
} 

in diesem Fall, dass Sie nur Daten mit Indizes haben Sie verwendet wurden, aber der Zugriff auf das Element durch den Index deutlich langsamer sein . Sie können auch std::unordered_map für einen schnelleren Zugriff in Betracht ziehen, wenn es Ihnen egal ist, ob die Daten im Container sortiert sind.