c ++, универсальная рекурсивная шаблонная функция для обхода древовидных структур - PullRequest
Новая
       46

c ++, универсальная рекурсивная шаблонная функция для обхода древовидных структур

0 голосов
/ 31 января 2019

Я попытался пройти древовидные структуры с помощью универсальной рекурсивной функции, не определяя рекурсивную функцию в глобальном масштабе каждый раз для каждой структуры. 

//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;
},
[&](...)
{
});

Здесь есть серьезная проблема.

Я должен указать тип объекта и его контейнер, потому что здесь лямбда-выражение определено в рекурсивной форме.

Может ли макрос выводить тип, такой как функция шаблона?или, может быть, я должен достичь этого по-другому?

Ответы [ 3 ]

0 голосов
/ 31 января 2019

Не полный ответ, но некоторые наполовину сформированные мысли.

Я не верю, что вам абсолютно необходим макрос здесь.Даже если интерфейс не совсем возможен, это должно быть возможно путем передачи указателей на члены и соответствующих функций.Вам, вероятно, также понадобится некоторая специализация шаблона для определения ->* против .*, но я пока не думал, что это так.

В качестве быстрого подтверждения концепции просто сделавнайти "бит вашей функции: 

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 это то, что вы ищете.Вы можете решить, что макрос в любом случае более гибок / соответствует вашим потребностям, но я просто хотел получить это там.

0 голосов
/ 31 января 2019

Только не пишите универсальный макрос вообще.Это действительно сложный макрос, который действительно трудно понять и использовать.Он также проходит через std::function, поэтому он добавляет много накладных расходов в качестве дополнительного бонуса?Это просто неправильный подход, и вы не получите от него особой пользы.

По сути, вам просто нужна рекурсивная лямбда.Лямбда не может быть напрямую рекурсивной в 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> принимает некоторую функцию, котораяВызывается на 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);
        }            
    });
};

Полная реализация Y-Combinator в C ++ 14 будет выглядеть так: 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));
}
0 голосов
/ 31 января 2019

Здесь есть серьезная проблема.

Я должен указать тип объекта и его контейнер, потому что здесь лямбда-выражение определено в рекурсивной форме.

Может макросвыводить тип, такой как функция шаблона?

Вы уверены, что макрос необходим?

Не лучше ли функция шаблона и некоторые методы с фиксированными именами в классах (своего родаинтерфейс)?

В любом случае, если я правильно понимаю ваш макрос, вместо 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);\
    }\
}
...