Il sort de ma fonction récursive trop tôt.

Version imprimable

Salut j'ai codé une fonction pour recherché un composant dans un arbre :
Code:

1 2 3 4 5 6 7 8 9 10 Node* Node::find(LightComponent* component) { std::cout<<"component : "<<this->component<<" component : "<<component<<std::endl; if (this->component == component) return this; std::cout<<"size : "<<nodes.size()<<std::endl; for (unsigned int i = 0; i < nodes.size(); i++) { return nodes[i]->find(component); } }
Mais j'ai un problème.
J'ai ajouté deux noeud au noeud racine et voilà ce que ça me fait :
-Appel de la méthode find sur le noeud racine en lui passant le composant du deuxième noeud enfant.
-Test si les composant sous les même. (non le composant du noeud racine n'est pas celui du deuxième noeud enfant.
-Entrée dans la boucle for. (size vaut deux car il y a deux noeud enfants.
-Appel récursif de find sur le premier noeuds enfant.
-Test si les composants ne sont pas les même. (non le composant du premier noeud enfant n'est pas celui du deuxième noeud enfant.
Je m'attendais à ce qu'il sorte de la fonction récursive et retourne dans la boucle for pour itérer sur le noeud suivant.
Mais ce n'est pas ce qui se passe!!!
Il sort de la boucle for et puis de la fonction en retournant null et ça plante!
Pourquoi il ne continue pas dans ma boucle for ?

10/01/2019, 17h19
Bousk

Parce que return a toujours voulu dire sortir de la fonction et jamais de continuer une boucle. :weird:

J'ai enlevé le return dans la boucle for et là il continue.
Mais la fonction me retourne null.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#0 0x8094d8c	std::vector<std::unique_ptr<odfaeg::graphic::gui::Node, std::default_delete<odfaeg::graphic::gui::Node> >, std::allocator<std::unique_ptr<odfaeg::graphic::gui::Node, std::default_delete<odfaeg::graphic::gui::Node> > > >::size(this=0x14) (/usr/include/c++/4.9/bits/stl_vector.h:655)
#1 0x8094cd7	odfaeg::graphic::gui::Node::getNodes(this=0x0) (/home/laurent/Développement/Projets-c++/ODFAEG/src/odfaeg/Graphics/GUI/node.cpp:112)
#2 0x8053e29	ODFAEGCreator::showProjectsFiles(this=0xbffff490, label=0x8e5cdb8) (/home/laurent/Développement/Projets-c++/ODFAEGCREATOR/application.cpp:194)
#3 0x8066d64	odfaeg::core::DynamicWrapper<void, ODFAEGCreator<odfaeg::graphic::gui::Label*> >::operator()<ODFAEGCreator<odfaeg::graphic::gui::Label*&> >(this=0x8e93788, o=0xbffff490) (/usr/local/include/odfaeg/Core/fastDelegate.h:309)
#4 0x8065f9e	std::_Function_handler<void (ODFAEGCreator*&, odfaeg::graphic::gui::Label*&), odfaeg::core::DynamicWrapper<void, ODFAEGCreator<odfaeg::graphic::gui::Label*> > >::_M_invoke(std::_Any_data const&, ODFAEGCreator*&, odfaeg::graphic::gui::Label*&)(__functor=..., __args#0=@0x8e937ac: 0xbffff490, __args#1=@0x8e9379c: 0x8e5cdb8) (/usr/include/c++/4.9/functional:2039)
#5 0x80697a6	std::function<void (ODFAEGCreator*&, odfaeg::graphic::gui::Label*&)>::operator()(ODFAEGCreator*&, odfaeg::graphic::gui::Label*&) const(this=0x8e9375c, __args#0=@0x8e937ac: 0xbffff490, __args#1=@0x8e9379c: 0x8e5cdb8) (/usr/include/c++/4.9/functional:2440)
#6 0x80687f3	odfaeg::core::FastDelegateImpl<void, ODFAEGCreator*, odfaeg::graphic::gui::Label*>::call<0u, 1u, void*&, void*&, void*&, void*&>(this=0x8e93758) (/usr/local/include/odfaeg/Core/fastDelegate.h:480)
#7 0x8067fd4	odfaeg::core::FastDelegateImpl<void, ODFAEGCreator*, odfaeg::graphic::gui::Label*>::operator() (this=0x8e93758, p0=0x0, p1=0x0, p2=0x0, p3=0x0) (/usr/local/include/odfaeg/Core/fastDelegate.h:449)
#8 0x80fe276	odfaeg::core::FastDelegate<void>::operator()<>() const(this=0x8de9e20) (/home/laurent/Développement/Projets-c++/ODFAEG/src/odfaeg/Core/../../../include/odfaeg/Core/fastDelegate.h:552)
#9 0x80fd7bf	odfaeg::core::Command::operator() (this=0x8de9e1c) (/home/laurent/Développement/Projets-c++/ODFAEG/src/odfaeg/Core/command.cpp:86)
#10 0x806a58e	odfaeg::core::Listener::processEvents(this=0x82c8d18) (/usr/local/include/odfaeg/Core/listener.h:126)
#11 0x806ab1d	odfaeg::core::Application::render(this=0xbffff490) (/usr/local/include/odfaeg/Core/application.h:128)
#12 0x806a8a6	odfaeg::core::Application::exec(this=0xbffff490) (/usr/local/include/odfaeg/Core/application.h:82)
#13 0x806a13c	main(argc=1, argv=0xbffff634) (/home/laurent/Développement/Projets-c++/ODFAEGCREATOR/main.cpp:7)

Pourtant c'est impossible que le pointeur this soit null dans la classe de l'objet il doit toujours pointé sur l'objet en cours.

Code:

1
2
 
Node* node = rootNode->find(label);

10/01/2019, 17h40
Luc Hermitte

Tu ne voudrais pas stocker le résultat d'appel du sous-noeud pour retourner SSI le résultat est non null plutôt ?
Et prévoir de renvoyer null si rien n'est trouvé au passage...

Code:

1
2
3
4
5
6
7
8
9
10
 
Node* Node::findNode(LightComponent* component) {
                if (this->component == component) {
                    return this;
                }
                for (unsigned int i = 0; i < nodes.size(); i++) {
                    nodes[i]->findNode(component);
                }
                return nullptr;
            }

Oui mais ce n'est pas normal que même si il le trouve la fonction me retourne null.

J'ai trouvé!

Il fallait en effet testé si le sous noeud ne renvoyait pas nullptr.
Sinon la fonction renvoyait nullptr c'est donc pour ça que ça plantait.

Code:

1
2
3
4
5
6
7
8
9
10
11
 
Node* Node::findNode(LightComponent* component) {
                if (this->component == component) {
                    return this;
                }
                for (unsigned int i = 0; i < nodes.size(); i++) {
                    if(nodes[i]->findNode(component) != nullptr)
                        return nodes[i]->findNode(component);
                }
                return nullptr;
            }

10/01/2019, 19h00
Bousk

Le double appel à une fonction récursive est un bon moyen de tuer ses perfs pour rien.

Oui ça c'est mieux.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
Node* Node::findNode(LightComponent* component) {
                if (this->component == component) {
                    return this;
                }
                for (unsigned int i = 0; i < nodes.size(); i++) {
                    Node* node;
                    if((node = nodes[i]->findNode(component)) != nullptr)
                        return node;
                }
                return nullptr;
            }

Je n'aime vraiment pas ce mélange qui ici n'apporte rien (pas une boucle) -- même le nouveau if avec déclaration du C++17, je n'y vois pas d'intérêt ici.

Code:

1
2
3
4
5
6
7
8
9
10
11
Node* Node::findNode(LightComponent* component) {
    if (this->component == component) {
        return this;
    }
    for (std::size_t i = 0; i < nodes.size(); i++) {
        Node* const node = nodes[i]->findNode(component);
        if (node)
            return node;
    }
    return nullptr;
}

Sinon, il y a <algorithm>

Code:

1
2
3
4
5
6
Node* Node::findNode(LightComponent* component) {
    if (this->component == component) {
        return this;
    }
    return std::find_if(nodes.begin(), nodes.end(), [&](Node const& n) {return n.findNode(component);});
}

14/01/2019, 13h22
Luc Hermitte

En l'état, ce n'est pas bon. find_if renvoie un itérateur, pas un pointeur qui sera nul si rien n'est trouvé.

La syntaxe avec find_if serait

Code:

1
2
auto it = std::find_if(nodes.begin(), nodes.end(), [&](Node const& n) {return n.findNode(component);});
return it != nodes.end() ? it->get() : nullptr;

14/01/2019, 14h37
Luc Hermitte

&*it, plutôt, non?
14/01/2019, 15h42
Bousk

En supposant que nodes est un std::vector<std::unique_ptr<Node>> alors l'itérateur-> est un std::unique_ptr et get retourne bien un Node*.
14/01/2019, 16h18
ternel

Alors, pour le coup, j'ai pas réfléchi à la forme de l'itéré.

Cela dit, retourner un pointeur nu est pour moi à remettre en question. Sauf si c'est une fonction privée, et que cela simplifie beaucoup de choses.
14/01/2019, 16h34
Luc Hermitte

C'est complexe. Pour du non-onwing, les C++CoreGuidelines recommandent des pointeurs bruts -- je n'ai pas dit que j'étais d'accord, il y a trop à dire.

Du coup, la généricité maximale, c'est quelque chose comme (*it)->.