基于指定格式数组创建C++ shared_ptr链表的正确方法及内存问题解决

Problem Description #

I need to correctly create a C++ linked list using shared_ptr based on a specific array format. The node type is defined as:

template<typename T> struct ListNode {
public:
    T data;
    shared_ptr<ListNode<T>> next;
    ListNode() { }
    ListNode(T data, shared_ptr<ListNode<T>> next) {
        this->data = data;
        this->next = next;
    }
};

The array follows the structure [value1, index1, value2, index2, ... , valueN], where even positions (0-based) hold node values, and the immediately following odd positions hold the relative index of the next node in the array. For example, the array [1,1,2,2,3,1] should create a circular linked list like:
node(val=1,idx=0) -> node(val=2,idx=1) -> node(val=3,idx=2) -> node(val=2,idx=1) -> ...

My current implementation has memory issues (likely circular reference causing memory leaks):

shared_ptr<ListNode<int>> convert(vector<int> value) {
    vector<shared_ptr<ListNode<int>>> nodes;
    for (int i = 0; i < value.size(); i += 2) {
        shared_ptr<ListNode<int>> node = make_shared<ListNode<int>>();
        node->data = value[i];
        nodes.push_back(node);
    }
    for (int i = 1; i < value.size(); i += 2) {
        shared_ptr<ListNode<int>> node = nodes[floor((i - 1) / 2)];
        int nextIndex = value[i];
        if (nextIndex >= 0) {
            shared_ptr<ListNode<int>> nextNode = nodes[nextIndex];
            node->next = nextNode;
        }
    }
    return nodes.empty() ? nullptr : nodes[0];
}

When I call this function, I encounter memory problems. Could you provide a correct implementation?

Solution #

The root cause of your memory issues is circular references created by using shared_ptr for the next pointer in cycles. shared_ptr uses reference counting to manage memory—if nodes form a cycle (like your example where node1 points to node2, which points back to node1), their reference counts never drop to zero, leading to permanent memory leaks.

Here's the fixed implementation, which uses weak_ptr to break these cycles while maintaining the required list structure:

Step 1: Update the ListNode Structure #

First, modify the next member to be a weak_ptr instead of shared_ptr. This prevents the reference count from being incremented for the next node, breaking the cycle:

template<typename T> struct ListNode {
public:
    T data;
    weak_ptr<ListNode<T>> next; // Swap shared_ptr for weak_ptr
    ListNode() { }
    ListNode(T data, shared_ptr<ListNode<T>> next) {
        this->data = data;
        this->next = next; // weak_ptr can be assigned directly from shared_ptr
    }
};

Step 2: Fixed Conversion Function #

Adjust the conversion code to work with weak_ptr, and add small improvements like bounds checking and cleaner integer division:

shared_ptr<ListNode<int>> convert(vector<int> value) {
    vector<shared_ptr<ListNode<int>>> nodes;
    
    // First pass: create all nodes and store them
    for (size_t i = 0; i < value.size(); i += 2) {
        auto node = make_shared<ListNode<int>>();
        node->data = value[i];
        nodes.push_back(node);
    }

    // Second pass: link nodes using weak_ptr
    for (size_t i = 1; i < value.size(); i += 2) {
        size_t node_idx = (i - 1) / 2; // No need for floor()—integer division works here
        auto current_node = nodes[node_idx];
        int next_idx = value[i];

        // Ensure next index is valid to avoid out-of-bounds access
        if (next_idx >= 0 && static_cast<size_t>(next_idx) < nodes.size()) {
            current_node->next = nodes[next_idx];
        }
    }

    return nodes.empty() ? nullptr : nodes[0];
}

How to Use the Next Node #

When accessing the next node in the list, you need to lock() the weak_ptr to get a valid shared_ptr (this also checks if the node is still alive):

auto head = convert({1,1,2,2,3,1});
auto current = head;
for (int i = 0; i < 5; ++i) {
    cout << current->data << " ";
    if (auto next_node = current->next.lock()) {
        current = next_node;
    } else {
        break; // Next node no longer exists
    }
}
// Output: 1 2 3 2 2

Key Improvements #

• Cycle safety: weak_ptr breaks circular references, allowing nodes to be properly destroyed when no external shared_ptr references exist.
• Bounds checking: Prevents crashes from invalid nextIndex values.
• Cleaner code: Removed redundant floor() call since integer division handles the index calculation correctly.

If modifying the ListNode structure isn't an option (e.g., it's part of a fixed API), manual cycle management is possible but far more error-prone. Using weak_ptr is the standard, safe approach for this scenario.

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