Полезность KeyEqual в std :: unordered_set / std :: unordered_map - PullRequest
4 голосов
/ 06 июля 2019

Я понимаю, что это может быть неопределенным вопросом, но мне интересно, каковы реальные случаи, когда пользовательский компаратор полезен для хеш-контейнеров в std.Я понимаю, что это полезно в заказанных контейнерах, но для хэш-контейнеров это кажется немного странным.

Причина этого заключается в том, что значение хеш-функции для элементов, которые равны по сравнению с компаратором, должно быть одинаковым, и я считаю, что в большинстве случаев это фактически означает преобразование элемента поиска / вставки в некоторое общее представление (это быстрееи проще в реализации).

Например:

  • набор строк без учета регистра: если вы хотите правильно хэшировать, вам все равно нужно в верхнем / нижнем регистре всю строку.
  • набор дробей(где 2/3 == 42/63): вам нужно преобразовать 42/63 в 2/3, а затем хэшировать это ...

Поэтому мне интересно, может ли кто-нибудь привести примеры из реального мира?полезность настройки параметров шаблона std::unordered_, чтобы я мог распознать эти шаблоны в будущем коде, который я напишу.

Примечание 1: «аргумент симметрии» (std::map включает настройку компаратора, поэтому std::unordred_ должен быть настраиваемымтакже) это то, что я рассмотрел, и я не думаю, что это убедительно.

Примечание 2: Я смешал 2 вида компараторов (< и ==) в сообщении для краткости, я знаю, что std::map использует <, а std::unordered_map использует ==.

Ответы [ 3 ]

10 голосов
/ 06 июля 2019

Согласно https://en.cppreference.com/w/cpp/container/unordered_set

Внутренне, элементы сортируются не в каком-то определенном порядке, но организованы в ведра. В какую корзину помещается элемент, зависит полностью на хэш своей стоимости. Это позволяет быстрый доступ к отдельные элементы, так как после вычисления хеша это относится к точное ведро, в которое помещен элемент.

Таким образом, хеш-функция определяет область, в которой будет находиться ваш элемент, но как только будет определено значение области, для поиска элемента будет использоваться operator ==.

В основном operator == используется для разрешения коллизий хешей, и, следовательно, вам нужно, чтобы ваша хеш-функция и operator == были согласованными. Кроме того, если ваш оператор operator == говорит, что два элемента равны, набор не допустит дублирования.

Что касается настройки, я думаю, что идея нечувствительного к регистру set из string s хороша: для двух строк вам потребуется предоставить хэш-функцию без учета регистра, чтобы позволить set чтобы определить область, в которой должна храниться строка. Затем вам нужно будет указать пользовательский KeyEqual, чтобы позволить набору фактически извлекать элемент.

Случай, с которым мне приходилось сталкиваться в прошлом, был способом, позволяющим пользователям вставлять строки, отслеживая их порядок вставки, но избегая дубликатов. Итак, с учетом такой структуры:

struct keyword{
  std::string value;
  int sequenceCounter;
};

Вы хотите обнаружить дубликаты только в соответствии с value. Одним из решений, которое я придумал, была unordered_set с пользовательской функцией сравнения / хэширования, которая использовала только value. Это позволило мне проверить наличие ключа, прежде чем разрешить вставку.

2 голосов
/ 15 июля 2019

Одним из интересных способов использования является определение эффективных для памяти индексов (смысл термина в базе данных) для данного набора объектов.

Пример

Допустим, у нас есть программа, которая имеет коллекцию N объектов этого класса:

struct Person {
    // each object has a unique firstName/lastName pair
    std::string firstName;
    std::string lastName;

    // each object has a unique ssn value
    std::string socialSecurityNumber;

    // each object has a unique email value
    std::string email;
}

И нам нужно эффективно извлекать объекты по значению любого уникального свойства.

Сравнение реализаций

Сложности времени даются при условии, что сравнения строк являются постоянными (строки имеют ограниченную длину).

1) Одиночный unordered_map

С одним map, индексированным одним ключом (например: email):

std::unordered_map<std::string,Person> indexedByEmail;
  • Сложность времени: поиск по любому уникальному свойству, кроме email, требует обхода карты: среднее значение O (N).
  • Использование памяти: значение email дублируется. Этого можно избежать, используя один set с пользовательским хешем и сравнением (см. 3).

2) Несколько unordered_map, без пользовательского хэша и сравнение

С картой для каждого уникального свойства, с хешем и сравнениями по умолчанию:

std::unordered_map<std::pair<std::string,std::string>, Person> byName;
std::unordered_map<std::string, const Person*> byEmail;
std::unordered_map<std::string, const Person*> bySSN;
  • Сложность времени: при использовании соответствующей карты поиск по любому уникальному свойству составляет среднее значение O (1) .
  • Использование памяти: неэффективно, из-за всех string дубликатов.

3) Несколько unordered_set, пользовательский хэш и сравнение:

С помощью пользовательского хеша и сравнения мы определяем различные unordered_set, которые будут хэшировать и сравнивать только определенные поля объектов. Наборы тезисов можно использовать для поиска, как если бы элементы хранились в map, как в 2, но без дублирования какого-либо поля.

using StrHash = std::hash<std::string>;
// --------------------
struct PersonNameHash {
    std::size_t operator()(const Person& p) const {
        // not the best hashing function in the world, but good enough for demo purposes.
        return StrHash()(p.firstName) + StrHash()(p.lastName);
    }
};
struct PersonNameEqual {
    bool operator()(const Person& p1, const Person& p2) const {
        return (p1.firstName == p2.firstName) && (p1.lastName == p2.lastName);
    }
};
std::unordered_set<Person, PersonNameHash, PersonNameEqual> byName;

// --------------------
struct PersonSsnHash {
    std::size_t operator()(const Person* p) const {
        return StrHash()(p->socialSecurityNumber);
    }
};
struct PersonSsnEqual {
    bool operator()(const Person* p1, const Person* p2) const {
        return p1->socialSecurityNumber == p2->socialSecurityNumber;
    }
};
std::unordered_set<const Person*, PersonSsnHash, PersonSsnEqual> bySSN;

// --------------------
struct PersonEmailHash {
    std::size_t operator()(const Person* p) const {
        return StrHash()(p->email);
    }
};
struct PersonEmailEqual {
    bool operator()(const Person* p1, const Person* p2) const {
        return p1->email == p2->email;
    }
};
std::unordered_set<const Person*,PersonEmailHash,PersonEmailEqual> byEmail;
  • Сложность времени: поиск по любому уникальному свойству по-прежнему составляет в среднем O (1).
  • Использование памяти: намного лучше, чем 2): нет string дублирование.

Демонстрационная версия

0 голосов
/ 17 июля 2019

Хеш-функция сама делает что-то для извлечения функций определенным образом, и задача компаратора состоит в том, чтобы различать, являются ли объекты одинаковыми или нет
С «оболочкой» данных вам не нужно изменять компаратор
Вкратце: добавьте в данные функциональную оболочку. Функции отвечают за сравнение

На самом деле, я не совсем понимаю, что у вас за описание проблемы. Моя речь неизбежно запутана в логике. Пожалуйста, поймите. :)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...