Я пытаюсь создать хэш-карту, которая будет отображать std::string
в std::string
,
до сих пор я использовал следующий код:
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;
};
который основан на документации libcds. Но я не уверен, правильно ли я использую хеш-карту …
Согласно статье, которая описывает SplitListMap
основной список должен быть отсортирован по хэши ключей, но документация предлагает использовать std::less<TKey>
указать порядок списка Майкла.
Является ли использование std::less<std::string>
правильный ?
Это обычная практика для хэш-карты. Хеш-функция может генерировать один хеш-код для разных ключей. Это называется столкновением. Когда мы ищем ключ, мы вычисляем хеш для ключа, ищем этот хеш на карте (обычно хеш — это просто индекс в хеш-таблице), а затем сравниваем ключ найденного элемента с нашим ключом. Так что std :: less необходим.
Других решений пока нет …