std::vector<std::vector<int>> push_back导致堆缓冲区溢出。

Question

我正在尝试使用以下代码来读取输入（std::cin被替换为自定义字符串数据，以便在此处将输入和程序代码放在一起）来解决hackerrank的even tree任务：

#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

这里我错过了什么？

编辑

好的，我已经找到了其中一种解决方案，可以在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

- Patryk

---

n = 10，当读取第10行8列时，您访问了v[10]（超出范围）。我没有阅读您想要解决的任务，但这听起来像是一个“偏移量为一”的错误。您是否意味着v[ui-1]和v[vi-1]？ - leemes

你可以尝试使用带有-D_GLIBCXX_DEBUG选项的g++编译器，它将使用带有范围检查的安全容器。 - Radek

Answer 1

在这行中

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

您创建了一个有10个元素的向量，这意味着您可以使用索引[0,9]（包括0和9）来访问元素。在最后一个数据中，您有10 8，这将导致超出范围的访问。如果您的数据在[1,10]范围内，则需要调整索引：

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

PS，您的修改消除了错误，因为您创建了一个具有10个元素的std::vector，然后在循环中添加了另外10个元素，这使得索引[0,19]有效。您可以通过以下方式修复代码：

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

如果您想在[1,10]区间内使用索引（尽管0号元素仍将存在于那里），而无需进行额外的循环，则可以考虑使用std :: map>，这样您就不必担心索引问题。

#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以获得更快的访问速度。

- Slava