使用变量初始化大小的vector出现无效读取问题求助

编写了isPermutation函数，用于判断vector<int>的元素是否是[1..vector.size()]的某个排列。该函数在返回0（false）的assert测试中触发段错误。

代码实现 #

#include <vector>
#include <cassert>
using namespace std;

// checks whether the elements of a vector are some permutation of range [1..vector.size()]
int isPermutation(vector<int> &&A)
{
    int res = 1;
    int vecSize = A.size();

    // vector to store elements already found in vector A
    vector<int> B(vecSize, 0);
    
    for (auto& it : A)
    {
        if (B[it - 1] != 0 || it > vecSize)
        {
            res = 0;
            break;
        } // element already exists in B or is outside the permutation range
        else
        {
            B[it - 1] = 1;
        } // register element
    }
    return res;
}

int main()
{
    assert(isPermutation({4, 1, 3, 2}) == 1);
    assert(isPermutation({4, 1, 3, 2}) != 0);
    assert(isPermutation({1, 3}) == 0);
    assert(isPermutation({2}) == 0);
    assert(isPermutation({1}) == 1);
    assert(isPermutation({1, 2}) == 1);
    assert(isPermutation({4, 1, 3}) == 0);
    assert(isPermutation({4, 1, 2, 3, 6, 5, 8, 7}) == 1);

    return 0;
}

Valgrind错误日志 #

==212== Invalid read of size 4
==212==    at 0x109306: isPermutation(std::vector<int, std::allocator<int> >&&) (main.cpp:16)
==212==    by 0x109598: main (main.cpp:33)
==212==  Address 0x4dade18 is 0 bytes after a block of size 8 alloc'd
==212==    at 0x483BE63: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==212==    by 0x10A6B7: __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) (new_allocator.h:114)
==212==    by 0x10A5CB: std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) (alloc_traits.h:443)
==212==    by 0x10A427: std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) (stl_vector.h:343)
==212==    by 0x10A2C0: std::_Vector_base<int, std::allocator<int> >::_M_create_storage(unsigned long) (stl_vector.h:358)
==212==    by 0x109F6A: std::_Vector_base<int, std::allocator<int> >::_Vector_base(unsigned long, std::allocator<int> const&) (stl_vector.h:302)
==212==    by 0x109BF2: std::vector<int, std::allocator<int> >::vector(unsigned long, int const&, std::allocator<int> const&) (stl_vector.h:521)
==212==    by 0x10928B: isPermutation(std::vector<int, std::allocator<int> >&&) (main.cpp:12)
==212==    by 0x109598: main (main.cpp:33)

返回1的assert测试无此问题，用常量而非vecSize初始化vector B可消除错误，请问原因是什么？

解答 #

问题出在条件判断的顺序错误，导致了数组越界访问：

当前代码的if条件是：

if (B[it - 1] != 0 || it > vecSize)

逻辑或||是短路求值，但这里的顺序搞反了——先尝试访问B[it-1]，再判断it是否超出范围。

举个测试用例的例子：isPermutation({2})，此时vecSize=1，it=2，it-1=1，而vector B的大小是1，合法索引只有0。这时候访问B[1]就是越界访问，直接触发内存错误，也就是Valgrind检测到的"Invalid read"。

而返回1的测试用例中，所有元素都在[1..vecSize]范围内，不会触发越界，因此没有问题。如果用常量初始化B（比如常量大于所有测试用例的vecSize），it-1可能落在B的合法索引范围内，自然不会触发越界错误，但这只是临时规避，没有解决根本问题。

另外还要注意，代码还遗漏了对it<=0的判断——如果向量中存在0或负数，同样会导致it-1为负数，引发越界访问。

修复方案：调整条件顺序，先判断it的合法性，再访问B的元素，同时补上it<=0的检查：

if (it > vecSize || it <= 0 || B[it - 1] != 0)

这样就能在访问B之前，先过滤掉所有超出范围的元素，避免越界。

内容的提问来源于stack exchange，提问作者BaikenM