How can I solve this ambiguousity wrt. mem_fun?

Question

To practice, one of the topics I'm familiarizing myself with again is trees. The thing about depth-first search and breadth-first search is that they differ only in the choice of the data structure that backs the algorithm.

I thought I could write a common tree search that I would feed either a stack (DFS) or a queue (BFS) using templates. stack and queue are nice enough that their adding and removing members have the same name. Unfortunately, the access function is once called top and front for the other. Because of this I did no quite arrive where I wanted. I didn't manage to do it without that 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(); });
}

I though that I should be able to use mem_fun (or mem_fun_ref) to provide the respective access function. I tried

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

But then the compiler complains about ambiguousity (between a const and a non-const version).

So I searched the internets and learned that I should provide the template type explicitly.

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

Sadly, none of the many possibilities for ??? that I could come up with satisfied the compiler.

Can someone give me a hint?

---

Update: Here a full working example (except if you define 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

You could cast the member function pointer to the type you need:

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

or

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

with appropriate R for the result type and Args... for the arguments.

EDIT: You made two (three) mistakes in your complete example:

a) The cast needs to be exact, that is you need to provide the correct return type. Luckily, std::stack has typedefs to help you with that. In your case, you can cast with these two options:

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

or

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

b) You tried to bind a temporary to a reference when calling ts. Together with a), change the code to:

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) In ts, you try to call the getter without an object. You need to change it to:

auto const current = getter( &ds );

With these changes, the code works for me.

Answer 2

Define few typedefs as:

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

then use whatever you need it.

In the posted code, you need const version, so write this:

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

The casting helps compiler to choose the version you intend to use.

By the way, in C++11, std::mem_fun is deprecated. And it has added another function called std::mem_fn. Notice the difference in the spelling. See this topic for details:

• std::mem_fun vs std::mem_fn

---

What you need is called std::bind, not std::mem_fun (or std::mem_fn) :

It works now:

• Online Demo

The way you're calling getter suggests that you need std::bind because you're invoking getter like this:

auto const current = getter();

That is an error if getter is an object returned from std::mem_fun, in which case it should be invoked like this:

auto const current = getter(&ds);

See this demo:

• Online Demo

Or if you simply pass the pointer-to-member, then you invoke as:

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

See : Online Demo

Compare all three. See the differences!

Hope that helps.