станд :: вектор & Lt; станд :: вектор & л; INT & GT; & GT; push_back дает переполнение кучи-буфера
Я пытаюсь решить хакерранковский четная задача дерева со следующим фрагментом кода для чтения ввода (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
Что мне здесь не хватает?
РЕДАКТИРОВАТЬ
Итак, я нашел одно из решений, которое будет emplace_back по умолчанию std::vector<int> на v:
std::vector<std::vector<int>> v(n);
for (int i = 0; i < n; ++i) v.emplace_back();
Но почему это не сработало раньше, так как конструктор с size_type cppreference
3) Создает контейнер с количеством вставленных по умолчанию экземпляров T. Копии не создаются.
Решение
В этой строке
std::vector<std::vector<int>> v(n);
Вы создаете вектор с 10 элементами, что означает, что вы можете получить доступ к элементам с индексом [0,9] включительно. В последних данных у вас есть 10 8, что приведет к выходу за пределы допустимого диапазона. Если ваши данные находятся в диапазоне [1,10], вам нужно настроить индекс:
v[ui-1].push_back(vi);
v[vi-1].push_back(ui);
PS ваше дополнение устраняет ошибку, потому что вы создаете std::vector с 10 элементами, а затем вы добавляете еще 10 элементов в цикл, что дает действительный индекс [0,19]. Вы можете исправить свой код:
std::vector<std::vector<int>> v(n+1);
без дополнительного цикла, если вы хотите использовать индексы в интервале [1,10] (хотя элемент с индексом 0 все еще существует там).
Вы можете рассмотреть возможность использования 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 для более быстрого доступа, если вам все равно, сортируются ли данные внутри контейнера.
Другие решения
Других решений пока нет …