C++:shared_ptr 泄漏，链表

Question

一般来说，我是 shared_ptr 和智能指针的新手。我的想法是智能指针通常不会泄漏内存。我正在编写一个巨大的链表文件，我将所有“原始”指针转换为智能指针后发生了一些内存泄漏。我正在使用带有“任意节点”的链表，其中每个节点都有一个 next 指针，以及 arb 指针，它指向同一链表中的任意节点。这可能会创建循环指针。问题是，在存在循环指针的情况下如何消除内存泄漏？

链表.hpp:

#pragma once

#include <exception>
#include <iostream>
#include <unordered_map>


template <typename T> class LinkedList;
class Int;
template <typename T>
std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);
std::ostream& operator<<(std::ostream& os, const Int& num);


/** Node class
 *
 * @tparam T template type
 */
template <typename T>
class Node {
public:
    /** Constructor */
    Node(T e = T(0)) : _elem(e), _next(nullptr), _arb(nullptr) {}
    // ~Node() { delete _next; }
public:
    // Getters/Setters:
    /** Return the value in the node
     *
     * @returns T value
     */
    const T& value() const { return this->_elem; }
    /** Return the next node
     *
     * @returns std::shared_ptr< Node<T> >
     */
    std::shared_ptr<Node<T>> next() const { return this->_next; }
    /** Return the arbitrary node
     *
     * @returns std::shared_ptr< Node<T> >
     */
    std::shared_ptr<Node<T>> arb() const { return this->_arb; }
    /** Set the value in the node
     *
     * @param T value
     */
    void setValue(const T& e) { this->_elem = e; }
    /** Set the next pointer
     *
     * @param std::shared_ptr< Node<T> > the next "next" pointer
     */
    void setNext(std::shared_ptr< Node<T> > n) { this->_next = n; }
    /** Set the arbitrary pointer
     *
     * @param std::shared_ptr< Node<T> > the next "arb" pointer
     */
    void setArb(std::shared_ptr< Node<T> > n) { this->_arb = n; }
private:
    T _elem;                    //!< Stored value
    // std::shared_ptr< Node<T> > _next;             //!< Next element
    // std::shared_ptr< Node<T> > _arb;              //!< Arbitrary element
    std::shared_ptr< Node<T> > _next;             //!< Next element
    std::shared_ptr< Node<T> > _arb;              //!< Arbitrary element

    friend class LinkedList<T>; //!< Friend class
};


/** Singly Linked List
 *
 * @tparam T template type
 */
template <typename T>
class LinkedList {
public:
    LinkedList();
    // ~LinkedList();
public:
    bool empty() const;
    const T& front() const throw(std::range_error);
    void addFront(const T& e);
    void removeFront();
public:
    // Housekeeping
    std::size_t size() const;
    std::shared_ptr< Node<T> > head();
    void setHead(std::shared_ptr< Node<T> > h);             // This is dangerous!!!
    // template <typename U>
    // friend std::ostream& operator<<(std::ostream& os, const LinkedList<U>& list);
    std::shared_ptr< Node<T> > operator[](std::size_t idx);
    friend std::ostream& operator<<<>(std::ostream& os, const LinkedList& list);
    void printArb();
private:
    std::shared_ptr< Node<T> > _head;
    // std::size_t _size;

    // Rust solutions after this point
public:
    void reverse();
    void reverseRecursive();
    void deleteKey (T key);
    LinkedList<T> deepCopy();
    void sort();
private:
    std::shared_ptr< Node<T> > _reverse_recursive(std::shared_ptr< Node<T> > node);
    std::shared_ptr< Node<T> > _deep_copy_1 (std::shared_ptr< Node<T> > head);
    std::shared_ptr< Node<T> > _deep_copy_2 (std::shared_ptr< Node<T> > head);
    std::shared_ptr< Node<T> > _sorted_insert(std::shared_ptr< Node<T> > head, std::shared_ptr< Node<T> > node);
    std::shared_ptr< Node<T> > _insertion_sort(std::shared_ptr< Node<T> > head);
};



/** Constructor */
template <typename T>
LinkedList<T>::LinkedList() : _head(nullptr)/*, _size(0)*/ {}

/** Destructor */
// template <typename T>
// LinkedList<T>::~LinkedList() {
//     while (!empty()) removeFront();
//     // delete _head;
// }

/** Empty?
 *
 * @returns bool True if empty
 */
template <typename T>
bool LinkedList<T>::empty() const {
    return _head == nullptr;
}

/** Get front element (read-only)
 *
 * @returns T
 */
template <typename T>
const T& LinkedList<T>::front() const
    throw (std::range_error) {
    if (empty()) {
        throw std::range_error("Linked List empty! Cannot get front()");
        // return 0;
    }
    return _head->_elem;
}

/** Add element in the front of the list
 *
 * @param e Element to be added
 */
template <typename T>
void LinkedList<T>::addFront(const T& e) {
    // std::shared_ptr< Node<T> > v = std::make_shared< Node<T> >();// (new Node<T>);
    std::shared_ptr< Node<T> > v(new Node<T>);
    v->_elem = e;
    v->_next = _head;
    _head = v;
    // _size++;
}

/** Remove the first element
 *
 */
template <typename T>
void LinkedList<T>::removeFront() {
    if (this->empty()) return;
    std::shared_ptr< Node<T> > old = _head;
    _head = old->_next;
    // _size--;
    // delete old;
    old.reset();
}

/** Number of elements in the list
 *
 * @returns std::size_t Number of elements in the list
 */
template <typename T>
std::size_t LinkedList<T>::size() const {
    // return this->_size;
    Node<T> head = this->head();
    std::size_t len = 0;
    while (head != nullptr) {
        head = head->next();
        len++;
    }
    return len;    
}

/** Returns the head of the linked list
 *
 * @returns std::shared_ptr< Node<T> > the head of the current linked list
 */
template <typename T>
std::shared_ptr< Node<T> > LinkedList<T>::head() { return this->_head; }

/** Set the head to different node
 *
 * NOTE: this method is dangerous as it will lose information
 * about other nodes!!!
 *
 * @params std::shared_ptr< Node<T> > the node to be set as head
 */
template <typename T>
void LinkedList<T>::setHead(std::shared_ptr< Node<T> > h) {
    this->_head = h;
    // this->resetSize();
}


/** Operator<< for the linked list
 *
 * @returns std::ostream
 * @param LHS->std::ostream
 * @param RHS->LinkedList<T>
 */
template <typename T>
std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list) {

    os << "HEAD->";
    std::shared_ptr< Node<T> > ptr = list._head;
    while (ptr != nullptr) {
        os << ptr->_elem << "->";
        ptr = ptr->_next;
    }
    os << "NULL";
    // delete ptr;
    ptr.reset();
    return os;

    /*
      os << "[HEAD]\n V\n";
      std::shared_ptr< Node<T> > ptr = list._head;
      while (ptr != nullptr) {
      os << "[" << ptr->_elem << "]->";
      os << "[";// << ( (ptr->arb() == nullptr) ? "NULL" : ptr->arb()->_elem) << "]\n V";
      if (ptr->arb() == nullptr)
      os << "NULL";
      else
      os << ptr->arb()->_elem << "|" << (ptr->arb());

      os << "]\n V\n";
      ptr = ptr->_next;
      }
      os << "[NULL]";
      delete ptr;
      return os;
    */
}

template <typename T>
void LinkedList<T>::printArb() {
    std::cout << "[HEAD]\n V\n";
    std::shared_ptr< Node<T> > ptr = this->_head;
    while (ptr != nullptr) {
        std::cout << "[" << ptr->_elem << "]->";
        std::cout << "[";// << ( (ptr->arb() == nullptr) ? "NULL" : ptr->arb()->_elem) << "]\n V";
        if (ptr->arb() == nullptr)
            std::cout << "NULL";
        else
            std::cout << ptr->arb()->_elem << "|" << (ptr->arb());

        std::cout << "]\n V\n";
        ptr = ptr->_next;
    }
    std::cout << "[NULL]";
    // delete ptr;
    ptr.reset();
    // return std::cout;
}

/* Rust solutions after this point */

/** Reverse the linked list using solution 1 (iterative)
 */
template <typename T>
void LinkedList<T>::reverse() {
    if (this->_head == nullptr || this->_head->_next == nullptr)
        return;

    std::shared_ptr< Node<T> > list_to_do = this->_head->_next;
    this->_head->_next = nullptr;

    while (list_to_do != nullptr) {
        std::shared_ptr< Node<T> > temp = list_to_do;
        list_to_do = list_to_do->_next;

        temp->_next = _head;
        _head = temp;
    }
    // delete list_to_do;
    list_to_do.reset();
}

/** Reverse the linked list using solution 2 (recursive)
 */
template <typename T>
void LinkedList<T>::reverseRecursive() {
    this->_head = this->_reverse_recursive(this->_head); // This method is declared later in the "Helpers" section
}

/** Delete a node with key `key` from the linked list
 *
 * @params T Key value
 */
template <typename T>
void LinkedList<T>::deleteKey (T key) {
    std::shared_ptr< Node<T> > prev = nullptr;
    std::shared_ptr< Node<T> > current = this->head();

    while (current != nullptr) {
        if (current->value() == key) {
            // this->_size--;
            break;              // Found it! :)
        }

        prev = current;
        current = current->next();
    }

    if (current == nullptr) {
        return;                         // Didn't find it :(
    }

    if (current == this->head()) {
        this->setHead(this->head()->next());
    } else {
        prev->setNext(current->next());
    }

    // delete current;
    current.reset();
}

/** Deep copy method
 *
 * @returns LinkedList<T> New linked list
 */
template <typename T>
LinkedList<T> LinkedList<T>::deepCopy() {
    LinkedList<T> copy;
    copy.setHead(this->_deep_copy_2(this->head()));
    return copy;
}

/** Sort the current linked list */
template <typename T>
void LinkedList<T>::sort() {
    this->setHead(this->_insertion_sort(this->head()));
}

//////////////////////////////////////
// Helpers:

/** Reverse a singly linked list (Recursive)
 *
 * @returns std::shared_ptr< Node<T> > The head of the reversed linked list
 * @param std::shared_ptr< Node<T> > The head of the linked list to be reversed
 */
template <typename T>
std::shared_ptr< Node<T> > LinkedList<T>::_reverse_recursive (std::shared_ptr< Node<T> > node) {
    // If the size of the linked list = 0 or 1, nothing to do :)
    if (node == nullptr || node->next() == nullptr)
        return node;

    std::shared_ptr< Node<T> > reversed_list = this->_reverse_recursive(node->next());

    node->next()->setNext(node);
    node->setNext(nullptr);
    return reversed_list;
}

/** Deep copy the single linked list (solution 1)
 *
 * @returns std::shared_ptr< Node<T> > The head of the new linked list
 * @params std::shared_ptr< Node<T> > The head of the original linked list
 */
template <typename T>
std::shared_ptr< Node<T> > LinkedList<T>::_deep_copy_1 (std::shared_ptr< Node<T> > head) {
    // If the linked list is empty, return
    if (head == nullptr) {
        return nullptr;
    }

    std::shared_ptr< Node<T> > current = head;
    std::shared_ptr< Node<T> > new_head = nullptr;
    std::shared_ptr< Node<T> > new_prev = nullptr;
    std::unordered_map<std::shared_ptr< Node<T> >, std::shared_ptr< Node<T> >> map;

    // Create copy of the linked list, recording the corresponding
    // nodes in hashmap without updating arbitrary pointer
    while (current != nullptr) {
        std::shared_ptr< Node<T> > new_node = std::make_shared< Node<T> >(current->value());
        // new Node<T>(current->value());

        // Copy the old arbitrary pointer in the new node
        new_node->setArb(current->arb());

        if (new_prev != nullptr) {
            new_prev->setNext(new_node);
        } else {
            new_head = new_node;
        }

        map[current] = new_node;
        new_prev = new_node;
        current = current->next();
    }

    std::shared_ptr< Node<T> > new_current = new_head;

    // Update arbitrary pointer:
    while (new_current != nullptr) {
        if (new_current->arb() != nullptr) {
            std::shared_ptr< Node<T> > node = map[new_current->arb()];
            new_current->setArb(node);
        }
        new_current = new_current->next();
    }
    return new_head;
}

/** Deep copy the single linked list (solution 2)
 *
 * @returns std::shared_ptr< Node<T> > The head of the new linked list
 * @params std::shared_ptr< Node<T> > The head of the original linked list
 */
template <typename T>
std::shared_ptr< Node<T> > LinkedList<T>::_deep_copy_2 (std::shared_ptr< Node<T> > head) {
    // If the linked list is empty, return
    if (head == nullptr) {
        return nullptr;
    }

    std::shared_ptr< Node<T> > current(head);

    // Inserting new nodes within the existing linked list
    while (current != nullptr) {
        // std::shared_ptr< Node<T> > new_node(std::make_shared< Node<T> >(current->value()));
        std::shared_ptr< Node<T> > new_node(new Node<T>(current->value()));
        new_node->setNext(current->next());
        current->setNext(new_node);
        current = new_node->next();
    }

    // Setting correct arbitrary pointers
    current = head;
    while (current != nullptr) {
        if (current->arb() != nullptr) {
            current->next()->setArb(current->arb()->next());
        }
        current = current->next()->next();
    }

    // Separating lists
    current = head;
    std::shared_ptr< Node<T> > new_head(head->next());
    std::shared_ptr< Node<T> > copied_current(nullptr);

    while (current != nullptr) {
        copied_current = current->next();
        current->setNext(copied_current->next());

        if (copied_current->next() != nullptr) {
            copied_current->setNext(copied_current->next()->next());
        }

        current = current->next();
    }
    return new_head;
}

/** Insert in a sorted manner
 *
 * This method looks for an appropriate position
 * for a given node and inserts it into the linked
 * list with head "head"
 *
 * @returns std::shared_ptr< Node<T> > The head of the new linked list
 * @param std::shared_ptr< Node<T> > head -> the head of the linked list
 * @param std::shared_ptr< Node<T> > node -> node to be inserted
 */
template <typename T>
std::shared_ptr< Node<T> > LinkedList<T>::_sorted_insert(std::shared_ptr< Node<T> > head, std::shared_ptr< Node<T> > node) {
    if (node == nullptr) {
        return head;
    }

    if (head == nullptr || node->value() <= head->value()) {
        node->setNext(head);
        return node;
    }

    std::shared_ptr< Node<T> > curr = head;

    while (curr->next() != nullptr && curr->next()->value() < node->value()) {
        curr = curr->next();
    }

    node->setNext(curr->next());
    curr->setNext(node);

    return head;
}


/** Sort the linked list (destructive)
 *
 * Sort the linked list and destroy the original
 *
 * @returns std::shared_ptr< Node<T> > The head of the new linked list
 * @param std::shared_ptr< Node<T> > head -> the head of the old linked list
 */

template <typename T>
std::shared_ptr< Node<T> > LinkedList<T>::_insertion_sort(std::shared_ptr< Node<T> > head){
    std::shared_ptr< Node<T> > sorted = nullptr;
    std::shared_ptr< Node<T> > curr = head;

    while (curr != nullptr) {
        std::shared_ptr< Node<T> > temp = curr->next();
        sorted = this->_sorted_insert(sorted, curr);
        curr = temp;
    }

    return sorted;
}

//////////////////////////////////////
// This is a specialized Linked List
// used for integer representation

/** Int class
 *
 * Every digit in the integer is represented as a node in
 * a singly linked list starting from ones
 */
class Int {
public:
    Int() { this->_num.setHead(nullptr); }
    Int(int n);
    Int (std::shared_ptr< Node<int> > n) { this->_num.setHead(n); }
    // ~Int();
public:
    std::shared_ptr< Node<int> > getHead() const {
        return const_cast<Int*>(this)->_num.head(); }
    Int& operator=(const Int& rhs);
    int value() const;
    // Int operator+(const Int& a, const Int& b);
public:
    friend std::ostream& operator<<(std::ostream& os, const Int& num);
    friend Int operator+(const Int&, const Int&);
private:
    LinkedList<int> _num;
    // bool negative;
};

/** Signed constructor
 */
Int::Int(int n) {
    // delete &_num;
    this->_num = LinkedList<int>();
    if (n < 0)
        throw (std::range_error("No support for negative numbers...!"));
    do {
        _num.addFront(n % 10);
        n = n / 10;
    } while (n > 0);
    _num.reverse();
}
/*
  Int::~Int() {
  while (!this->_num.empty()) this->_num.removeFront();
  }
*/

/** Copy assignment !!!
 */
Int& Int::operator=(const Int& rhs) {
    while (!this->_num.empty()) this->_num.removeFront();
    int n = rhs.value();
    if (n < 0)
        throw (std::range_error("No support for negative numbers...!"));
    do {
        this->_num.addFront(n % 10);
        n = n / 10;
    } while (n > 0);
    this->_num.reverse();
    return *this;
}

/** Return the value
 */
int Int::value() const {
    long exp = 1;
    int n = 0;
    std::shared_ptr< Node<int> > ptr = this->getHead();
    while (ptr != nullptr) {
        n += exp * ptr->value();
        exp *= 10;
        ptr = ptr->next();
    }
    // delete ptr;
    return n;
}

/** Addition operator overloading
 */
Int operator+(const Int& A, const Int& B) {
    std::shared_ptr< Node<int> > a = A.getHead();
    std::shared_ptr< Node<int> > b = B.getHead();

    std::shared_ptr< Node<int> > result = nullptr;
    std::shared_ptr< Node<int> > last = nullptr;
    int carry = 0;

    while (a != nullptr || b != nullptr || carry > 0) {
        int first = (a == nullptr ? 0 : a->value());
        int second = (b == nullptr ? 0 : b->value());

        int sum = first + second + carry;
        // cout << "DEBUG: " << first << ' ' << second << endl;
        std::shared_ptr< Node<int> > pNew = std::make_shared< Node<int> >(sum%10);
        // (new Node<int>(sum % 10));
        carry = sum / 10;

        if (result == nullptr) {
            result = pNew;
        } else {
            last->setNext(pNew);
        }

        last = pNew;

        if (a != nullptr) {
            a = a->next();
        }

        if (b != nullptr) {
            b = b->next();
        }
    }
    // This is the head of the new LinkedList:
    // return result;
    Int temp;
    temp._num.setHead(result);
    return temp;
}

/** Ostream method
 */
std::ostream& operator<<(std::ostream& os, const Int& num) {
    /*Node<int> *ptr = num.getHead();
      int counter = 1;
      int number = 0;
      while (ptr != nullptr) {
      number = counter * ptr->value();
      ptr = ptr->next();
      counter *= 10;
      }
      os << number;
      return os;*/
    os << num.value();
    return os;
}

测试.cpp:

#include <iostream>
#include <exception>

#include "LinkedList.hpp"

using namespace std;

int main() {
  LinkedList<int> list;
  cout << list << endl;
  try {
    cout << list.front() << endl;
  } catch (std::exception& e) {
    cout << "Exception caught: " << e.what() << endl;
  }

  list.addFront('a');           // Should be invalid, but works
  list.addFront(21);
  list.addFront(14);
  list.addFront(7);

  cout << "Initial list:\n";
  cout << list << endl;


  // Check iterative reversing:
  cout << "\nAfter iterative reverse:\n";
  list.reverse();
  cout << list << endl;

  // Check recursive reversing:
  cout << "\nAfter recursive reverse:\n";
  list.reverseRecursive();
  cout << list << endl;

  // Check deleting nodes:
  cout << "\nAfter deleting non-existing key:\n";
  list.deleteKey(0);
  cout << list << endl;

  cout << "\nAfter deleting head key:\n";
  list.deleteKey(list.head()->value());
  cout << list << endl;

  cout << "\nAfter deleting middle key:\n";
  list.deleteKey(list.head()->next()->value());
  cout << list << endl;

  cout << "\nAfter deleting key:\n";
  list.deleteKey(list.head()->next()->value());
  cout << list << endl;

  cout << "\nCreate an Linked List Int:\n";
  Int num(100);
  cout << num << endl;
  num = Int(200);
  cout << num << endl;

  Int a(123);
  Int b(897);
  Int c = a + b;
  cout << c << endl;

  LinkedList<int> listArb;
  listArb.addFront(21);
  listArb.addFront(14);
  listArb.addFront(7);
  listArb.head()->setArb(listArb.head()->next()->next());
  listArb.head()->next()->next()->setArb(listArb.head());
  cout << listArb << endl;

  LinkedList<int> listArbCopy = listArb.deepCopy();
  // listArbCopy.setHead(deep_copy_arbitrary_pointer(listArb.head()));

  // Change some stuff to check if the linked lists are really separate
  listArbCopy.head()->next()->setValue(123);
  listArb.head()->setValue(321);

  cout << listArbCopy << endl;
  cout << listArb << endl;

  // Check the sorting algos:
  LinkedList<int> sort;
  sort.addFront(11);
  sort.addFront(82);
  sort.addFront(23);
  sort.addFront(29);

  cout << sort << endl;
  sort.sort();
  cout << sort << endl;


  return 0;
}

Answer 1

只需将 _arb 更改为

std::weak_ptr< T >  _arb;

因为所有节点都属于 shared_ptr，所以 weak_ptr 仅指没有任何所有权的任意节点。要使用 weak_ptr，您会在打算使用它时获得它的 shared_ptr:

std::shared_ptr< T > sp( this->_arb );
return sp;

以上是您如何更改 Node 类中的“arb”函数。

注意:如果出于某种原因(这对 weak_ptr 是普遍的)_arb 一旦指向列表中其他地方的有效 shared_ptr，然后随后该节点被删除，上述函数将返回一个空的 shared_ptr 作为 weak_ptr 消失的指示.