c++ - 修复我自己的双向链表中的内存泄漏

Question

我正在尝试编写自己的双向链表。但是 Valgrind 说我这里有内存泄漏。我不知道 Valgrind 向我展示的行会发生什么坏事。你能帮帮我吗？

我试图将我所有的指针更改为 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);