and I have read up about the std::hash_map so I thought this might give me some benefits.
The problem I have run into is that the tutorial suggests using a point as the key so the spatial hashing can be 'sparse' instead of having a pre-defined grid structure.
But when I try to query the std::hash_map to see if a certain key already exists it gives me lots of errors along the lines of:
>c:\program files\microsoft visual studio 10.0\vc\include\xfunctional(125): error C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const Point'
1> c:\program files\microsoft visual studio 10.0\vc\include\xtree(1885) : see declaration of 'std::operator <'
1> c:\program files\microsoft visual studio 10.0\vc\include\xfunctional(124) : while compiling class template member function 'bool std::less<_Ty>::operator ()(const _Ty &,const _Ty &) const'
1> with
1> [
1> _Ty=Point
1> ]
I presume this is because Point is my own structure so it cannot perform its checks in the map. Can anyone please suggest a way around this as if I want the spatial hashing to be 'sparse' then I really need to store a point as the index and not just a single value i.e. int.
Here is my code so far if it helps, the error is coming in the InsertObjectPoint function:
struct Point
{
int x, y;
};
class HashTable
{
public:
HashTable(int argCellSize);
HashTable(int argCellSize, int argWidth, int argHeight);
~HashTable(void);
private:
int cellSize;
bool sparse;
std::hash_map<Point, std::list<BaseObject*>> table;
Ok I just got it to compile by making the key a pointer to a Point, is this wise or will it cause me numerous errors down the line somewhere???
EDIT:: Sorry, that doesnt work, the comparison does not return if the key is present because Im creating a new one so the address in memory isnt the same, me being stupid, sorry.
Ok I just got it to compile by making the key a pointer to a Point, is this wise or will it cause me numerous errors down the line somewhere???
EDIT:: Sorry, that doesnt work, the comparison does not return if the key is present because Im creating a new one so the address in memory isnt the same, me being stupid, sorry.
Thanks
I'm guessing it is related to the fact that you have no methods to compare points to each other, so ==, <, >, whatever else is probably undefined.
edit: the pointer didn't work because it tests if they are in the same memory location then, not if they are actually equal.
If you want to use a class with stdext::hash_map, you need to provide an appropriate traits class for the key type as the third template parameter. It should implement the same interface as the hash_compare class. For a point type you generally implement operator()(const Point &, const Point &) as a lexicographic comparison.
Sorry for the late reply, I've been a bit busy the past few days.
So SiCrane do you mean I have to create my own 'hash_compare' class which uses the Traits class? I'm a bit confused as to how to do this.
The MSDN gives the hash_compare as:
template<class Key, class Traits = less<Key> >
class hash_compare
{
Traits comp;
public:
const size_t bucket_size = 4;
const size_t min_buckets = 8;
hash_compare( );
hash_compare( Traits pred );
size_t operator( )( const Key& _Key ) const;
bool operator( )(
const Key& _Key1,
const Key& _Key2
) const;}
[font="arial, verdana, tahoma, sans-serif"]I'm confused as to what you mean, so I should make my own class which I use as the 3rd template parameter? [/font]
[font="arial, verdana, tahoma, sans-serif"]And should I use the () instead of < so where the current hash_compare has [/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]template<class Key, class Traits = less<Key> >[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Should I put something like:[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"]template<class Key, class Traits = ()<Key> >[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]And then make sure in point class it has a () operator which compares the two points?[/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Can you explain a bit more please?[/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Thanks.[/font][font="arial, verdana, tahoma, sans-serif"] [/font][font="arial, verdana, tahoma, sans-serif"] [/font][font="arial, verdana, tahoma, sans-serif"] [/font]
Did you add HashTable.cpp to your project?
(I've missed that step a few times myself...)
Important!
The hash comparison function needs to return "less than", not "equals".
Recommendations
Save yourself some trouble by using hash_multimap, which allows you to insert multiple elements into a key without having to maintain per-key object containers. At the very least use a hash_map of lists instead of a hash_map of pointers to lists. (Right now you have a memory leak.)
Implement Point::operator< instead of a custom hash_compare:
Point::operator<(const Point &rhs)
{
if (x < rhs.x)
return true;
else if (x > rhs.x)
return false;
if (y < rhs.y)
return true;
else if (y > rhs.y)
return false;
if (z < rhs.y)
return true;
return false;
}