Comment puis-je résoudre cette ambiguïté par rapport à. mem_fun?

Question

Pour m'entraîner, l'un des sujets que je me familiarise à nouveau est celui des arbres. La chose à propos de la recherche en profondeur d'abord et de la recherche en largeur d'abord, c'est qu'ils ne diffèrent que par le choix de la structure de données qui soutient l'algorithme. J'ai pensé que je pourrais écrire une recherche commune d'arbre que je nourrirais une pile (DFS) ou une file d'attente (BFS) en utilisant des calibres. stack et queue sont assez gentils que leurs membres d'ajout et de suppression ont le même nom. Malheureusement, la fonction d'accès est une fois appelée top et front pour l'autre. Pour cette raison, je ne suis pas tout à fait arrivé là où je voulais. Je ne l'ai pas réussi à le faire sans que lambda:

template<typename T, typename D, typename G> 
bool ts(Tree<T> const & tree, T const value, D & ds, G getter) 
{ 
    if (empty(tree)) 
    { 
     return false; 
    } 

    ds.push(tree.Root); 
    while (!ds.empty()) 
    { 
     auto const current = getter(); 
     ds.pop(); 

     if (current->Value == value) 
     { 
      return true; 
     } 
     if (current->Left) 
     { 
      ds.push(current->Left); 
     } 
     if (current->Right) 
     { 
      ds.push(current->Right); 
     } 
    } 
    return false; 
} 

template<typename T> 
bool dfs(Tree<T> const & tree, T const value) 
{ 
    stack<typename Tree<T>::Node const * const> ds; 
    return ts(tree, value, ds, [&ds](){ return ds.top(); }); 
} 

template<typename T> 
bool bfs(Tree<T> const & tree, T const value) 
{ 
    queue<typename Tree<T>::Node const * const> ds; 
    return ts(tree, value, ds, [&ds](){ return ds.front(); }); 
} 

Je pensais que je devrais pouvoir utiliser mem_fun (ou mem_fun_ref) pour assurer la fonction d'accès respectif. J'ai essayé

template<typename T> 
bool dfs(Tree<T> const & tree, T const value) 
{ 
    typedef stack<typename Tree<T>::Node const * const> DataStructure; 
    return ts(tree, value, DataStructure(), mem_fun(&DataStructure::top)); 
} 

Mais le compilateur se plaint ambiguousity (entre un const et une version non const).

J'ai donc cherché les internets et appris que je devrais fournir le type de modèle explicitement.

template<typename T> 
bool dfs(Tree<T> const & tree, T const value) 
{ 
    typedef stack<typename Tree<T>::Node const * const> DataStructure; 
    return ts(tree, value, DataStructure(), mem_fun</*???*/>(&DataStructure::top)); 
} 

Malheureusement, aucune des nombreuses possibilités pour ??? que je pourrais trouver satisfait le compilateur.

Quelqu'un peut-il me donner un indice?

---

Mise à jour: Voici un exemple de travail complet (sauf si vous définissez NO_LAMBDA):

#include <iostream> 
#include <stack> 
#include <functional> 

using namespace std; 

template<typename T> 
struct Tree 
{ 
    struct Node 
    { 
     T Value; 
     Node * Left; 
     Node * Right; 

     Node(T value) : Value(value), Left(nullptr), Right(nullptr) {} 

     virtual ~Node() 
     { 
      if (Left) delete Left; 
      if (Right) delete Right; 
     } 
    }; 

    Node * Root; 

    Tree() : Root(nullptr) {} 

    virtual ~Tree() { if (Root) delete Root; } 
}; 

template<typename T> void insert(typename Tree<T>::Node * node, T const & value) 
{ 
    typename Tree<T>::Node ** selected = &(value < node->Value ? node->Left : node->Right); 

    if (*selected) 
     insert(*selected, value); 
    else 
     *selected = new typename Tree<T>::Node(value); 
} 

template<typename T> void insert(Tree<T> & tree, T value) 
{ 
    if (!tree.Root) 
     tree.Root = new typename Tree<T>::Node(value); 
    else 
     insert(tree.Root, value); 
} 

template<typename T, typename D, typename G> 
bool ts(Tree<T> const & tree, T const value, D & ds, G getter) 
{ 
    if (!tree.Root) return false; 

    ds.push(tree.Root); 
    while (!ds.empty()) 
    { 
     auto const current = getter(); 
     ds.pop(); 

     if (current->Value == value) return true; 

     if (current->Left) ds.push(current->Left); 
     if (current->Right) ds.push(current->Right); 
    } 
    return false; 
} 

template<typename T> 
bool dfs(Tree<T> const & tree, T const value) 
{ 
    typedef typename Tree<T>::Node const * DataStructureContent; 
    typedef stack<DataStructureContent> DataStructure; 
#ifdef NO_LAMBDA // With this defined, it breaks. 
    return ts(tree, value, DataStructure(), 
     mem_fun(static_cast<DataStructureContent (DataStructure::*)() const>(&DataStructure::top))); 
#else // This works. 
    DataStructure ds; 
    return ts(tree, value, ds, [&ds]() { return ds.top(); }); 
#endif 
} 

int main() 
{ 
    Tree<int> tree; 
    insert(tree, 5); 
    insert(tree, 2); insert(tree, 1); insert(tree, 3); 
    insert(tree, 7); insert(tree, 6); insert(tree, 9); 
    cout << "DFS(7) -> " << dfs(tree, 7) << endl; 
    cout << "DFS(8) -> " << dfs(tree, 8) << endl; 
    return 0; 
} 

Answer 1

Vous pouvez lancer le pointeur de fonction membre du type dont vous avez besoin:

mem_fun(static_cast< R (DataStructure::*)(Args...) >(&DataStructure::top)) 

ou

mem_fun(static_cast< R (DataStructure::*)(Args...) const >(&DataStructure::top)) 

avec R approprié pour le type de résultat et Args... pour les arguments.

EDIT: Vous avez fait deux (trois) erreurs dans votre exemple complet:

a) Le casting a besoin pour être exact, c'est que vous devez fournir le type de retour correct. Heureusement, std::stack a typedefs pour vous aider avec cela. Dans votre cas, vous pouvez lancer avec ces deux options:

typedef typename DataStructure::reference (DataStructure::*non_const_top)(); 
mem_fun(static_cast<non_const_top>(&DataStructure::top)) 

ou

typedef typename DataStructure::const_reference (DataStructure::*const_top)() const; 
mem_fun(static_cast<const_top>(&DataStructure::top)) 

b) Vous avez essayé de lier temporaire à une référence lors de l'appel ts.Ensemble avec a), changer le code:

DataStructure ds; 
typedef typename DataStructure::reference (DataStructure::*non_const_top)(); 
return ts(tree, value, ds, mem_fun(static_cast<non_const_top>(&DataStructure::top))); 

c) Dans ts, vous essayez d'appeler l'getter sans objet. Vous devez le changer pour:

auto const current = getter(&ds); 

Avec ces changements, le code fonctionne pour moi.

Answer 2

Define quelques typedefs comme:

typedef typename DataStructure::reference  reference; 
typedef typename DataStructure::const_reference const_reference; 

typedef reference (DataStructure::*top_type)();    //non-const version 
typedef const_reference (DataStructure::*ctop_type)() const;//const version 

puis utilisez tout ce que vous avez besoin.

Dans le code affiché, vous devez utiliser la version const, donc écrire ceci:

mem_fun(static_cast<ctop_type>(&DataStructure::top)) 

Le casting aide compilateur de choisir la version que vous souhaitez utiliser. A propos, en C++ 11, std::mem_fun est déconseillé. Et il a ajouté une autre fonction appelée std::mem_fn. Notez la différence dans l'orthographe. Voir ce sujet pour plus de détails:

• std::mem_fun vs std::mem_fn

---

Qu'est-ce que vous avez besoin est appelé std::bind, non std::mem_fun (ou std::mem_fn):

Il travaille maintenant:

• Online Demo

La façon dont vous vous appelez getter suggère que vous avez besoin std::bind parce que vous êtes invoquer getter comme ceci:

auto const current = getter(); 

C'est une erreur si getter est un objet retourné de std::mem_fun, auquel cas il devrait être appelé comme ceci:

auto const current = getter(&ds); 

Voir cette démo:

• Online Demo

Ou si vous passez simplement le pointeur à membre, vous invoquez comme:

auto const current = (ds.*getter)(); 

Voir: Online Demo

Comparez tous les trois. Voyez les différences!

Espérons que ça aide.