Вектор рекурсивных структур имеет проблемы с памятью

Я полностью застрял в простом куске кода, который плохо себя ведет с памятью (как сообщает Valgrind). Я сократил его до этого короткого теста:

#include <vector>

struct el
{
    el * next = nullptr;
};

class list
{
public:
    list(): tail(nullptr) {}

    void push_back()
    {
        el nw;
        m_list.push_back(nw);

        if (tail == nullptr)
            tail = &m_list.back();
        else
        {
            tail->next = &m_list.back();
            tail = tail->next;
        }
    }

private:
    std::vector<el> m_list;
    el * tail;
};

int main()
{
    list a;
    a.push_back();
    a.push_back();
    return 0;
}

Я ожидаю, что он создаст массив с 2 структурами, первая из которых имеет указатель на вторую. Реальный источник падает с segfault на уничтожение, поэтому я считаю этот отчет важным:

==1630== Invalid write of size 8
==1630==    at 0x400A37: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Address 0x5a86c80 is 0 bytes inside a block of size 8 free'd
==1630==    at 0x4C2A8DC: operator delete(void*) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4011D5: __gnu_cxx::new_allocator<el>::deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400F79: std::_Vector_base<el, std::allocator<el> >::_M_deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400DA3: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Block was alloc'd at
==1630==    at 0x4C29780: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4012BB: __gnu_cxx::new_allocator<el>::allocate(unsigned long, void const*) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4010D2: std::_Vector_base<el, std::allocator<el> >::_M_allocate(unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400CC1: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x40095D: main (in /home/ilya/Projects/algos/a.out)
==1630==
==1630== Invalid read of size 8
==1630==    at 0x400A42: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Address 0x5a86c80 is 0 bytes inside a block of size 8 free'd
==1630==    at 0x4C2A8DC: operator delete(void*) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4011D5: __gnu_cxx::new_allocator<el>::deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400F79: std::_Vector_base<el, std::allocator<el> >::_M_deallocate(el*, unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400DA3: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400969: main (in /home/ilya/Projects/algos/a.out)
==1630==  Block was alloc'd at
==1630==    at 0x4C29780: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1630==    by 0x4012BB: __gnu_cxx::new_allocator<el>::allocate(unsigned long, void const*) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4010D2: std::_Vector_base<el, std::allocator<el> >::_M_allocate(unsigned long) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400CC1: void std::vector<el, std::allocator<el> >::_M_emplace_back_aux<el const&>(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x400B42: std::vector<el, std::allocator<el> >::push_back(el const&) (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x4009FF: list::push_back() (in /home/ilya/Projects/algos/a.out)
==1630==    by 0x40095D: main (in /home/ilya/Projects/algos/a.out)
Источник

1 ответ

Решение

После того, как вы нажмете на вектор или иным образом измените его, все ссылки и указатели на сохраненные элементы становятся недействительными, поэтому все tail а также next поля будут содержать висячие указатели. И разыменование их приведет к неопределенному поведению. Вы действительно можете использовать std::list или (если вы просто пишете некоторую реализацию списка для целей обучения), вы можете сначала заполнить вектор, а затем собрать указатели на сохраненные элементы, зная, что они останутся действительными.

Источник
Другие вопросы по тегам