Как я могу решить эту двусмысленность в отношении. mem_fun?

Question

Как я могу решить эту двусмысленность в отношении. mem_fun?

На практике одна из тем, с которыми я снова знакомлюсь, это деревья. Особенность поиска в глубину и в ширину заключается в том, что они отличаются только выбором структуры данных, которая поддерживает алгоритм.

Я думал, что мог бы написать общий поиск по дереву, который бы я загружал либо в стек (DFS), либо в очередь (BFS), используя шаблоны. stack а также queue достаточно хороши, чтобы их добавляющие и удаляющие члены имели одинаковое имя. К сожалению, функция доступа однажды вызвана top а также front для другого. Из-за этого я не совсем приехал туда, куда хотел. Мне не удалось сделать это без этой лямбды:

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

Я думаю, что я должен быть в состоянии использовать mem_fun (или же mem_fun_ref), чтобы обеспечить соответствующую функцию доступа. Я старался

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

Но тогда компилятор жалуется на неоднозначность (между const и неconst версия).

Поэтому я искал в интернете и узнал, что должен явно указать тип шаблона.

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

К сожалению, ни одна из многих возможностей для ??? чтобы я мог придумать довольный компилятор.

Может кто-нибудь дать мне подсказку?

Обновление: вот полный рабочий пример (кроме случаев, когда вы определяете 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;
}

0

c++ templates generics mem-fun

Источник

user581002 06 мар '13 в 15:18

2 ответа

Решение

Определите несколько typedefs как:

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

затем используйте все, что вам нужно.

В размещенном коде вам нужна постоянная версия, поэтому напишите это:

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

Приведение помогает компилятору выбрать версию, которую вы собираетесь использовать.

Кстати, в C++11, std::mem_fun устарела. И он добавил еще одну функцию под названием std::mem_fn, Обратите внимание на разницу в написании. Смотрите эту тему для деталей:

std:: mem_fun vs std:: mem_fn

То, что вам нужно, называется std::bindне std::mem_fun (или же std::mem_fn):

Это работает сейчас:

Демо онлайн

То, как вы звоните getter предполагает, что вам нужно std::bind потому что вы вызываете getter как это:

auto const current = getter();

Это ошибка, если getter это объект, возвращенный из std::mem_funв этом случае он должен вызываться так:

auto const current = getter(&ds);

Смотрите это демо:

Демо онлайн

Или, если вы просто передаете указатель на член, то вы вызываете как:

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

Смотрите: Онлайн Демо

Сравните все три. Смотрите различия!

Надеюсь, это поможет.

2

Источник

user415784 06 мар '13 в 15:24

Другие вопросы по тегам c++ templates generics mem-fun

user2073257 06 мар '13 в 15:21 2013-03-06 15:21 · Accepted Answer · 2013-03-06 15:21

Вы можете привести указатель на функцию-член к нужному типу:

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

или же

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

с соответствующими R для типа результата и Args... для аргументов.

РЕДАКТИРОВАТЬ: вы сделали две (три) ошибки в вашем полном примере:

a) Приведение должно быть точным, то есть вы должны предоставить правильный тип возвращаемого значения. К счастью, std::stack есть typedefs, чтобы помочь вам с этим. В вашем случае вы можете разыграть эти две опции:

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

или же

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

б) Вы пытались привязать временную ссылку к ссылке при звонке ts, Вместе с а) измените код на:

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

в) в tsпытаешься позвонить getter без объекта. Вам нужно изменить это на:

auto const current = getter( &ds );

С этими изменениями код работает для меня.