Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > How should unordered_map be used correctly ... ?

Reply
Thread Tools

How should unordered_map be used correctly ... ?

 
 
mast4as
Guest
Posts: n/a
 
      12-19-2010
In the context of what I am trying to do. I am trying to get a
technique implemented where cells are created in a linear table and
indexed using a hash key. So after making a little bit of research on
the web I decided to try to use unordered_map which I thought would
save me time from having to lean how to write my own hash table
However I can't get it to work apparently.

* I wrote this small program but when I run it it tells me that the
table size of that the end is 1?

* I am guessing I am not using it properly because the hash function
which is recommended in the paper I am trying to implement is
computing an integer while the returned value from the hash function
is a size_t type. So right there I must do something wrong already.

* Now this where I am really confused about unordered map. If the
returned type is size_t for the hash function does that mean that the
map size can not be greater than 255 ? Sorry I am sure that will sound
like an idiotic question from someone who has not understood what they
are and how they work at all. But precisely I seek some light here and
would love to hear some comments back on my questions...

For what I am trying to do (using potentially more than a few million
points positions to index an array of cell in 3D space) unordered_map
are what I need ? Or do I need to write something of my own because
they can't handle table size that big ?

Thanks a lot for your help and sorry for being confused. If you have
also good reference on hash map technique I would be very grateful (of
course I am searching on my side in the meantime).

-coralie

#include <cstdio>
#include <cmath>
#include <cstdlib>

#include <tr1/unordered_map>

typedef struct point {
float x, y, z;
};

struct hashfunc {
size_t operator() (const point &pt) const { printf("in here\n");
return 541 * pt.x + 79 * pt.y + 31 * pt.z; }
};

struct setequal {
bool operator() (const point &pa, const point &pb) const { return
(pa.x == pb.x); }
};

typedef std::tr1::unordered_map<point, int, hashfunc, setequal>
tablegrid;

float signedrand() { (drand48()-0.5)*100; }

int main (int argc, const char * argv[])
{
int dim = 128;
int gridsize = dim * dim * dim;
printf("grid size %d\n", gridsize);
tablegrid grid;
point pt;
for (int i = 0; i < gridsize; ++i) {
if (i%64==0) fprintf(stderr, "\b\b\b\b%d%c", int(100*i/
float(gridsize-1)), '%');
pt.x = signedrand(); pt.y = signedrand(); pt.z = signedrand();
grid[pt] = int(drand48() * 100);
}
printf("\nsize of table %d\n", grid.size());
return 0;
}

 
Reply With Quote
 
 
 
 
Öö Tiib
Guest
Posts: n/a
 
      12-19-2010
On Dec 19, 5:33*pm, mast4as <(E-Mail Removed)> wrote:
> In the context of what I am trying to do. I am trying to get a
> technique implemented where cells are created in a linear table and
> indexed using a hash key. So after making a little bit of research on
> the web I decided to try to use unordered_map which I thought would
> save me time from having to lean how to write my own hash table
> However I can't get it to work apparently.
>
> * I wrote this small program but when I run it it tells me that the
> table size of that the end is 1?
>
> * I am guessing I am not using it properly because the hash function
> which is recommended in the paper I am trying to implement is
> computing an integer while the returned value from the hash function
> is a size_t type. So right there I must do something wrong already.
>
> * Now this where I am really confused about unordered map. If the
> returned type is size_t for the hash function does that mean that the
> map size can not be greater than 255 ? Sorry I am sure that will sound
> like an idiotic question from someone who has not understood what they
> are and how they work at all. But precisely I seek some light here and
> would love to hear some comments back on my questions...
>
> For what I am trying to do (using potentially more than a few million
> points positions to index an array of cell in 3D space) unordered_map
> are what I need ? Or do I need to write something of my own because
> they can't handle table size that big ?
>
> Thanks a lot for your help and sorry for being confused. If you have
> also good reference on hash map technique I would be very grateful (of
> course I am searching on my side in the meantime).
>
> -coralie
>
> #include <cstdio>
> #include <cmath>
> #include <cstdlib>
>
> #include <tr1/unordered_map>
>
> typedef struct point {
> * * * * float x, y, z;
>
> };
>
> struct hashfunc {
> * * size_t operator() (const point &pt) const { printf("in here\n");
> return 541 * pt.x + 79 * pt.y + 31 * pt.z; }
>
> };
>
> struct setequal {
> * * bool operator() (const point &pa, const point &pb) const { return
> (pa.x == pb.x); }
>
> };


Seems confusing name ... "hasSameX" or something? Seems you are
written it for strange reasons.

>
> typedef std::tr1::unordered_map<point, int, hashfunc, setequal>
> tablegrid;



'point' is a key and 'int' is mapped type? Seems like it is not what
you described that you are trying to achieve.


> > float signedrand() { (drand48()-0.5)*100; }

>
> int main (int argc, const char * argv[])
> {
> * * * * int dim = 128;
> * * * * int gridsize = dim * dim * dim;
> * * * * printf("grid size %d\n", gridsize);
> * * * * tablegrid grid;
> * * * * point pt;
> * * * * for (int i = 0; i < gridsize; ++i) {
> * * * * * * * * if (i%64==0) fprintf(stderr, "\b\b\b\b%d%c", int(100*i/
> float(gridsize-1)), '%');
> * * * * * * * * pt.x = signedrand(); pt.y = signedrand(); pt.z = signedrand();
> * * * * * * * * grid[pt] = int(drand48() * 100);
> * * * * }
> * * * * printf("\nsize of table %d\n", grid.size());
> * * return 0;
>
>
>
> }

 
Reply With Quote
 
 
 
 
mast4as
Guest
Posts: n/a
 
      12-19-2010
> Seems confusing name ... "hasSameX" or something? Seems you are
> written it for strange reasons.


Sorry, I am not too sure to understand what you mean by that

> 'point' is a key and 'int' is mapped type? Seems like it is not what
> you described that you are trying to achieve.


Hum yes the mapped type is an int indeed because I was trying to see
if I could unordered_map to work before going any further. But in
reality for what I want to do it would be a pointer to a cell
structure/class ...

class Cell {...};

typedef std::tr1::unordered_map<point, Cell *, hashfunc, setequal>
tablegrid;
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      12-19-2010
On Dec 19, 6:29*pm, mast4as <(E-Mail Removed)> wrote:
> > Seems confusing name ... "hasSameX" or something? Seems you are
> > written it for strange reasons.

>
> Sorry, I am not too sure to understand what you mean by that


I meant that i am confused by that functior type name. Should it be
for checking equality of hashes? That are points? 'set' prefix is
usually used for mutator function names.

> > 'point' is a key and 'int' is mapped type? Seems like it is not what
> > you described that you are trying to achieve.

>
> Hum yes the mapped type is an int indeed because I was trying to see
> if I could unordered_map to work before going any further. But in
> reality for what I want to do it would be a pointer to a cell
> structure/class ...
>
> class Cell {...};
>
> typedef std::tr1::unordered_map<point, Cell *, hashfunc, setequal>
> tablegrid;


So that hashfunc should calculate hash (point) from a mapped type
(Cell*)? It is seemingly not what it is doing.

 
Reply With Quote
 
mast4as
Guest
Posts: n/a
 
      12-19-2010
Oops and there was a bug in my code ...

signedrand didn't return a value...

float signedrand() { return (drand48()-0.5)*100; }

With this corrected the map has a size = to the number of points
"inserted". So that's much better

grid size 2097152
size of table 2097147

How is that possible ? Considering that hash function is only
returning a value of size_t how can it be that the value is so big ? I
am confused... I would imagine that a lot of the points used in the
hash function would return the same value (and therefore I was
expected a table much smaller).

Any help ? thank you -c
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      12-19-2010
On Dec 19, 6:49*pm, Öö Tiib <(E-Mail Removed)> wrote:
>
> So that hashfunc should calculate hash (point) from a mapped type
> (Cell*)? It is seemingly not what it is doing.


No it should calculate int from key type (point).
 
Reply With Quote
 
mast4as
Guest
Posts: n/a
 
      12-19-2010
Sorry I will try to explain again what I am trying to do. I have a set
of points (particles in 3D space) and need to insert them in voxels.
Instead of creating a static 3D grid, I want to use a dynamic one. The
idea is to do something like that:

for (each point in point set)
find cell for point p (using a hash map)
if cell doesn't exist create it (insert it in hash map)
insert p in cell

so the paper recommends to use a hash map for this. What they do is
that they use this hash function

int hashfunc(const point &pt) { return 541 * pt.x + 79 * pt.y + 31 *
pt.z; }

where pt is the key indeed. The result of the function (hash) being
used to make a lookup in the table. If the bucket (cell) for that hash
exists then I return it otherwise I need to create it.

I hope it makes things clearer

Thank you very much -c
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      12-19-2010
On Dec 19, 6:55*pm, mast4as <(E-Mail Removed)> wrote:
> Oops and there was a bug in my code ...
>
> signedrand didn't return a value...
>
> float signedrand() { return (drand48()-0.5)*100; }
>
> With this corrected the map has a size = to the number of points
> "inserted". So that's much better
>
> grid size 2097152
> size of table 2097147
>
> How is that possible ? Considering that hash function is only
> returning a value of size_t how can it be that the value is so big ? I
> am confused... I would imagine that a lot of the points used in the
> hash function would return the same value (and therefore I was
> expected a table much smaller).


Perhaps the point: you compare in setequal collides 5 times.
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      12-19-2010
On Dec 19, 7:04*pm, mast4as <(E-Mail Removed)> wrote:
> Sorry I will try to explain again what I am trying to do. I have a set
> of points (particles in 3D space) and need to insert them in voxels.
> Instead of creating a static 3D grid, I want to use a dynamic one. The
> idea is to do something like that:
>
> for (each point in point set)
> * find cell for point p (using a hash map)
> * if cell doesn't exist create it (insert it in hash map)
> * insert p in cell
>
> so the paper recommends to use a hash map for this. What they do is
> that they use this hash function
>
> int hashfunc(const point &pt) { return 541 * pt.x + 79 * pt.y + 31 *
> pt.z; }
>
> where pt is the key indeed. The result of the function (hash) being
> used to make a lookup in the table. If the bucket (cell) for that hash
> exists then I return it otherwise I need to create it.
>
> I hope it makes things clearer


OK. It is clearer. But like i understand unordered_map is only weakly
sorted by hash. Hash causes some sort of "buckets" of same order in
map. In buckets the equality is decided by your "setequal".
 
Reply With Quote
 
mast4as
Guest
Posts: n/a
 
      12-19-2010

> OK. It is clearer. But like i understand unordered_map is only weakly
> sorted by hash. Hash causes some sort of "buckets" of same order in
> map. In buckets the equality is decided by your "setequal".


Ah thank you ... I guessed that already through your previous answer
so decided that maybe things would be easier for all of us if i
was actually finished my code ha ha ha... so here it is... it seems to
work. Let me know if you see anything that I am doing wrong (I mean I
know I use struct and all that which is not for the C++ purist but I
am just prototyping here to understand how unordered_map works. Thx a
lot for your feedbacks.

Thx Öö Tiib (not sure how to pronounce your name

-c


#include <cstdio>
#include <cmath>
#include <cstdlib>

#include <tr1/unordered_map>

//using namespace stdext;
//http://stackoverflow.com/questions/2099540/defining-custom-hash-
function-and-equality-function-for-unordered-map


template<typename T>
struct point {
T x, y, z;
};

struct hashfunc {
size_t operator() (const point<int> &pt) const { return 541 * pt.x
+ 79 * pt.y + 31 * pt.z; }
};

struct setequal {
bool operator() (const point<int> &pa, const point<int> &pb) const
{ return (pa.x == pb.x && pa.y == pb.y && pa.z == pb.z); }
};

typedef struct voxel {
float data;
};

typedef std::tr1::unordered_map<point<int>, voxel *, hashfunc,
setequal> tablegrid;

float signedrand() { return (drand48()-0.5)*2; }

int main (int argc, const char * argv[])
{
int dim = 1;
float cellsize = 0.01;
//int gridsize = dim * dim * dim;
//printf("grid size %d\n", gridsize);
int npts = 1e6;
tablegrid grid;
point<int> pt;
for (int i = 0; i < npts; ++i) {
if (i%512==0) fprintf(stderr, "\b\b\b\b%d%c", int(100*i/
float(npts-1)), '%');
pt.x = int(dim * signedrand() / cellsize);
pt.y = int(dim * signedrand() / cellsize);
pt.z = int(dim * signedrand() / cellsize);
tablegrid::const_iterator it = grid.find(pt);
if (it != grid.end()) {
// do nothing
}
else {
grid[pt] = new voxel;
}
//printf("val %d\n", hashfunc(pt));
}
printf("\nsize of table %d\n", grid.size());
// delete mem
tablegrid::const_iterator it = grid.begin();
for (; it != grid.end(); ++it) {
delete it->second;
}
printf("delete mem done\n", grid.size());
return 0;
}

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
how to have user defined hash for unordered_map ? abir C++ 3 07-11-2008 06:48 PM
iterator as key for unordered_map abir C++ 6 06-26-2008 09:59 PM
error with tr1 unordered_map iterator Rares Vernica C++ 6 02-28-2007 07:28 PM
Template problem with unordered_map Paulo Matos C++ 4 08-03-2006 05:10 PM



Advertisments