C ++：如何在递归函数内的lambda中将数据从父级传递给子级

Question

我想遍历数据结构并收集元素的路径。我希望以尽可能通用的方式对结构进行迭代（参见 void WithAllMembersRecursively(..)），并将对结构的操作作为参数插入。

下面的代码将 return:

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

但目标是：

C
C::B
C::A

有没有办法设计 lambda 及其参数以达到预期的结果？

备注：

是的，我知道连续堆叠的原因是由 lambda 中的 string& fullPath 引起的。因为它 FullPath 是通过引用传递的。
另一方面，使用 string fullPath 会导致另一个错误的结果，因为 FullPath ("") 是按值传递的，因此每个 lambda 调用只会看到空字符串：

C
B
A

无法修改class和数据树以插入附加信息。
到目前为止，我为我的项目确定的当前次优解决方案是在递归方法中分配和传递从父到子的路径。但这是我想摆脱的东西，以允许其他人结合他们的逻辑使用递归方法：

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

代码示例：

#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

我认为下面的代码可以：

可变参数 args 可以简单地替换为 const string& fullPath。
f 构建到 elem 的完整路径，将其添加到 AllPaths，然后 returns 它。
WithAllMembersRecursively 调用每个 pMember 将完整路径传递给 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

Answer 2

当递归遍历完全完成一个项目时，您需要某种方式从路径中弹出一个项目。

当前对f的调用本质上是一个“pre-visit”调用，然后访问发生，这是迭代所有子项并递归访问的主要递归函数。如果您还添加一个 post-visit 调用，您将有足够的灵活性从运行状态弹出，而无需更改任何其他代码。

执行此操作的一种方法是传入另一个仿函数对象来执行弹出操作。以下将为您提供所需的输出。

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

C ++：如何在递归函数内的lambda中将数据从父级传递给子级

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

c++

recursion

lambda

parent-child

recursive-datastructures