Как я могу решить эту двусмысленность в отношении. 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;
}