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

Btw, you are binding an lvalue reference (`D& ds` in `ts()`) to an rvalue (`DataStructure()` in `dsf()`). If the compiler accepts it, that is bad. You shouldn't do it. — Andy Prowl, Mar 06 '13 at 15:26
Note in general taking pointers to C++ library member functions is not portable, since library implementations are allowed to add additional parameters with default arguments. — aschepler, Mar 06 '13 at 19:50

Daniel Frey · Accepted Answer · 2013-03-06T19:23:26.130

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.

I added a full solution with your suggestion, at least as I understood it, doesn't work. The error is given in Nawaz' answer. — primfaktor, Mar 06 '13 at 17:20
Thanks, I knew about *c*, should have put a comment there. But I never got that far. — primfaktor, Mar 07 '13 at 07:41

score 2 · Answer 2 · edited May 23 '17 at 12:21

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.

edited May 23 '17 at 12:21

Community

1
1

answered Mar 06 '13 at 15:24

Nawaz

353,942
115
666
851

Good point with `mem_fn`, but it seems, my STL doesn't have that one, yet. – primfaktor Mar 06 '13 at 17:13
@primfaktor: which version of which compiler are you using? If you using GCC, try compiling your code with `-std=c++11` (or `-std=c++0x`) option. – Nawaz Mar 06 '13 at 17:15
Tried your and the solution of Daniel. Got neither working. Clang (in this case) always complains about “address of overloaded function 'top'” not being staticly castable. – primfaktor Mar 06 '13 at 17:16
Yes, I'm using `-std=c++11`. – primfaktor Mar 06 '13 at 17:17
@primfaktor: In your edited post, you're doing two different things in `#ifdef` and `#else` part. In one, you're passing `DataStructure()` (which is temporary object), and in the other you're passing `ds`. Treat the same branch in the same way, except the last argument. – Nawaz Mar 06 '13 at 17:22
That's right, I do. I like the temporary object more—especially when thinking about rvalue references—but int the `#else` case I have no other choice but to create it beforehand. Because I need to be able to capture it. – primfaktor Mar 06 '13 at 18:27
But of course I could have a non-temporary instance on both cases. But it doesn't make a difference wrt. the error. – primfaktor Mar 06 '13 at 18:59
@primfaktor: In that case, you should post the error, indicating the line numbers the source code. – Nawaz Mar 06 '13 at 19:00
@primfaktor: You did some blunder in your code. I fixed all. See my edited answer. I also demonstrated the alternative syntax, and approaches. – Nawaz Mar 06 '13 at 19:43
Thanks, the 2nd is was I was shooting for. I knew that I would have to change the call to *getter* somehow, but I didn't get that far. But some weird syntax in the 3rd. <:-| I'm going to accept Daniel's answer as it is equally good but both first answer and enlightening edit were earlier. Thank you anyway! – primfaktor Mar 07 '13 at 08:05

How can I solve this ambiguousity wrt. mem_fun?

2 Answers2