Одним из интересных способов использования является определение эффективных для памяти индексов (смысл термина в базе данных) для данного набора объектов.
Пример
Допустим, у нас есть программа, которая имеет коллекцию 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 дублирование.
Демонстрационная версия