StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow can I solve this ambiguousity wrt. mem_fun?
primarykey
Id
15251124
data
AcceptedAnswerId
15251192
AnswerCount
2
ClosedDate
CommentCount
3
CommunityOwnedDate
CreationDate
2013-03-06T15:18:02.323
FavoriteCount
0
LastActivityDate
2013-03-06T19:42:09.087
LastEditDate
2013-03-06T17:11:40.167
LastEditorUserId
581002
OwnerUserId
581002
ParentId
0
PostTypeId
1
Score
0
ViewCount
138
LastEditorDisplayName
text
Body
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. <code>stack</code> and <code>queue</code> are nice enough that their adding and removing members have the same name. Unfortunately, the access function is once called <code>top</code> and <code>front</code> for the other. Because of this I did no quite arrive where I wanted. I didn't manage to do it without that lambda: <pre><code>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(); }); } </code></pre> I though that I should be able to use <code>mem_fun</code> (or <code>mem_fun_ref</code>) to provide the respective access function. I tried <pre><code>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)); } </code></pre> But then the compiler complains about ambiguousity (between a <code>const</code> and a non-<code>const</code> version). So I searched the internets and learned that I should provide the template type explicitly. <pre><code>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)); } </code></pre> Sadly, none of the many possibilities for ??? that I could come up with satisfied the compiler. Can someone give me a hint? <hr> Update: Here a full working example (except if you define NO_LAMBDA): <pre><code>#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; } </code></pre>
Tags
<c++><templates><generics><mem-fun>
Title
How can I solve this ambiguousity wrt. mem_fun?
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USprimfaktor
UserOwnerUserId
1. USprimfaktor
plurals
PostLinksPostIdRelatedPostId
1. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.