Boost property_tree time complexity

Question

What is the time complexity of using boost property tree's get_child_optional method? How fast or slow is it as compared to std::unordered_map lookup if we store node name and property_tree as KV pair?

No doc found for the same

Answer 1

It calls walk_path() to do most of the work, which is here

        // Recurse down the tree to find the path.
        key_type fragment = p.reduce();
        const_assoc_iterator el = find(fragment);
        if(el == not_found()) {
            // No such child.
            return 0;
        }
        // Not done yet, recurse.
        return el->second.walk_path(p);

But what about that find()? It is on a Boost Multi-Index container, and that ordered_non_unique type is documented here

So in total it is O(n log m): linear time in the number of path components n you pass to get_child_optional(), and logarithmic time in the number of children m at each step in the recursion through the path components.

How fast or slow is it as compared to std::unordered_map lookup?

You'll have to test that with your actual data to find out.