Используйте libcds SplitListMap с std::string

Question

Я пытаюсь создать хэш-карту, которая будет отображать 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> правильный?

Answer 1

Это обычная практика для хэш-карты. Хеш-функция может генерировать один хеш-код для разных ключей. Это называется столкновением. Когда мы ищем ключ, мы вычисляем хеш для ключа, ищем этот хеш на карте (обычно хеш - это просто индекс в хеш-таблице), а затем сравниваем ключ найденного элемента с нашим ключом. Так что std::less необходим.