hash_map,map hash function for composite key

Question

I got a working std::map class, which is somewhat slow, so I want to try other datastructures

My key is a composite datatype like

typedef struct {
  char * name;
  int offset;
}position;

And for the std::map I'm using the following partial ordering function

struct cmp_position {
  bool operator()(const position& first,const  position& second) {
    int tmp = std::strcmp(first.name, second.name);
    if(tmp!=0)
      return tmp<0;
    else
      return first.offset<second.offset;
  }
};

And my map definition is

typedef std::map<position,int,cmp_position> myMap;

I've been looking at the __gcc_ext::hash_map this requires an equality function which could simply be

struct positionEq
{
  bool operator()(const position& s1, const position & s2) const
  {
    return strcmp(s1.name, s2.name) == 0 && (s1.offset==s2.offset) ;
  }
};

Which should work, but I'm having troubles with the hash function of my composite type. I guess I could do something like

position s;
char buf[100];
snprintf(buf,100,"%s:%d\n",s.name,s.offset);

But I'm having problems glueing it together.

Actually the map and hash map might be somewhat overkill since I'm not using the value of the keys, I'm solely using my map for checking for existence.

It's my intention not to use std::strings.

Thanks

Edit:

In the above example, I tried with a std::set instead of std::map, and std::set is consistently slower both populating and looking up entries. It uses a lot less memory though the overall comparison is tabulated below. I tried running each 10 times

         Set        map
 size   1.8gig     3.1gig
 pop    <15sec     <14sec
 find   <12sec     <9sec

I used a dataset with more than 34mio entries, and after populating the datastructure, i tried looking up all 34 mio elements. I guess the conclusion is, that other than apart from conserving memory, the std::set is inferior.

Please define "is somewhat slow". What is slow? Insertion? Finding? Traversal? — sbi, Jun 17 '11 at 17:44
It's better to learn unordered_map than hash_map. Both are hash tables, but unordered_map is (or very soon will be) standard. — , Jun 17 '11 at 17:50
It should be _somewhat fast_ in a release build, how are you profiling to determine this? In agreement with Steve, if you don't need values use a more appropriate container. — AJG85, Jun 17 '11 at 18:49

score 0 · Answer 1 · edited May 23 '17 at 10:08

Have you tried it with the key structure storing a hashed value of name (using boost::hash_value for example) - so that comparing key objects would be just two number comparisons, which should be pretty quick.

Try testing it with an unordered_set. The boost::multi_index_container claims to outperform std::set and such in some circumstances, you could see if that speeds things along a bit (see my answer here for an example of its use).

hash_map,map hash function for composite key

1 Answers1