C++: How to pass data from parent to child in a lambda inside a recursive function

Question

I want to iterate over a data structure and collect the paths of the elements. I'd like to do it in a way where the iteration over the structure is as generic as possible (see void WithAllMembersRecursively(..)) and the operation on the structure is inserted as an parameter.

The code below will return:

C
C::B
C::B::A

But the goal is:

C
C::B
C::A

Is there a way to design the lambda and its args to achieve the desired result?

Notes:

1. Yes, I'm aware that the reason for the continous stacking is caused by string& fullPath in the lambda. Beacause it FullPath is passed by reference.
2. Using string fullPath on the other hand will result in another wrong result because FullPath ("") is passed by value and thus every lambda call will only see the empty string:

C
B
A

3. The class and the data tree can not be modified to insert additional information.
4. The current sub-optimal solution that I settled on for my project so far has the assignment and passing of the path from parent to child in the recursive method. But that is something that I'd like to get rid off to allow others to use the recursive method in conjunction with their logic:

template<typename F, typename... Args>
void WithAllMembersRecursively(MyElement* pElement, string parentPath, const F& f, Args&&... args)
{
  string newPath = parentPath.empty() ? pElement->mName : parentPath + "::" + pElement->mName;
  f(pDOInterface, newPath, std::forward<Args>(args)...);
  for (auto pMember: pElement->mMembers)
  {
    WithAllMembersRecursively(pMember, newPath, f, std::forward<Args>(args)...);
  }
}

Code Example:

#include <iostream>
#include <vector>

using namespace std;


class MyElement
{
public:
  MyElement(string name) : mName(name) {}
  void AddElement(MyElement* elem) { mMembers.emplace_back(elem); }

  string mName;
  vector<MyElement*> mMembers;
};

template<typename F, typename... Args>
void WithAllMembersRecursively(MyElement * pElem, const F & f, Args&&... args)
{
  f(pElem, args...);
  for (auto pMember : pElem->mMembers)
  {
    WithAllMembersRecursively(pMember, f, std::forward<Args>(args)...);
  }
}

int main()
{
  MyElement C("C");
  MyElement B("B");
  MyElement A("A");
  C.AddElement(&B);
  C.AddElement(&A);

  vector<string> AllPaths;
  string FullPath = "";
  WithAllMembersRecursively(&C, [&AllPaths](MyElement* elem, string& fullPath) {

    fullPath = fullPath.empty() ? elem->mName : fullPath + "::" + elem->mName;
    AllPaths.emplace_back(fullPath);
    }, FullPath);

  for (auto e : AllPaths)
  {
    cout << e << endl;
  }

  return 0;
}

Answer 1

You need some way of popping an item from the path when the recursive traversal finishes with an item completely.

The current call to f is essentially a "pre-visit" call, then the visit happens which is the main recursive function iterating over all children and recursively visiting. If you also add a post-visit call you will have enough flexibility to pop from the running state without changing any other code.

One way to do this is to pass in another functor object to do the pop. The following will give you the output you want.

#include <iostream>
#include <vector>

using namespace std;


class MyElement
{
public:
    MyElement(string name) : mName(name) {}
    void AddElement(MyElement* elem) { mMembers.emplace_back(elem); }

    string mName;
    vector<MyElement*> mMembers;
};

template<typename C, typename F, typename... Args>
void WithAllMembersRecursively(MyElement* pElem, const C& post_visit, const F& pre_visit, Args&&... args)
{
    pre_visit(pElem, args...);
    for (auto pMember : pElem->mMembers) {
        WithAllMembersRecursively(pMember, clear, f, std::forward<Args>(args)...);
    }
    post_visit();
}

int main()
{
    MyElement mC("mC");

    MyElement mCmB("mB");
    MyElement mCmBmA("mA");
    MyElement mCmBmRevA("mrevA");

    MyElement mCmRevB("mRevB");
    MyElement mCmRevBmA("mA");
    MyElement mCmRevBmRevA("mrevA");

    mCmRevB.AddElement(&mCmRevBmA);
    mCmRevB.AddElement(&mCmRevBmRevA);

    mCmB.AddElement(&mCmBmA);
    mCmB.AddElement(&mCmBmRevA);

    mC.AddElement(&mCmB);
    mC.AddElement(&mCmRevB);

    vector<string> AllPaths;
    string FullPath = "";
    WithAllMembersRecursively(&mC, 
        [&FullPath]() {
            auto iter = FullPath.find_last_of("::");
            if (iter == FullPath.size()) {
                return;
            }
            FullPath = FullPath.substr(0, iter-1);
        },
        [&AllPaths](MyElement* elem, string& fullPath) {
            fullPath = fullPath.empty() ? elem->mName : fullPath + "::" + elem->mName;
            AllPaths.emplace_back(fullPath);
        }, 
        FullPath
    );

    for (auto e : AllPaths)
    {
        cout << e << endl;
    }

    return 0;
}