Исправить утечки памяти в моем собственном двусвязном списке

Question

Я пытаюсь написать свой двусвязный список. Но Вальгринд говорит, что у меня здесь утечки памяти. Я понятия не имею, что может произойти в тех строках, которые мне показывает Вальгринд. Не могли бы вы помочь мне?

Я пытался изменить весь мой указатель на shared_ptr, но это не помогло.

Весь код с int main ():

#include <cstddef>
#include <iostream>
#include <vector>
#include <random>
#include <memory>

template <typename T>
class List {

private:
    class ListNode {

    public:
        T value_;
        std::shared_ptr<ListNode> prev_;
        std::shared_ptr<ListNode> next_;

        ListNode(T &value, std::shared_ptr<ListNode> prev, std::shared_ptr<ListNode> next)
                : value_(std::move(value)) {
            std::swap(next_, next);
            std::swap(prev_, prev);
        }

        ~ListNode() {
            prev_ = nullptr;
            next_ = nullptr;
        }
    };

    class Iterator {

    public:
        Iterator(const std::shared_ptr<ListNode> &current) : current_(current) {
        }

        Iterator &operator++() {
            if (current_->next_ != nullptr) {
                current_ = current_->next_;
            }
            return *this;
        }

        Iterator operator++(int) {
            Iterator cpy(*this);
            if (current_->next_ != nullptr) {
                current_ = current_->next_;
            }
            return cpy;
        }

        Iterator &operator--() {
            if (current_->prev_ != nullptr) {
                current_ = current_->prev_;
            }
            return *this;
        }

        Iterator operator--(int) {
            Iterator cpy(*this);
            if (current_->prev_ != nullptr) {
                current_ = current_->prev_;
            }
            return cpy;
        }

        T &operator*() const {
            return current_->value_;
        }

        T &operator->() const {
            return current_->value_;
        }

        bool operator==(const Iterator &rhs) const {
            return current_ == rhs.current_;
        }

        bool operator!=(const Iterator &rhs) const {
            return current_ != rhs.current_;
        }

        std::shared_ptr<ListNode> current_;
    };

    std::shared_ptr<ListNode> begin_;
    std::shared_ptr<ListNode> end_;
    size_t size_ = 0;

public:
    List() : begin_(nullptr), end_(nullptr), size_(0) {
    }

    List(List &lst) {
        begin_ = nullptr;
        end_ = nullptr;
        size_ = 0;
        for (auto x : lst) {
            PushBack(x);
        }
    }

    List(List &&lst) {
        begin_ = nullptr;
        end_ = nullptr;
        size_ = 0;
        for (auto &x : lst) {
            PushBack(std::move(x));
        }
        lst.begin_ = nullptr;
        lst.end_ = nullptr;
        lst.size_ = 0;
    }

    ~List() {
        for (auto &x : (*this)) {
            x.~T();
        }
        begin_ = nullptr;
        end_ = nullptr;
        size_ = 0;
    }

    List &operator=(List &lst) {
        this->~List();
        for (auto x : lst) {
            PushBack(x);
        }
        return *this;
    }

    List &operator=(List &&lst) {
        for (auto &x : lst) {
            PushBack(std::move(x));
        }

        lst.begin_ = nullptr;
        lst.end_ = nullptr;
        lst.size_ = 0;
        return *this;
    }

    bool IsEmpty() const {
        return size_ == 0;
    }

    size_t Size() const {
        return size_;
    }

    void PushBack(T &elem) {
        if (end_ == nullptr) {
            begin_ = std::make_shared<ListNode>(elem, nullptr, nullptr);
            end_ = std::make_shared<ListNode>(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            end_->value_ = elem;
            end_->next_ = std::make_shared<ListNode>(elem, end_, nullptr);
            end_ = end_->next_;
        }
        size_++;
    }

    void PushBack(T &&elem) {
        if (end_ == nullptr) {
            begin_ = std::make_shared<ListNode>(elem, nullptr, nullptr);
            end_ = std::make_shared<ListNode>(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            end_->value_ = std::move(elem);
            end_->next_ = std::make_shared<ListNode>(elem, end_, nullptr);
            auto q = end_->next_;
            end_ = q;
            q.reset();
        }
        size_++;
    }

    void PushFront(const T &elem) {
        if (end_ == nullptr) {
            begin_ = std::make_shared<ListNode>(elem, nullptr, nullptr);
            end_ = std::make_shared<ListNode>(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            begin_->prev_ = std::make_shared<ListNode>(elem, nullptr, begin_);
            begin_ = begin_->prev_;
        }
        size_++;
    }

    void PushFront(T &&elem) {
        if (end_ == nullptr) {
            begin_ = std::make_shared<ListNode>(elem, nullptr, nullptr);
            end_ = std::make_shared<ListNode>(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            begin_->prev_ = std::make_shared<ListNode>(elem, nullptr, begin_);
            begin_ = begin_->prev_;
        }
        size_++;
    }

    T &Front() {
        return begin_->value_;
    }

    const T &Front() const {
        return begin_->value_;
    }

    T &Back() {
        return end_->prev_->value_;
    }

    const T &Back() const {
        return end_->prev_->value_;
    }

    void PopBack() {
        if (end_ != begin_) {
            std::shared_ptr<ListNode> cur_node = end_;
            if (end_->prev_) {
                end_->prev_->next_ = nullptr;
                end_ = end_->prev_;
                size_--;
            } else {
                begin_ = nullptr;
                end_ = nullptr;
                size_--;
            }
        } else {
            begin_.reset();
            end_.reset();
            begin_ = nullptr;
            end_ = nullptr;
            size_--;
        }
    }

    void PopFront() {
        if (begin_) {
            std::shared_ptr<ListNode> cur_node = begin_;
            if (begin_->next_) {
                begin_->next_->prev_ = nullptr;
                begin_ = begin_->next_;
                size_--;
            } else {
                begin_ = nullptr;
                end_ = nullptr;
                size_--;
            }
        } else {
            begin_ = nullptr;
            end_ = nullptr;
            size_--;
        }
    }

    Iterator Begin() {
        return Iterator(begin_);
    }

    Iterator End() {
        return Iterator(end_);
    }

    Iterator begin() {  // NOLINT
        return List<T>::Iterator(begin_);
    }

    Iterator end() {  // NOLINT
        return List<T>::Iterator(end_);
    }
};
int main() {
 ////////
    List<std::shared_ptr<int>> l10;
    l10.PushBack(std::make_shared<int>(0));
    l10.PushBack(std::make_shared<int>(1));
    l10.PushBack(std::make_shared<int>(2));

    List<std::shared_ptr<int>> l20{l10};
    List<std::shared_ptr<int>> l30;

    l30 = l10;

    std::cout << (l30.Size() == 3);
    std::cout << (l20.Size() == 3);

    std::cout << (l10.Front().use_count() == 3);
////////

    List<std::unique_ptr<int>> l1;

    l1.PushBack(std::make_unique<int>(0));
    l1.PushBack(std::make_unique<int>(1));
    l1.PushBack(std::make_unique<int>(2));

    List<std::unique_ptr<int>> l2{std::move(l1)};

    std::cout << (*l2.Front() == 0);

    std::cout << (l1.Size() == 0);
    std::cout << (l2.Size() == 3);

    List<std::unique_ptr<int>> l3;

    l3 = std::move(l2);

    std::cout << (l2.Size() == 0);
    std::cout << (l3.Size() == 3);

    std::cout << (*l3.Front() == 0);

/////////
    List<int> l;
    l.PushBack(0);
    l.PushBack(1);
    l.PushBack(2);

    auto i = l.Begin();
    std::cout << (*i == 0) << std::endl;
    std::cout << (*(++i) == 1) << std::endl;
    std::cout << (*(++i) == 2) << std::endl;

    std::cout << (*(i++) == 2) << std::endl;
    std::cout << (i == l.End()) << std::endl;

    std::cout << (*(--i) == 2) << std::endl;
    std::cout << (*(--i) == 1) << std::endl;
    std::cout << (*(i--) == 1) << std::endl;

    std::cout << (i == l.Begin()) << std::endl;

    i++;
    std::cout << (i == ++l.Begin()) << std::endl;
}

Valgrind говорит, что я ошибаюсь в этой строке в обеих функциях push_front и push_back:

begin_ = std::make_shared<ListNode>(elem, nullptr, nullptr);

Снимок экрана с предупреждениями Valgrinid: https://yadi.sk/i/IcHkUUjEeq-YiQ У меня недостаточно репутации, чтобы опубликовать его как изображение. = (

Версия с необработанными указателями:

#pragma once

#include <cstddef>
#include <iostream>
#include <vector>
#include <random>
#include <memory>

template <typename T>
class List {

private:
    class ListNode {

    public:
        T value_;
        ListNode *prev_;
        ListNode *next_;

        ListNode(T &value, ListNode *prev, ListNode *next)
                : value_(std::move(value)) {
            std::swap(next_, next);
            std::swap(prev_, prev);
        }

        ~ListNode() {
            prev_ = nullptr;
            next_ = nullptr;
        }
    };

    class Iterator {

    public:
        Iterator(ListNode *current) : current_(current) {
        }

        Iterator &operator++() {
            if (current_->next_ != nullptr) {
                current_ = current_->next_;
            }
            return *this;
        }

        Iterator operator++(int) {
            Iterator cpy(*this);
            if (current_->next_ != nullptr) {
                current_ = current_->next_;
            }
            return cpy;
        }

        Iterator &operator--() {
            if (current_->prev_ != nullptr) {
                current_ = current_->prev_;
            }
            return *this;
        }

        Iterator operator--(int) {
            Iterator cpy(*this);
            if (current_->prev_ != nullptr) {
                current_ = current_->prev_;
            }
            return cpy;
        }

        T &operator*() const {
            return current_->value_;
        }

        T &operator->() const {
            return current_->value_;
        }

        bool operator==(const Iterator &rhs) const {
            return current_ == rhs.current_;
        }

        bool operator!=(const Iterator &rhs) const {
            return current_ != rhs.current_;
        }

        ListNode *current_;
    };

    ListNode *begin_;
    ListNode *end_;
    size_t size_ = 0;

public:
    List() : begin_(nullptr), end_(nullptr), size_(0) {
    }

    List(List &lst) {
        begin_ = nullptr;
        end_ = nullptr;
        size_ = 0;
        for (auto x : lst) {
            PushBack(x);
        }
    }

    List(List &&lst) {
        begin_ = nullptr;
        end_ = nullptr;
        size_ = 0;
        for (auto &x : lst) {
            PushBack(std::move(x));
        }
        lst.begin_ = nullptr;
        lst.end_ = nullptr;
        lst.size_ = 0;
    }

    ~List() {
        for (auto &x : (*this)) {
            x.~T();
        }
        begin_ = nullptr;
        end_ = nullptr;
        size_ = 0;
    }

    List &operator=(List &lst) {
        this->~List();
        for (auto x : lst) {
            PushBack(x);
        }
        return *this;
    }

    List &operator=(List &&lst) {
        for (auto &x : lst) {
            PushBack(std::move(x));
        }

        lst.begin_ = nullptr;
        lst.end_ = nullptr;
        lst.size_ = 0;
        return *this;
    }

    bool IsEmpty() const {
        return size_ == 0;
    }

    size_t Size() const {
        return size_;
    }

    void PushBack(T &elem) {
        if (end_ == nullptr) {
            begin_ = new ListNode(elem, nullptr, nullptr);
            end_ = new ListNode(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            end_->value_ = elem;
            end_->next_ = new ListNode(elem, end_, nullptr);
            end_ = end_->next_;
        }
        size_++;
    }

    void PushBack(T &&elem) {
        if (end_ == nullptr) {
            begin_ = new ListNode(elem, nullptr, nullptr);
            end_ = new ListNode(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            end_->value_ = std::move(elem);
            end_->next_ = new ListNode(elem, end_, nullptr);
            auto q = end_->next_;
            end_ = q;
        }
        size_++;
    }

    void PushFront(const T &elem) {
        if (end_ == nullptr) {
            begin_ = new ListNode(elem, nullptr, nullptr);
            end_ = new ListNode(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            begin_->prev_ = new ListNode(elem, nullptr, begin_);
            begin_ = begin_->prev_;
        }
        size_++;
    }

    void PushFront(T &&elem) {
        if (end_ == nullptr) {
            begin_ = new ListNode(elem, nullptr, nullptr);
            end_ = new ListNode(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            begin_->prev_ = new ListNode(elem, nullptr, begin_);
            begin_ = begin_->prev_;
        }
        size_++;
    }

    T &Front() {
        return begin_->value_;
    }

    const T &Front() const {
        return begin_->value_;
    }

    T &Back() {
        return end_->prev_->value_;
    }

    const T &Back() const {
        return end_->prev_->value_;
    }

    void PopBack() {
        if (end_ != begin_) {
            ListNode *cur_node = end_;
            if (end_->prev_) {
                end_->prev_->next_ = nullptr;
                end_ = end_->prev_;
                size_--;
            } else {
                begin_ = nullptr;
                end_ = nullptr;
                size_--;
            }
        } else {
            begin_ = nullptr;
            end_ = nullptr;
            size_--;
        }
    }

    void PopFront() {
        if (begin_) {
            ListNode *cur_node = begin_;
            if (begin_->next_) {
                begin_->next_->prev_ = nullptr;
                begin_ = begin_->next_;
                size_--;
            } else {
                begin_ = nullptr;
                end_ = nullptr;
                size_--;
            }
        } else {
            begin_ = nullptr;
            end_ = nullptr;
            size_--;
        }
    }

    Iterator Begin() {
        return Iterator(begin_);
    }

    Iterator End() {
        return Iterator(end_);
    }

    Iterator begin() {  // NOLINT
        return Iterator(begin_);
    }

    Iterator end() {  // NOLINT
        return Iterator(end_);
    }
};

int main() {
 ////////
    List<std::shared_ptr<int>> l10;
    l10.PushBack(std::make_shared<int>(0));
    l10.PushBack(std::make_shared<int>(1));
    l10.PushBack(std::make_shared<int>(2));

    List<std::shared_ptr<int>> l20{l10};
    List<std::shared_ptr<int>> l30;

    l30 = l10;

    std::cout << (l30.Size() == 3);
    std::cout << (l20.Size() == 3);

    std::cout << (l10.Front().use_count() == 3);
////////

    List<std::unique_ptr<int>> l1;

    l1.PushBack(std::make_unique<int>(0));
    l1.PushBack(std::make_unique<int>(1));
    l1.PushBack(std::make_unique<int>(2));

    List<std::unique_ptr<int>> l2{std::move(l1)};

    std::cout << (*l2.Front() == 0);

    std::cout << (l1.Size() == 0);
    std::cout << (l2.Size() == 3);

    List<std::unique_ptr<int>> l3;

    l3 = std::move(l2);

    std::cout << (l2.Size() == 0);
    std::cout << (l3.Size() == 3);

    std::cout << (*l3.Front() == 0);

/////////
    List<int> l;
    l.PushBack(0);
    l.PushBack(1);
    l.PushBack(2);

    auto i = l.Begin();
    std::cout << (*i == 0) << std::endl;
    std::cout << (*(++i) == 1) << std::endl;
    std::cout << (*(++i) == 2) << std::endl;

    std::cout << (*(i++) == 2) << std::endl;
    std::cout << (i == l.End()) << std::endl;

    std::cout << (*(--i) == 2) << std::endl;
    std::cout << (*(--i) == 1) << std::endl;
    std::cout << (*(i--) == 1) << std::endl;

    std::cout << (i == l.Begin()) << std::endl;

    i++;
    std::cout << (i == ++l.Begin()) << std::endl;
}

Эта версия также прошла все тесты.

Теперь Valgrind говорит, что я ошибаюсь в строке:

begin_ = new ListNode(elem, nullptr, nullptr);

Выход Valgrind (одна из ошибок):

<error>
  <unique>0x16</unique>
  <tid>1</tid>
  <kind>Leak_DefinitelyLost</kind>
  <xwhat>
    <text>128 (32 direct, 96 indirect) bytes in 1 blocks are definitely lost in loss record 23 of 25</text>
    <leakedbytes>128</leakedbytes>
    <leakedblocks>1</leakedblocks>
  </xwhat>
  <stack>
    <frame>
      <ip>0x4C3017F</ip>
      <obj>/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so</obj>
      <fn>operator new(unsigned long)</fn>
    </frame>
    <frame>
      <ip>0x10AB0B</ip>
      <obj>/home/meetch/CLionProjects/LinkedList/cmake-build-debug/LinkedList</obj>
      <fn>List&lt;std::shared_ptr&lt;int&gt; &gt;::PushBack(std::shared_ptr&lt;int&gt;&amp;)</fn>
      <dir>/home/meetch/CLionProjects/LinkedList</dir>
      <file>main.cpp</file>
      <line>154</line>
    </frame>
    <frame>
      <ip>0x109D5A</ip>
      <obj>/home/meetch/CLionProjects/LinkedList/cmake-build-debug/LinkedList</obj>
      <fn>List&lt;std::shared_ptr&lt;int&gt; &gt;::List(List&lt;std::shared_ptr&lt;int&gt; &gt;&amp;)</fn>
      <dir>/home/meetch/CLionProjects/LinkedList</dir>
      <file>main.cpp</file>
      <line>100</line>
    </frame>
    <frame>
      <ip>0x109086</ip>
      <obj>/home/meetch/CLionProjects/LinkedList/cmake-build-debug/LinkedList</obj>
      <fn>test_copy_constr()</fn>
      <dir>/home/meetch/CLionProjects/LinkedList</dir>
      <file>main.cpp</file>
      <line>484</line>
    </frame>
    <frame>
      <ip>0x108F93</ip>
      <obj>/home/meetch/CLionProjects/LinkedList/cmake-build-debug/LinkedList</obj>
      <fn>main</fn>
      <dir>/home/meetch/CLionProjects/LinkedList</dir>
      <file>main.cpp</file>
      <line>473</line>
    </frame>
  </stack>
  <suppression>
    <sname>insert_a_suppression_name_here</sname>
    <skind>Memcheck:Leak</skind>
    <skaux>match-leak-kinds: definite</skaux>
    <sframe> <fun>_Znwm</fun> </sframe>
    <sframe> <fun>_ZN4ListISt10shared_ptrIiEE8PushBackERS1_</fun> </sframe>
    <sframe> <fun>_ZN4ListISt10shared_ptrIiEEC1ERS2_</fun> </sframe>
    <sframe> <fun>_Z16test_copy_constrv</fun> </sframe>
    <sframe> <fun>main</fun> </sframe>
    <rawtext>
<![CDATA[
{
   <insert_a_suppression_name_here>
   Memcheck:Leak
   match-leak-kinds: definite
   fun:_Znwm
   fun:_ZN4ListISt10shared_ptrIiEE8PushBackERS1_
   fun:_ZN4ListISt10shared_ptrIiEEC1ERS2_
   fun:_Z16test_copy_constrv
   fun:main
}
]]>
    </rawtext>
  </suppression>
</error>

Answer 1

Я не уверен, что мне не хватает какой-то фундаментальной проблемы с двусвязным списком, который вы создаете. Но на основе скриншота ошибка именно в этом коде

 void PushBack(T &&elem) {
        if (end_ == nullptr) {
            begin_ = new ListNode(elem, nullptr, nullptr);
            end_ = new ListNode(elem, begin_, nullptr);
            begin_->next_ = end_;
        } else {
            end_->value_ = std::move(elem);
            end_->next_ = new ListNode(elem, end_, nullptr);
            auto q = end_->next_;
            end_ = q;
        }
        size_++;
    }

Что меня смущает, так это то, что эта версия (есть другая с & elem) принимает двойной указатель на элемент, но он вызывает конструктор точно так жекак единственный указатель. Похоже, вы хотели бы что-то вроде. Но я не уверен на 100%, потому что я не уверен, что делает эта версия PushBack, а другая - нет.

        begin_ = new ListNode(*elem, nullptr, nullptr);