Мотивация
Предположим, что ты - С++ программист и тебе нужно создать справочник. Ну а точнее, рассмотрим один из этапов, когда тебе нужно отобразить одно множество на другое. В процессе поиска решения ты узнаешь про хэш-таблицы, деревья, и делаешь самую наивную реализацию. После чего, при усложнении стандартного примера, начинаешь задаваться вопросами:
Как сделать ключом поле класса?
Что, если правил для индексации(способов отображения одного мн-ва на другое) станет больше 1?
Для начала рассмотрим класс с информацией о человеке, на котором будем рассматривать следующие примеры:
struct Person
{
Person(std::string name, std::string surname, uint8_t years)
: name(std::move(name))
, surname(std::move(surname))
, years(years)
{
}
std::string name;
std::string surname;
uint8_t years;
};Решение в рамках стандартной библиотеки
Давайте начнём с наивной реализации:
std::vector<Person> persons
{
Person("Jena", "Kisly", 60),
Person("Vadya", "Molodec", 40),
Person("Onnia", "Solnce", 40)
};
auto jenaIter = std::find_if(persons.begin(), persons.end(),
[](Person const& person) {return person.name == "Jena";});Очевидна проблема такого решения - слишком долгий поиск по контейнеру. Можно добиться, в среднем, константного времени поиска, вместо линейного(пока что опустим нюанс, что людей с одним именем может быть больше 1). Для этого пусть поле name отныне будет ключом в хэш-таблице:
std::unordered_map<std::string/*name*/, Person> persons
{
{ "Jena", Person{"Jena", "Kisly", 60} },
{ "Vadya", Person{"Vadya", "Molodec", 40} },
{ "Onnia", Person{"Onnia", "Solnce", 40} }
};
auto jenaIter = persons.find("Jena");Но и в таком решении есть ряд недостатков:
Дублирование одинакового значения(имени) в памяти.
Плохо, как минимум потому что мы дублируем строки, которые могут занимать много места, и, в рамках предметной области, таких строк может быть много. Следовательно, масштабы дублирования, в перспективе, станут колоссальными.Проблемы синхронизации, вытекает из п.1.
Если программисту скажут добавить фичу смены имени, то ему нужно будет помнить о том, что после изменения поляPerson::nameнадо ещё актуализировать значение соответствующего ключа. Можно, конечно, написать для этого специальной обвес, но нужно ли?Сложность изменения ключа, вытекает из п.2.
Чтобы добиться синхронизации, нужно будет изменить ключ. Вообще, сделать это до C++17 с егоunordered_map<T>::extractкрасиво не получится, потому что ключ константен. Сделать это можно только черезunordered_map<T>::erase+unordered_map<T>::insert, комбинация которых вроде бы не должна приводить к оверхэду вида ресайза и/или рехэширования.Решение не выдержит, если мы захотим индексироваться по ещё какому-то полю(а мы обязательно захотим). К примеру, по фамилии.
Проанализировав список проблем, можно сказать, что их часть можно решить довольно просто, если не нарушать DRY. Можем заDRYить, убрав поле Person::name, пусть значение имени будет храниться только в ключе контейнера:
std::unordered_map<std::string/*name*/, Person> persons
{
{ "Jena", Person{"Kisly", 60} },
{ "Vadya", Person{"Molodec", 41} },
{ "Onnia", Person{"Solnce", 40} }
};
auto jenaIter = persons.find("Jena");Минусы решения налицо:
Нарушение принципа наименьшего удивления.
Такое решение выглядит как минимум странновато, что значит - новоприбывшему программисту(две недели в отпуске делают нас всех такими) потребуется больше времени на осознание кода.Высокая связанность со спецификой конкретного контейнера. Это затруднит переход к другому контейнеру, при необходимости.
Никуда не пропала сложность изменения ключа.
Никуда не пропала проблема индексации по другим полям.
Тогда в голову приходит решение через std::unordered_set. Для него нужно будет реализовать хэш-функцию и компаратор по имени:
template<typename ClassWithNameField>
class NameHash
{
public:
size_t operator()(ClassWithNameField const& person) const
{
return std::hash<decltype(person.name)>{}(person.name);
}
};
template<typename ClassWithNameField>
class NamesEqual
{
public:
bool operator()(ClassWithNameField const& lhs, ClassWithNameField const& rhs) const
{
return lhs.name == rhs.name;
}
};
void main()
{
std::unordered_set<Person, NameHash<Person>, NamesEqual<Person>> persons
{
Person{"Jena", "Kisly", 60},
Person{"Vadya", "Molodec", 41},
Person{"Onnia", "Solnce", 40}
};
auto jenaIter = persons.find(Person{"Jena", "blah", 0});
}Но и такое решение не идеально. Нам приходится делать кучу всего:
Создавать фиктивный объект
Personдля поиска по имени.В частности, приходится знать какое из полей
Personпри поиске - фиктивное, хотя это дело хэш-функции и компаратора.
Писать отдельные от объявления контейнера хэш-функцию и компаратор, что размазывает логику по коду, тем самым затрудняя его понимание.
Людей с одним и тем-же именем может быть больше 1, поэтому множество(set) не подходит по определению.
Никуда не пропала проблема индексации по другим полям.
Решение при помощи transparent компаратора
Забегая немного вперёд, мало кто об этом знает, но начиная с C++14 проблему предыдущего решения 1, связанную с созданием фиктивного объекта, можно устранить, если:
У вас ordered контейнер(прим.
std::set) и вы используете C++14 или выше .У вас unordered контейнер(прим.
std::unordered_set) и вы используете C++20 или выше.
Для этого нужно определить в компараторе алиас is_transparent(какой тип алиасить - не важно). Это позволит использовать перегрузки find( count, upper_bound etc.), которые позволяют сравнивать с элементом в контейнере значения любого другого типа.
На нашем примере это выглядит так:
class PersonsComparator
{
public:
using is_transparent = void;
// сравнение по имени, если для поиска передали Person
bool operator()(Person const& lhs, Person const& rhs) const
{
return lhs.name < rhs.name;
}
// сравнение по фамилии, если для поиска передали std::string
bool operator()(std::string const& name, Person const& person) const
{
return name < person.name;
}
bool operator()(Person const& person, std::string const& name) const
{
return person.name < name;
}
};
void main()
{
std::set<Person, PersonsComparator> persons
{
Person{"Jena", "Kisly", 60},
Person{"Vadya", "Molodec", 41},
Person{"Onnia", "Solnce", 40}
};
auto jenaIter = persons.find(Person{"Jena", "Kisly", 60});
auto onniaIter = persons.find("Onnia");
}Но данное решение не до конца устраняет проблему [1.1], а только немного видоизменяет: теперь нам надо знать семантику передаваемого в компаратор значения(в данном случае знать, что это - имя), о которой должен знать только компаратор. Но видимо это as design ¯\_(ツ)_/¯
Изначально я даже неверно предположил, что таким решением можно решить проблему [4](индексации по другим полям). Но как верно меня поправили пользователи Хабра, transparent компаратор позволяет сравнивать только по тому полю структуры, которое используется для определения отношения порядка в контейнере. В нашем случае, в методе operator()(Person const &, Person const &), это поле name. То есть transparent компаратор не решает проблему поиска по нескольким полям, а только позволяет выполнять поиск по значению, не создавая промежуточного пустого объекта Person (решает проблему [1]).
Если же говорить о том, что произойдёт если попробовать сделать индексацию по нескольким полям в transparent компараторе, то @0o00oo00o0 выяснил эмпирически, что поиск по контейнеру с таким компаратором ведёт себя нестабильно и может приводить к падению.
Итог: решение на основе STL
Я не описал все возможные варианты решения, но так или иначе, все они будут иметь схожие существенные проблемы(не обязательно каждую):
Слишком много знать о семантике ключа.
Размазывать логику сравнения по разным классам, отделяя её от определения контейнера.
Смириться с тем, что индексироваться сразу по нескольким полям - несколько проблематично.
Решение на основе стандартной библиотеки получается недостаточно гибким. В такой ситуации приходит время либо пилить самопал, либо же обратиться к готовым решениям. Одно из таких решений - Boost.MultiIndex.
Решение на основе Boost.MultiIndex
Для начала оговорюсь, что это решение предполагает некоторые компромиссы, в первую очередь связанные с непонятным с первого взгляда объявлением контейнера, завязанном на шаблонах. Но, с моей точки зрения, таков путь буста.
Возвращаясь к примеру с Person, решение на основе multi_index_container будет выглядеть так:
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/hashed_index.hpp>
class Person
{
// name, surname, years
};
using Persons = boost::multi_index::multi_index_container<
Person,
boost::multi_index::indexed_by<
boost::multi_index::hashed_unique<
boost::multi_index::tag<struct PersonsByName>,
boost::multi_index::member<Person, decltype(Person::name), &Person::name>
>
>
>;
void main()
{
Persons persons
{
Person{"Jena", "Kisly", 60},
Person{"Vadya", "Molodec", 41},
Person{"Onnia", "Solnce", 40}
};
auto const& personsByName = persons.get<PersonsByName>();
auto jenaIter = personsByName.find("Jena");
}Да, выглядит посложнее чем с unordered_map. Но зато теперь наши возможности почти безграничны. К примеру, теперь мы можем легко добавить возможность индексироваться и по фамилии:
using Persons = boost::multi_index::multi_index_container<
Person,
boost::multi_index::indexed_by<
boost::multi_index::hashed_unique<
boost::multi_index::tag<struct PersonsByName>,
boost::multi_index::member<Person, decltype(Person::name), &Person::name>
>,
boost::multi_index::hashed_unique<
boost::multi_index::tag<struct PersonsBySurname>,
boost::multi_index::member<Person, decltype(Person::surname), &Person::surname>
>
>
>;
void main()
{
Persons persons
{
Person{"Jena", "Kisly", 60},
Person{"Vadya", "Molodec", 41},
Person{"Onnia", "Solnce", 40}
};
auto const& personsByName = persons.get<PersonsByName>();
auto jenaIter = personsByName.find("Jena");
auto const& personsBySurname = persons.get<PersonsBySurname>();
auto vadyaIter = personsBySurname.find("Molodec");
}Фактически, мы добавили всего ничего кода, но решили почти все существенные проблемы, которые были у предыдущих решений.
Среди альтернативных решений в голову приходит только пара unordered_map, где в одном ключом будет name, а в другом surname. Но такая система из двух карт очень неудобная и рано или поздно приведёт к ошибкам, связанным с синхронизацией элементов контейнеров.
Ну или ещё можно было бы использовать пару unordered_set вместе с is_transparent, как я описывал до этого, но у этого варианта тоже есть существенные недостатки, о которых я писал.
Ещё один из плюсов boost::multi_index::multi_index_container это то, что он позволяет нам довольно просто создавать и использовать составные ключи:
#include <boost/multi_index/composite_key.hpp>
class Person
{
// name, surname, years
};
using Persons = boost::multi_index::multi_index_container<
Person,
boost::multi_index::indexed_by<
boost::multi_index::hashed_non_unique<
boost::multi_index::tag<struct PersonsByNameAndSurname>,
boost::multi_index::composite_key<
Person,
boost::multi_index::member<Person, decltype(Person::name), &Person::name>,
boost::multi_index::member<Person, decltype(Person::surname), &Person::surname>
>
>
>
>;
void main()
{
Persons persons
{
Person{"Jena", "Kisly", 60},
Person{"Jena", "Kisly", 10},
Person{"Vadya", "Molodec", 41},
Person{"Onnia", "Solnce", 40}
};
auto const& personsByName = persons.get<PersonsByNameAndSurname>();
auto jenaIter = personsByName.find(boost::make_tuple("Jena","Kisly"));
}Так же в этом примере мы учли, что существуют люди с одинаковыми именем и фамилией при помощи _non_unique индекса. Теперь, чтобы найти всех людей с одними и теми же именем и фамилией достаточно вызвать метод equal_range:
Persons persons
{
Person{"Jena", "Kisly", 60},
Person{"Jena", "Kisly", 62},
Person{"Vadya", "Molodec", 41},
Person{"Onnia", "Solnce", 40}
};
auto const& personsByName = persons.get<PersonsByNameAndSurname>();
auto jenasItersPair = personsByName.equal_range(boost::make_tuple("Jena","Kisly"));
// Вывод в зависимости от хэш-функции:
// Jena Kisly 62
// Jena Kisly 60
std::for_each(jenasItersPair.first, jenasItersPair.second,
[](Person const& person)
{
std::cout << person.name
<< " " << person.surname
<< " " << (size_t)person.years << std::endl;
});Проблема с тем, что смена значения ключа довольно некрасивая(до C++17), тоже теперь разрешима. Нужно использовать метод modify_key:
auto& personsByName = persons.get<PersonsByName>();
auto jenaIter = personsByName.find("Jena");
personsByName.modify_key(jenaIter, [](std::string& name){ name="Jonny"; });Это ещё не вся сила данного контейнера. Существуют и другие виды индексов, которые делают решение на основе данного контейнера более гибким. Если кратко, то инструкция по их выбору примерно следующая:
Способ индексации | Ключ уникален | Вид индекса | Аналогичный STL контейнер |
На основе отношения порядка(через сравнение по оператору <>==) | Да |
|
|
Нет |
|
| |
Через хэш | Да |
|
|
Нет |
|
| |
Произвольный доступ по номеру элемента в контейнере |
|
| |
Последовательный доступ |
|
|
Сравнение производительности Boost.MultiIndex vs STL
В Boost.MultiIndex не используется динамический полиморфизм, поэтому вызовы методов boost::multi_index::multi_index_container не создают дополнительных расходов на динамическую диспетчеризацию.
Согласно проверкам производительности, предоставленным в документации Boost.MultiIndex, multi_index_container превосходит как по пространственной, так и по временной эффективности эквивалентные структуры данных, полученные через ручное комбинирование STL контейнеров. Это становится более заметно, когда количество индексов увеличивается.
Если же говорить про частный случай, когда мы используем только один индекс, то производительность Boost.MultiIndex сравнима с производительностью протестированных реализаций STL и даже может привести к некоторым улучшениям как в потреблении памяти, так и во времени выполнения.
Заключение
Boost.MultiIndex - мощный инструмент, который за цену довольно допустимых компромиссов даёт большие возможности для индексации по набору данных. Благодарю за внимание!
