Tree traversal using std::for_each

Question

I am fairly new to using algorithm and functional in C++. I need to do tree traversal and perform a function for each element. See the code below.

This works but a I have few things I don't like and perhaps can do better. Note that I am limited to a fairly old version of g++ (4.4.7) and cannot use lambda functions.

1. I use a wrapper function do_walk and std::bind to call the member function walk on each element. Is there a way to avoid the wrapper function and directly call the member function?

2. I use a typedef for the callback function UnaryFunction. I would prefer to use a templated version of walk. However, when I change the code to use a template I get the following compilation error: error: no matching function for call to 'bind(<unresolved overloaded function type>, std::_Placeholder<1>&, void (*&)(const Elem&))'. Is it possible to use templates in this context?

3. Perhaps there is an alternative to std::for_each that is better suited for this kind of tree traversal?

My code so far:

#include <list>
#include <algorithm>
#include <functional>

struct Elem;
typedef void (*UnaryFunction)(const Elem&); // (2)

struct Elem
{
    std::list<Elem> children; // Some container, std::list for now.

    //template< class UnaryFunction > // (2)
    void walk(UnaryFunction f) const
    {
        // Walk all children.
        std::for_each(
            children.begin(),
            children.end(),
            std::bind(do_walk, std::placeholders::_1, f)); // (1)

        // Walk this object.
        f(*this);
    }

    //template< class UnaryFunction > // (2)
    static void do_walk(const Elem& elem, UnaryFunction f) // (1)
    {
        elem.walk(f);
    }
};

void pretty_print(const Elem& elem)
{
    // Pretty print element.
}

int main()
{
    Elem root;
    // Create tree somehow.
    root.walk(pretty_print);
    return 0;
}

Answer 1

You can use std::function instead to solve problem with template walk. Let's sumarryze:

I use a wrapper function do_walk and std::bind to call the member function walk on each element. Is there a way to avoid the wrapper function and directly call the member function?

Yes. Use std::function

I use a typedef for the callback function UnaryFunction. I would prefer to use a templated version of walk. However, when I change the code to use a template I get the following compilation error: error: no matching function for call to 'bind(, std::_Placeholder<1>&, void (*&)(const Elem&))'. Is it possible to use templates in this context?

Yes. Use std::function + variadic templates

Perhaps there is an alternative to std::for_each that is better suited for this kind of tree traversal?

I think std::for_each is OK for this purpose

#include <list>
#include <algorithm>
#include <functional>


struct Elem
{
   std::list<Elem> children; // Some container, std::list for now.

                          //template< class UnaryFunction > // (2)
   template<typename ...TArgs>
   void walk( std::function<TArgs...> f ) const
   {
       // Walk all children.
       std::for_each(
           children.begin(),
           children.end(),
           f ); // (1) NO WRAPPER
   }
};

void pretty_print( const Elem& elem )
{
    // Pretty print element.
}

int main()
{
   Elem root;
   Elem root1;
   root.children.push_back( root1 );

   // Create tree somehow.
   root.walk<void( const Elem& )>( pretty_print );
   // or root.walk<decltype( pretty_print )>( pretty_print ); if you do not 
   // want to clarify type
   return 0;
}

Answer 2

1. std::bind is capable of invoking member functions (passing the first argument to the implicit this parameter), so you can replace do_walk with this:

   std::bind(&Elem::walk, std::placeholders::_1, f)
   

2. The problem with making walk a template is that at the time of binding, it's not clear which instantiation should be used. You can disambiguate that by explicitly specifying the template argument:

   std::bind(&Elem::walk<UnaryFunction>, std::placeholders::_1, f)
   

3. I believe std::for_each is fine.

[Live example] using gcc 4.4.7