0

I try to create hash map that will map std::string to std::string, so far I used the following code: 

template<typename TKey, typename TValue>
struct lockfree_hash_map_traits_t
    : public cds::container::split_list::type_traits 
{

    typedef cds::container::michael_list_tag  ordered_list    ;   // what type of ordered list we want to use
    typedef std::hash<TKey>                   hash            ;   // hash functor for the key stored in split-list map

    // Type traits for our MichaelList class
    struct ordered_list_traits: public cds::container::michael_list::type_traits {
        typedef std::less<TKey> less;   // comparer that specifies order of list nodes
    };
};

template<typename TKey, typename TValue>
class lockfree_hash_map_t { 
public:
    typedef
        cds::container::SplitListMap<cds::gc::HP, TKey, TValue, lockfree_hash_map_traits_t<TKey, TValue> > 
        base_hash_map;

// ... some stuff
private:
    base_hash_map _map;
};

which is based on libcds documentation. But I am uncertain if I use hash map correctly... According to paper that describes SplitListMap underlying list should be sorted by hashes of keys, but documentation suggests to use std::less<TKey> to specify Michael List order. Is use of std::less<std::string> correct ?

user1669174
  • 3
  • 1

1 Answers1

0

It is usual practice for hash map. The hash function can produce one hash code for different keys. It is called as a collision. When we search for a key we compute a hash for the key, search this hash in the map (usually the hash is just an index in hash table) and then compare the key of item found with our key. So the std::less is necessary.

Max Khiszinsky
  • 56
  • 2
  • Referring to this question, could you maybe provide an example how to init this Map in a main function and add one element? I was also searching in the documentation, just writing `int2int_map name;` causes an exception for me (referring to the example given in the docu). – Alex VII Jun 03 '14 at 10:13