5

我尝试使用通用递归函数遍历树状结构，而无需每次为每个结构在全局中定义递归函数。

//structure #1
class CA
{
public:
    std::string name;
    std::vector<CA*> vecChild;
};

我用 CA 创建了一棵树

auto root = new CA;
root->name = "root";
root->push_back(new CA);
auto& childA = root->back();
childA->name = "childA";
root->push_back(new CA);
auto& childB = root->back();
childB->name = "childB";
...

我可以使用这个宏来遍历这个结构，这可以与其他树状结构一起使用。

#define Combinator(obj, combinatorObjToContainer, containerNameOfObj, invokingGetCount, combinatorContainerToIndexingItem, TAnyObject, TAnyContainer, argEnterFunc, argLeaveFunc)\
{\
    std::function<void(TAnyObject, TAnyContainer)> RecursFunc = [&](auto& argObj, auto& argContainer)\
    {\
        argEnterFunc(argObj, argContainer);\
        for(size_t idx=0; idx<argObj combinatorObjToContainer containerNameOfObj invokingGetCount; ++idx)\
        {\
            RecursFunc(argObj, argObj combinatorObjToContainer containerNameOfObj combinatorContainerToIndexingItem [idx]);\
        }\
        argLeaveFunc(argObj, argContainer);\
    }\
}

很难阅读，但效果很好，我像这样遍历 CA 的根

Combinator(root, ->, vecChild, .size(), , CA*, std::vector<CA*>&, 
[&](auto& item, auto& vec)
{
    std::cout << item.name << std::endl;
},
[&](...)
{
});

与其他结构一起使用，像这样

struct MyData;
struct MyList
{
    int count;
    MyData* pItem;
};
struct MyData
{
    char* name;
    MyList* pLstChild;
};

遍历 MyData 的根

Combinator(root, ->, pLstChild, ->count, ->pItem, MyData*, MyList*, 
[&](auto& pItem, auto& pLst)
{
    std::cout << pItem->name << std::endl;
},
[&](...)
{
});

这里有一个大问题。

我必须指定对象及其容器的类型，因为这里的 lambda 表达式是以递归形式定义的。

宏可以像模板函数一样推断类型吗？或者我应该以其他方式实现这一目标？

4

3 回答 3

1

根本不要编写通用宏。这是一个非常复杂的宏，很难理解和使用。它也通过了std::function，所以它增加了很多开销作为额外的奖励？这完全是错误的方法，您不会从中获得太多价值。

基本上，您只需要一个递归 lambda。Lambdas 还不能在 C++ 中直接递归，但你可以使用称为 Y-Combinator 的东西来完成工作：

auto print_names = y_combinator([](auto self, CA const& item) {
    std::cout << item.name << std::endl;
    for (CA* ca : item.vecChild) {
        self(*ca);
    }
});

你可以用一个变量模板来概括它（它实际上不必是一个变量模板，你可以recurse为每种类型编写一个不同的函数——这只是给所有的东西赋予相同的名称）：

// variable template to handle all all tree recursions
template <typename TreeLike>
auto recurse = 0;

template <>
auto recurse<CA> = [](auto f){
    return y_combinator([=](auto self, auto&& ca){
        f(ca);
        for (auto child : ca.vecChild) {
            self(*child);
        }
    });
};

recurse<CA>接受一些可在 a 上调​​用CA的函数，并返回一个在 的树上递归调用它的函数CA。

这让你写：

auto print_names = recurse<CA>([](CA const& item){
    std::cout << item.name << std::endl;
});

这种方法可以让你为你的其他结构写同样的东西——在普通代码中：

template <>
auto recurse<MyList> = [](auto f){
    return y_combinator([=](auto self, auto* list){
        for (int i = 0; i < list->count; ++i) {
            f(list->pItem[i]);
            self(list->pitem[i].pLstChild);
        }            
    });
};

C++14 中 Y-Combinator 的完整实现将是，从P0200

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
于 2019-01-31T15:07:48.790 回答
1

不是一个完整的答案，而是一些半成品的想法。

我不相信你在这里绝对需要一个宏。即使接口不是绝对可能的，也应该通过传递指向成员的指针和适当的函数来实现。您可能还需要一些模板专业化来确定->*vs. .*，但我还没有想到那么远。

作为一个快速的概念验证，只需执行您的功能的“尺寸查找”位：

template <typename Obj, typename ContainerMemPtr, typename SizeFunc>
void recurseFunc(Obj&& obj, ContainerMemPtr container, SizeFunc func) {
    for (unsigned i = 0; i < func(obj.*container); i++)
        std::cout << i << std::endl;; // fill out this section
}

// ...

CA ca = // ...
recurseFunc(ca, &CA::vecChild, [](const auto& vec){ return vec.size(); });

MyData* data = // ...
recurseFunc(*data, &MyData::pLstChild, [](const auto& list) { return list->count; });

http://coliru.stacked-crooked.com/a/2fd33500e52e5fe7

但是，我意识到我已经回避了您的实际问题。为此，我相信这decltype就是您正在寻找的。无论如何，您可能会决定宏更灵活/更适合您的需求，但我只是想把它放在那里。

于 2019-01-31T03:14:54.990 回答
0

这里有一个大问题。

我必须指定对象及其容器的类型，因为这里的 lambda 表达式是以递归形式定义的。

宏可以像模板函数一样推断类型吗？

你确定宏是必要的吗？

在类（一种接口）中使用模板函数和一些具有固定名称的方法不是更好吗？

无论如何，如果我正确理解你的宏，TAnyObject你可以使用decltype(obj)而不是TAnyContainer你可以使用decltype(containerNameOfObj)

所以有些事（对不起：代码未经测试）

#define Combinator(obj, combinatorObjToContainer, containerNameOfObj, invokingGetCount, combinatorContainerToIndexingItem, argEnterFunc, argLeaveFunc)\
{\
    std::function<void(decltype(obj), decltype(containerNameOfObj))> RecursFunc = [&](auto& argObj, auto& argContainer)\
    {\
        argEnterFunc(argObj, argContainer);\
        for(size_t idx=0; idx<argObj combinatorObjToContainer containerNameOfObj invokingGetCount; ++idx)\
        {\
            RecursFunc(argObj, argObj combinatorObjToContainer containerNameOfObj combinatorContainerToIndexingItem [idx]);\
        }\
        argLeaveFunc(argObj, argContainer);\
    }\
}
于 2019-01-31T02:43:26.537 回答