Sign in to follow this  
lucky6969b

gnu_cxx::hash_map vs stdext::hash_map

Recommended Posts

Hello,

template<typename OBJ, class HashKey, class EqKey, class CmpKey>
class heap2 {
public:
heap2();
~heap2();
void reset();
void add(OBJ val);
void decreaseKey(OBJ val);
bool isIn(OBJ val);
OBJ remove();
void pop() { remove(); }
OBJ top() { return _elts[0]; }
OBJ find(OBJ val);
bool empty();
unsigned size() { return _elts.size(); }
// void verifyData();
private:
std::vector<OBJ> _elts;
void heapifyUp(unsigned int index);
void heapifyDown(unsigned int index);
typedef __gnu_cxx::hash_map<OBJ, unsigned int, HashKey, EqKey > IndexTable;
IndexTable table;
};



This code snippet compiles just fine under Linux.
Pay attention to __gnu_cxx::hash_map


template<typename OBJ, class HashKey, class EqKey, class CmpKey>
class heap2 {
public:
heap2();
~heap2();
void reset();
void add(OBJ val);
void decreaseKey(OBJ val);
bool isIn(OBJ val);
OBJ remove();
void pop() { remove(); }
OBJ top() { return _elts[0]; }
OBJ find(OBJ val);
bool empty();
unsigned size() { return _elts.size(); }

private:
std::vector<OBJ> _elts;
void heapifyUp(unsigned int index);
void heapifyDown(unsigned int index);
typedef stdext::hash_map<OBJ, unsigned int, HashKey, EqKey> IndexTable;
IndexTable table;
};



while this code snippet has trouble when being instantiated.


class SearchNode
{
public:
SearchNode(double _fCost=0, double _gCost=0, uint32_t curr=0, uint32_t prev=0)
: fCost(_fCost), gCost(_gCost), currNode(curr), prevNode(prev) { }

SearchNode(uint32_t curr)
: fCost(0), gCost(0), currNode(curr), prevNode(0) { }

double fCost;
double gCost;
uint32_t currNode;
uint32_t prevNode;
};

struct SearchNodeEqual {
bool operator()(const SearchNode& i1, const SearchNode &i2)
{ return i1.currNode == i2.currNode; } };

struct SearchNodeCompare {
bool operator()(const SearchNode &i1, const SearchNode &i2)
{
if (fequal(i1.fCost, i2.fCost))
{
return (fless(i1.gCost, i2.gCost));
}
return (fgreater(i1.fCost, i2.fCost));
} };

struct SearchNodeHash {
size_t operator()(const SearchNode& x) const
{ return (size_t)(x.currNode); }
};

typedef heap2<GenericAStarUtil::SearchNode, GenericAStarUtil::SearchNodeHash,
GenericAStarUtil::SearchNodeEqual, GenericAStarUtil::SearchNodeCompare> PQueue;




GenericAStarUtil::PQueue openQueue;



Error:

1>Compiling...
1>GenericAStar.cpp
1>d:\program files (x86)\microsoft visual studio 9.0\vc\include\hash_map(32) : error C2903: 'rebind' : symbol is neither a class template nor a function template
1> d:\program files (x86)\microsoft visual studio 9.0\vc\include\xhash(191) : see reference to class template instantiation 'stdext::_Hmap_traits<_Kty,_Ty,_Tr,_Alloc,_Mfl>' being compiled
1> with
1> [
1> _Kty=GenericAStarUtil::SearchNode,
1> _Ty=unsigned int,
1> _Tr=GenericAStarUtil::SearchNodeHash,
1> _Alloc=GenericAStarUtil::SearchNodeEqual,
1> _Mfl=false
1> ]
1> d:\program files (x86)\microsoft visual studio 9.0\vc\include\hash_map(88) : see reference to class template instantiation 'stdext::_Hash<_Traits>' being compiled
1> with
1> [
1> _Traits=stdext::_Hmap_traits<GenericAStarUtil::SearchNode,unsigned int,GenericAStarUtil::SearchNodeHash,GenericAStarUtil::SearchNodeEqual,false>
1> ]
1> c:\users\garfield\documents\visual studio 2008\projects\mock pathfinding\mock pathfinding\util\heap2.h(29) : see reference to class template instantiation 'stdext::hash_map<_Kty,_Ty,_Tr,_Alloc>' being compiled
1> with
1> [
1> _Kty=GenericAStarUtil::SearchNode,
1> _Ty=unsigned int,
1> _Tr=GenericAStarUtil::SearchNodeHash,
1> _Alloc=GenericAStarUtil::SearchNodeEqual
1> ]
1> c:\users\garfield\documents\visual studio 2008\projects\mock pathfinding\mock pathfinding\util\genericastar.h(88) : see reference to class template instantiation 'heap2<OBJ,HashKey,EqKey,CmpKey>' being compiled
1> with
1> [
1> OBJ=GenericAStarUtil::SearchNode,
1> HashKey=GenericAStarUtil::SearchNodeHash,
1> EqKey=GenericAStarUtil::SearchNodeEqual,
1> CmpKey=GenericAStarUtil::SearchNodeCompare
1> ]
1>d:\program files (x86)\microsoft visual studio 9.0\vc\include\hash_map(32) : error C2039: 'rebind' : is not a member of 'GenericAStarUtil::SearchNodeEqual'
1> c:\users\garfield\documents\visual studio 2008\projects\mock pathfinding\mock pathfinding\util\genericastar.h(27) : see declaration of 'GenericAStarUtil::SearchNodeEqual'


I understand that the declaration differs, but how come the Linux version compiles while the Windows version won't.
Anyone give that a fix, please?

Share this post


Link to post
Share on other sites
Given
Quote:
'rebind' : is not a member of 'GenericAStarUtil::SearchNodeEqual'


and

Quote:
d:\program files (x86)\microsoft visual studio 9.0\vc\include\hash_map(32)


have you already looked into that file?


Well, after looking into the documentation I realise you are putting SearchNodeEqual as the fourth parameter to hash_map, but the fourth parameter shall be an allocator.

My guess is you have mistaken the arguments (or maybe the template argument list from gnu differs from ms') ;)

Share this post


Link to post
Share on other sites
Quote:
Could anyone lend me hand to make an educated guess what the heck is TP?

My motivation to help you has largely increased ever since you decided to amply bypass my previous reply.

Share this post


Link to post
Share on other sites
Quote:
Original post by phresnel
Quote:
Could anyone lend me hand to make an educated guess what the heck is TP?

After you've ignored my previous post, I lost interest.


I haven't. I just tried to map the 2 containers, maybe provide some code snippet?

Share this post


Link to post
Share on other sites
Quote:
Original post by lucky6969b
Quote:
Original post by phresnel
Quote:
Could anyone lend me hand to make an educated guess what the heck is TP?

After you've ignored my previous post, I lost interest.


I haven't. I just tried to map the 2 containers, maybe provide some code snippet?


Maybe you would just reread my previous reply and try to understand what I've written:

Quote:
[...] but the fourth parameter shall be an allocator.


You could try with the default template parameters of MS' implementation and see if it works.

Anyways, never mind.

Share this post


Link to post
Share on other sites

1>Compiling...
1>GenericAStar.cpp
1>d:\program files (x86)\microsoft visual studio 9.0\vc\include\xhash(199) : error C2039: 'bucket_size' : is not a member of 'GenericAStarUtil::SearchNodeEqual'
1> c:\users\garfield\documents\visual studio 2008\projects\mock pathfinding\mock pathfinding\util\genericastar.h(27) : see declaration of 'GenericAStarUtil::SearchNodeEqual'
1> d:\program files (x86)\microsoft visual studio 9.0\vc\include\hash_map(88) : see reference to class template instantiation 'stdext::_Hash<_Traits>' being compiled
1> with
1> [
1> _Traits=stdext::_Hmap_traits<GenericAStarUtil::SearchNodeHash,GenericAStarUtil::SearchNode,GenericAStarUtil::SearchNodeEqual,std::allocator<std::pair<const GenericAStarUtil::SearchNodeHash,GenericAStarUtil::SearchNode>>,false>
1> ]
1> c:\users\garfield\documents\visual studio 2008\projects\mock pathfinding\mock pathfinding\util\heap2.h(29) : see reference to class template instantiation 'stdext::hash_map<_Kty,_Ty,_Tr>' being compiled
1> with
1> [
1> _Kty=GenericAStarUtil::SearchNodeHash,
1> _Ty=GenericAStarUtil::SearchNode,
1> _Tr=GenericAStarUtil::SearchNodeEqual
1> ]
1> c:\users\garfield\documents\visual studio 2008\projects\mock pathfinding\mock pathfinding\util\genericastar.h(89) : see reference to class template instantiation 'heap2<OBJ,HashKey,EqKey,CmpKey>' being compiled
1> with
1> [
1> OBJ=GenericAStarUtil::SearchNode,
1> HashKey=GenericAStarUtil::SearchNodeHash,
1> EqKey=GenericAStarUtil::SearchNodeEqual,
1> CmpKey=GenericAStarUtil::SearchNodeCompare
1> ]


Whoops..still having problems...
Further hints or reading recommendations?
Thanks
Jack

Share this post


Link to post
Share on other sites
The declaration of MS' hash_map looks like this:

template <
class Key,
class Type,
class Traits=hash_compare<Key, less<Key> >,
class Allocator=allocator<pair <const Key, Type> >
>
class hash_map



The ='s mean you can omit those last two parameters, in which case the compiler would use what is behind =. So, have you already tried

has_map<YourKey, YourType> foobar;


, just to get it working for a moment?

Share this post


Link to post
Share on other sites
Thanks phresnel
Its been great help!
But what if I need to add my hash function and compare function?
How can I derive the coding based on what I've got from the first post?
Note its okay to compile when I omit those parameters you mentioned.
Thanks
Jack

Share this post


Link to post
Share on other sites
Quote:
Original post by lucky6969b
Thanks phresnel

Welcome, after some initial confusion ;)



Quote:
But what if I need to add my hash function and compare function?

You write some, but that's not too trivial. You have to look what the requirements are, e.g., as you have seen, an allocator would be required to have a "rebind()" member, etc.


Quote:
How can I derive the coding based on what I've got from the first post?
Note its okay to compile when I omit those parameters you mentioned.

I'd say: Do you really need custom comparers and allocators? If not, just use the standard ones and forget about them. Allocators can be a tough topic :)

Share this post


Link to post
Share on other sites
Well, I'd say in general, since you're implementing a priority queue, your comp.
is quite important to the behavior of your heap, unless you plan to store
something very simple as a key (such as an int).

BTW, you do realize that the C++ standard library provides a priority_queue ?
its an adaptation of a vector using a heap. Don't know if its enough for you,
it supports the common operations in O(logn) time.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this