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:

mC
mC::mB
mC::mB::mA
mC::mB::mA::mrevA
mC::mB::mA::mrevA::mRevB
mC::mB::mA::mrevA::mRevB::mA
mC::mB::mA::mrevA::mRevB::mA::mrevA

But the goal is:

mC
mC::mB
mC::mB::mA
mC::mB::mrevA
mC::mRevB
mC::mRevB::mA
mC::mRevB::mrevA

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

My current code:

#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 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, [&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;
}

CodePudding user response：

I think the code below would do:

• The variadic parameter args can simply be replaced by the const string& fullPath.
• f builds the full path to elem, adds it to AllPaths, and returns it.
• WithAllMembersRecursively calls each pMember passing the full path to pElem.

[Demo]

#include <iostream>  // cout
#include <string>
#include <vector>

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

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

template <typename F>
void WithAllMembersRecursively(MyElement* pElem, const F& f, const std::string& fullPath) {
    auto newFullPath{ f(pElem, fullPath) };  // add to AllPaths and get path to current node
    for (auto pMember : pElem->mMembers) {
        WithAllMembersRecursively(pMember, f, newFullPath);
    }
}

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);

    std::vector<std::string> AllPaths{};
    std::string FullPath{};
    WithAllMembersRecursively(
        &mC,
        [&AllPaths](MyElement* elem, const std::string& fullPath) {
            std::string ret{fullPath.empty() ? elem->mName : fullPath   "::"   elem->mName};
            AllPaths.emplace_back(ret);
            return ret;
        },
        FullPath);

    for (auto e : AllPaths) {
        std::cout << e << "\n";
    }
}

// Outputs:
//
//   mC
//   mC::mB
//   mC::mB::mA
//   mC::mB::mrevA
//   mC::mrevB
//   mC::mrevB::mA
//   mC::mrevB::mrevA

CodePudding user response：

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;
}