Range based for loop does not check all elements in vector of structs-CodePudding

I am trying to implement a tree for a file system, each node having a name, a size, a type (file or directory, and a parent node (supernode) and a child node (subnode), the node type is defined so in this struct:

struct Node {
    std::string name;
    std::string type;
    int size;

    std::vector<std::shared_ptr<Node>> subnodes;
    std::weak_ptr<Node> supernode;
};

And then initialised using this function:

auto add_node(std::string a_name, std::string a_type, int a_size, std::weak_ptr<Node> a_supernode) -> std::shared_ptr<Node> {
    
    Node temporary_node;
    
    temporary_node.name = a_name;
    temporary_node.type = a_type;
    temporary_node.size = a_size;
    temporary_node.supernode = a_supernode;

    return std::make_shared<Node> ( temporary_node );
}

I have a find() function to traverse the tree and find a specific node, once found, it returns the node:

auto find(const Node& node, std::string target) -> std::shared_ptr<Node> {
    auto identifier = std::make_shared<Node> (Node {});
    for (const auto& itr : node.subnodes) {
            if(itr -> name == target) {
                identifier = itr;
                break;
            } else {
                find(*itr, target);
            }
    }
    return identifier;
}

Then in main, I have a root node called 'tree' and then I create nodes to resemble a file system:

auto main() -> int {
    auto tree = std::make_shared<Node> ( Node { "/" });
    tree -> type = "root";

    auto current_node = tree;

    std::shared_ptr<Node> new_node = add_node("FOLDER_A", "directory", 0, current_node);
    current_node -> subnodes.push_back(new_node);

    std::shared_ptr<Node> new_node1 = add_node("FOLDER_B", "directory", 0, current_node);
    current_node -> subnodes.push_back(new_node1);

    current_node = find(*tree, "FOLDER_A");

    std::shared_ptr<Node> new_node2 = add_node("FOLDER_C", "directory", 0, current_node);
    current_node -> subnodes.push_back(new_node2);

    std::shared_ptr<Node> new_node3 = add_node("FOLDER_D", "directory", 0, current_node);
    current_node -> subnodes.push_back(new_node3);

    current_node = find(*tree, "FOLDER_D");

    return 0;
}

The nodes initialise just fine, but the problem is with the second time the find() function is called, where it will not iterate over all the subnodes, and skips straight to the return statement and returns an empty node. This is wierd, because the first find() call works just find and does change current_node to 'FOLDER_A'.

I would expect for the find() function to iterate over all the nodes, and find the node which is clearly there and return it, but for some reason the for loop does not go all the way the second time find() is called, and as a result the current_node is not changed to FOLDER_D. Is there perhaps an issue with my pointers here?

Edit:

#include <vector>
#include <string>
#include <memory>
#include <iostream>
#include <fstream>
#include <functional>

CodePudding user response：

Recursive functions work exactly like non-recursive functions.
In particular, local variables are local to a function call, and functions return to their immediate caller.

You never use the result from the recursion, so it's just discarded.

I would expect the function to return an empty shared_ptr on failure, and look something like this:

auto find(const Node& node, const std::string& target) -> std::shared_ptr<Node> {
    for (const auto& itr : node.subnodes) {
        if (itr->name == target) {
            return itr;
        } else {
            auto result = find(*itr, target);
            if (result)
            {
                return result;
            }
        }
    }
    return nullptr;
}

CodePudding user response：

Result of the recursive call to find(*itr, target); is not propagated up. Must set the return value with the result:

identifier = find(*itr, target);
if (identifier->name == target)
    break;