Break an ownership cycle with weak_ptr

Use std::shared_ptr when several owners need to keep the same object alive independently. The managed object is destroyed when the last owning share is released. A lifetime determined at runtime does not itself require shared ownership: a unique_ptr can also own an object for as long as needed.

Shared pointers use bookkeeping, commonly called a control block, to track ownership. Copying an owning shared pointer adds an owner; destroying that copy removes one. Moving it transfers the existing share. Implementations commonly use atomic reference counts, but exact object sizes, instructions and costs are not fixed by the interface.

Make parameter ownership intentional

void inspect(const Widget& widget);       // borrow an existing object
void inspect(const Widget* widget);       // borrow; nullptr can mean absent
void retain(std::shared_ptr<Widget> p);   // receive an owning share

A by-value shared pointer keeps the object alive for the call and can be moved into longer-lived storage. Passing an lvalue copies a share; passing an rvalue can move it. That ownership may be useful even when the function does not keep it after returning. Use a borrowed parameter when the caller already guarantees the needed lifetime and the function needs only the object.

How an ownership cycle leaks

Suppose a parent owns a child, and the child also owns its parent:

struct Node {
    std::vector<std::shared_ptr<Node>> children;
    std::shared_ptr<Node> parent;
};

For a single parent-child pair, after external owners are released, each node still has one owner: the other node. Neither count reaches zero, so neither node is destroyed. Reference counting does not find and collect such cycles.

This tree needs ownership from parent to child. The link back to the parent is for navigation and does not need to extend the parent's lifetime.

Use a weak pointer for the parent link

std::weak_ptr observes a shared ownership group without keeping its object alive. Call lock() to obtain an owning shared pointer if the object is still alive, then check that result before using it:

std::shared_ptr<Node> parent = weak_parent.lock();
if (parent != nullptr) {
    // parent keeps the node alive while you use it
}

An empty result means the weak pointer was never assigned or its object has expired. Locking combines the lifetime check and acquisition of a share atomically. A separate expired() check cannot guarantee that a later lock will succeed. Keep the returned owner while using the object.

This protects lifetime only. If several threads modify the object's contents, they still need appropriate synchronization.

Creating shared objects

std::make_shared<T>(...) typically combines the object and control block in one allocation. When storage is combined, surviving weak pointers can keep that allocation reserved after the object is destroyed. The object's own destructor still runs when the last owning share is released; resources it owns, such as a vector's separate element buffer, can be released then.

Your task

The provided depths function builds nodes from a parent-index list and returns their depths. Fix the ownership cycle by changing the type of Node::parent_ and the body of Node::parent(). Keep the rest of the code, including depths, unchanged.

parent_of[i] identifies node i's parent. A negative or out-of-range index makes that node a root with depth zero. Valid links in the test inputs form an acyclic forest, which may have several roots. For [-1, 0, 0, 1], the depths are [0, 1, 1, 2].

Each parent must still own its children. Each child should observe its parent without owning it. parent() must return an owning pointer when the parent exists, or an empty pointer otherwise.

The harness reports the depths and Node::live after depths returns. The live count must be zero. Weak parent links break these ownership cycles; they do not make cyclic input into a valid tree.