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 ?
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.