Гибкая индексация элементов в контейнере на С++ и при чём тут Boost.MultiIndex24.05.2022 10:31

Мотивация

Предположим, что ты — С++ программист и тебе нужно создать справочник. Ну, а точнее, рассмотрим один из этапов, когда тебе нужно отобразить одно множество на другое. В процессе поиска решения ты узнаешь про хэш-таблицы, деревья, и делаешь самую наивную реализацию. После чего, при усложнении стандартного примера, начинаешь задаваться вопросами:

  1. Как сделать ключом поле класса?

  2. Что, если правил для индексации (способов отображения одного мн-ва на другое) станет больше 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 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 persons
{
		{ "Jena", Person{"Jena", "Kisly", 60} },
		{ "Vadya", Person{"Vadya", "Molodec", 40} },
		{ "Onnia", Person{"Onnia", "Solnce", 40} }
};

auto jenaIter = persons.find("Jena");

Но и в таком решении есть ряд недостатков:

  1. Дублирование одинакового значения (имени) в памяти.
    Плохо, как минимум потому что мы дублируем строки, которые могут занимать много места, и, в рамках предметной области, таких строк может быть много. Следовательно, масштабы дублирования, в перспективе, станут колоссальными.

  2. Проблемы синхронизации, вытекает из п.1.
    Если программисту скажут добавить фичу смены имени, то ему нужно будет помнить о том, что после изменения поля Person: name надо ещё актуализировать значение соответствующего ключа. Можно, конечно, написать для этого специальной обвес, но нужно ли?

  3. Сложность изменения ключа, вытекает из п.2.
    Чтобы добиться синхронизации, нужно будет изменить ключ. Вообще, сделать это до C++17 с его unordered_map::extract красиво не получится, потому что ключ константен. Сделать это можно только через unordered_map::erase+ unordered_map::insert, комбинация которых вроде бы не должна приводить к оверхэду вида ресайза и/или рехэширования.

  4. Решение не выдержит, если мы захотим индексироваться по ещё какому-то полю (а мы обязательно захотим). К примеру, по фамилии.

Проанализировав список проблем, можно сказать, что их часть можно решить довольно просто, если не нарушать DRY. Можем заDRYить, убрав поле Person::name, пусть значение имени будет храниться только в ключе контейнера: 

std::unordered_map persons
{
		{ "Jena", Person{"Kisly", 60} },
		{ "Vadya", Person{"Molodec", 41} },
		{ "Onnia", Person{"Solnce", 40} }
};

auto jenaIter = persons.find("Jena");

Минусы решения налицо:

  1. Нарушение принципа наименьшего удивления.
    Такое решение выглядит как минимум странновато, что значит — новоприбывшему программисту (две недели в отпуске делают нас всех такими) потребуется больше времени на осознание кода.

  2. Высокая связанность со спецификой конкретного контейнера. Это затруднит переход к другому контейнеру, при необходимости.

  3. Никуда не пропала сложность изменения ключа.

  4. Никуда не пропала проблема индексации по другим полям.

Тогда в голову приходит решение через std::unordered_set. Для него нужно будет реализовать хэш-функцию и компаратор по имени: 

template
class NameHash
{
public:
    size_t operator()(ClassWithNameField const& person) const
    {
        return std::hash{}(person.name);
    }
};

template
class NamesEqual
{
public:
    bool operator()(ClassWithNameField const& lhs, ClassWithNameField const& rhs) const
    {
        return lhs.name == rhs.name;
    }
};

void main()
{
    std::unordered_set, NamesEqual> persons
    {
        Person{"Jena", "Kisly", 60},
        Person{"Vadya", "Molodec", 41},
        Person{"Onnia", "Solnce", 40}
    };

    auto jenaIter = persons.find(Person{"Jena", "blah", 0});
}

Но и такое решение не идеально. Нам приходится делать кучу всего:

  1. Создавать фиктивный объект Person для поиска по имени.

    1. В частности, приходится знать какое из полей Person при поиске — фиктивное, хотя это дело хэш-функции и компаратора.

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

  3. Людей с одним и тем-же именем может быть больше 1, поэтому множество (set) не подходит по определению.

  4. Никуда не пропала проблема индексации по другим полям.

Решение при помощи std: set:: is_transperent

Забегая немного вперёд, мало кто об этом знает, но начиная с C++14 проблемы предыдущего решения:

  1. [1] и [1.1], связанные с тем, что приходится знать о семантике ключа.

  2. [4], связанная с индексацией по другим полям.

можно полностью устранить, если у вас ordered контейнер (прим. std::set) и вы используете C++14 или выше.

Для этого нужно определить в компараторе алиас 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;
    }
	
  	// сравнение по годам, если для поиска передали uint8_t
    bool operator()(uint8_t years, Person const& person) const
    {
        return years < person.years;
    }
    bool operator()(Person const& person, uint8_t years) const
    {
        return person.years < years;
    }

  	// сравнение по фамилии, если для поиска передали std::string
    bool operator()(std::string surname, Person const& person) const
    {
        return surname < person.surname;
    }
    bool operator()(Person const& person, std::string surname) const
    {
        return person.surname < surname;
    }
};

void main()
{
    std::set persons
    {
        Person{"Jena", "Kisly", 60},
        Person{"Vadya", "Molodec", 41},
        Person{"Onnia", "Solnce", 40}
    };

    auto jenaIter = persons.find(Person{"Jena", "Kisly", 60});
    auto vadyaIter = persons.find(41);
    auto onniaIter = persons.find("Solnce");
}

В общем же случае это решение блестяще решает только проблему [1] (фиктивный объект). Но проблема [1.1] только немного видоизменяется: теперь нам надо знать семантику переданного волшебного числа, о которой должен знать только компаратор. Но видимо это as design ¯\_(ツ)_/¯

А касательно проблемы [4](индексации по другим полям), поскольку в таком решении выбор типа влияет на поле, по которому ведётся поиск, и эта связь — логическая, т.е. компилятор не сможет её никак провалидировать самостоятельно, то велика вероятность наткнутся на курьёзную ситуацию, когда в find из предыдущего примера кто-нибудь захочет передать имя, вместо фамилии. В таком случае человек найдёт ошибку только в рантайме, что намного позже, чем хотелось бы. На данном примере, конечно, это будет почти безобидно, но вероятность наткнуться на эту проблему растёт с количеством полей одинакового типа.

Итог: решение на основе STL

Я не описал все возможные варианты решения, но так или иначе, все они будут иметь схожие существенные проблемы (не обязательно все):

  • Слишком много знать о семантике ключа.

  • Размазывать логику сравнения по разным классам, отделяя её от определения контейнера.

  • Смириться с тем, что индексироваться сразу по нескольким полям — несколько проблематично.

Решение на основе стандартной библиотеки получается недостаточно гибким. В такой ситуации приходит время либо пилить самопал, либо же обратиться к готовым решениям. Одно из таких решений — Boost.MultiIndex.

Решение на основе Boost.MultiIndex

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

e07f6aa1a57883bbb81a78b7d4c62050.jpeg

Возвращаясь к примеру с Person, решение на основе multi_index_container будет выглядеть так: 

#include 
#include 
#include 

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,
                boost::multi_index::member
            >
        >
    >;  

void main()
{
    Persons persons
    {
        Person{"Jena", "Kisly", 60},
        Person{"Vadya", "Molodec", 41},
        Person{"Onnia", "Solnce", 40}
    };

    auto const& personsByName = persons.get();
    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,
                boost::multi_index::member
            >,
            boost::multi_index::hashed_unique<
                boost::multi_index::tag,
                boost::multi_index::member
            >
        >
    >;  

void main()
{
    Persons persons
    {
        Person{"Jena", "Kisly", 60},
        Person{"Vadya", "Molodec", 41},
        Person{"Onnia", "Solnce", 40}
    };

    auto const& personsByName = persons.get();
    auto jenaIter = personsByName.find("Jena");

    auto const& personsBySurname = persons.get();
    auto vadyaIter = personsByName.find("Molodec");
}

Фактически, мы добавили всего ничего кода (картинка ниже), но решили почти все существенные проблемы, которые были у предыдущих решений.

Среди альтернативных решений в голову приходит только пара unordered_map, где в одном ключом будет name, а в другом surname. Но такая система из двух карт очень неудобная и рано или поздно приведёт к ошибкам, связанным с синхронизацией элементов контейнеров.
Ну или ещё можно было бы использовать unordered_set вместе с is_transperent, как я описывал до этого, но у этого варианта тоже есть существенные недостатки, о которых я писал.

Ещё один из плюсов boost::multi_index::multi_index_container это то, что он позволяет нам довольно просто создавать и использовать составные ключи: 

#include 

class Person
{
  	// ...
};

using Persons = boost::multi_index::multi_index_container<
        Person,
        boost::multi_index::indexed_by<
            boost::multi_index::hashed_non_unique<
                boost::multi_index::tag,
                boost::multi_index::composite_key<
                    Person,
                    boost::multi_index::member,
                    boost::multi_index::member
                >
            >
        >
    >;  

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();
    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();
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();
auto jenaIter = personsByName.find("Jena");
personsByName.modify_key(jenaIter, [](std::string& name){ name="Jonny"; });

Это ещё не вся сила данного контейнера. Существуют и другие виды индексов, которые делают решение на основе данного контейнера более гибким. Если кратко, то инструкция по их выбору примерно следующая:

1.а Если элементы идут по порядку (через сравнение по оператору <>==) — нужен ordered_index.
1.b Если нужно индексироваться по хэшу — нужен hashed_index.

2.a Если элемент по ключу уникален — нужен _unique индекс
Синтаксис: [ordered|hashed]_unique.
Если ordered то получится как в std::set, если hashed то как в std::unordered_set.
2.b Элемент по ключу не уникален — нужен _non_unique индекс
Синтаксис: [ordered | hashed]_non_unique.
Если ordered то получится как в std::multiset, если hashed то как в std::unordered_multiset.

3. Нужен произвольный доступ к элементу по индексу — используем random_access индекс (получится как в std::vector/array).

Заключение

Boost.MultiIndex — мощный инструмент, который за цену довольно допустимых компромиссов даёт большие возможности для индексации по набору данных. Благодарю за внимание!

© Habrahabr.ru