Комментарии 22
Есть парочка вопросов (предположу что найти на них ответ можно в доке, но раз уж мы тут собрались):
Что с производительностью?
Что с накладными расходами на память?
Какие плюсы/минусы относительно хранения нескольких индексов в нескольких контейнерах, а в значениях - указатели?
Если индексы всё равно нужны, то накладных расходов нет.
Из особенностей: т.к. для контейнера вся структура ключ, то при необходимости модификации "значения" приходится либо помечать неключевые поля как mutable, либо делать const_cast (вопрос: как это делать канонично?). Использовать modify - явно не вариант, т.к. тогда итерирование замедляется в несколько раз.
Если вы:
1. Ищете иных способов изменения значения, кроме modify.
2. Уверены, что изменение значения поля не повлияет на индексацию(не относится ни к одному индексу).
То можно получить ссылку на значение через итератор: iter->get_node()->value(). После получения ссылки можно будет модифицировать интересующее вас поле.
Правда я не уверен насколько этот метод каноничен, да и на безопасность он тоже не претендует. Вполне допускаю, что есть более подходящие способы.
В сравнении производительности, предоставленном в документации Boost.MultiIndex, авторы утверждают, что multi_index_container превосходит как по пространственной, так и по временной эффективности эквивалентные структуры данных, полученные через ручное комбинирование STL контейнеров. Это становится более заметно, когда количество индексов увеличивается.
Если же говорить про частный случай, когда мы используем только один индекс, то производительность Boost.MultiIndex сравнима с производительностью протестированных реализаций STL и даже может привести к некоторым улучшениям как в потреблении памяти, так и во времени выполнения.
Так вы производительность меряли или нет? Пляски с логической и физической константностью для mutable никаких проблем не создают? Или вы не обращали внимания?
Не до конца понял что именно вы имеете ввиду. Предположу, что вы говорите про специфику внутреннего представления ключей в multi_index_container. Если так то, судя по всему, эта специфика либо не влияет на производительность, либо же влияет недостаточно чтобы решение стало хуже эквивалента на STL-ном контейнере.
В сравнении производительности, предоставленном в документации Boost.MultiIndex, авторы утверждают, что multi_index_container превосходит как по пространственной, так и по временной эффективности эквивалентные структуры данных, полученные через ручное комбинирование STL контейнеров. Это становится более заметно, когда количество индексов увеличивается.
Если же говорить про частный случай, когда мы используем только один индекс, то производительность Boost.MultiIndex сравнима с производительностью протестированных реализаций STL и даже может привести к некоторым улучшениям как в потреблении памяти, так и во времени выполнения.
Это позволит использовать перегрузки
find(count,upper_boundetc.), которые позволяют сравнивать с элементом в контейнере всё что-угодно.
Не очень понимаю, как это работает (и работает ли это вообще)? Тоесть мы отсортировали set по одному полю, а искать можем по любому другому полю? Это как?
В худшем случае — неправильно. Плюсы ничего особо не запрещают.
Как оказалось, я действительно неверно понял механизм работы std::set<T>::is_transparent. Прошу прощения. Таким решением нельзя решить проблему [4](индексации по другим полям).
transparent компаратор позволяет сравнивать только по тому полю структуры, которое используется для определения отношения порядка в контейнере. В нашем случае, в методе operator()(Person const &, Person const &), это поле name. То есть is_transparent не решает проблему поиска по нескольким полям, а только позволяет выполнять поиск по значению, не создавая промежуточного пустого объекта Person (решает проблему [1]).
Если же говорить о том, что произойдёт если попробовать сделать индексацию по нескольким полям в transparent компараторе, то @0o00oo00o0 выяснил эмпирически, что поиск по контейнеру с таким компаратором ведёт себя нестабильно и может привести к падению:
mscv2019 программа падает, если заменить в find(41) из примера значение 41 на 40 или 60.
Поэтому решение на основе transparent компаратора становится не таким привлекательным.
Собственно для включения «прозрачного сравнения» требуются активные действия именно потому, что это накладывает новый инвариант: компараторы должны быть согласованы. В статье действительно что-то странное предлагается.
Мне понравилось решение с std:set. Оно проще и не надо городить миллион шаблонов. Если есть вероятность запутаться, на каждое поле в структуре можно завести тип-тэг (PersonByName, PersonBySurnane, PersonByAgeAndName, etc), точно также как это делает решение с boost.
Вроде это решит все обозначенные проблемы?
Это действительно решает почти все обозначенные проблемы. Говорю почти все потому что, чтобы применить такое решение нужно:
Использовать минимум C++14, если нужен гетерогенный поиск по упорядоченным контейнерам.
Использовать минимум С++20, если нужен гетерогенный поиск по неупорядоченным контейнерам.
Писать отдельные от объявления контейнера хэш-функции(для неупорядоченного контейнера) и компараторы(для упорядоченного), что размазывает логику по коду, тем самым затрудняя его понимание.
Ещё, если я вас верно понял, то стоит учитывать, что такое решение потребует написать намного больше кода и потребует больше ручной работы. Поскольку:
Нужно будет определять по структуре тэга с конструктором, принимающим один параметр(если только это не POD), потому что нам надо будет передавать через объект этой тэга значение ключа.
Нужно будет создавать реализацию
operator()в компараторе для каждого из тегов вручную. При этом стоит учитывать, что всегда нужно по 2 реализации: когда тег - первый параметр, и когда второй.
В итоге придётся написать так:
struct PersonBySurname
{
PersonBySurname(std::string surname)
: surname(std::move(surname))
{
}
std::string surname;
};
class PersonsComparator
{
public:
using is_transparent = void;
bool operator()(Person const& lhs, Person const& rhs) const
{
return lhs.name < rhs.name;
}
bool operator()(PersonBySurname const& surnameTag, Person const& person) const
{
return surnameTag.surname < person.surname;
}
bool operator()(Person const& person, PersonBySurname const& surnameTag) const
{
return person.surname < surnameTag.surname;
}
};Вместо in-place объявления в типе контейнера boost::multi_index::tag<struct PersonsByName> :
boost::multi_index::hashed_unique<
boost::multi_index::tag<struct PersonsBySurname>,
boost::multi_index::member<Person, decltype(Person::surname), &Person::surname>
>Масштаб этой проблемы незначителен на маленьком количестве тэгов. Но на маленьком наборе и не получится проверить насколько такое решение гибкое. Если добавить много разных тегов, в т.ч. и композитных, то даже на небольшом множестве из 3 полей может получится уже до 6 структур тегов и 12 реализаций operator() для каждой структуры, и весь этот код придётся писать вручную. Соответственно, в более сложных системах всё будет более печально.
Поэтому я не считаю такое решение достаточно гибким.
Да, вы меня верно поняли. Я ничего против boost решения не имею, просто иногда он недоступен. Обозначенные проблемы STL решения частично решаются написанием простеньких оберток и - о, ужас! - парочкой макросов. К сожалению, пишу с телефона и потому не могу привести пример.
Да, надо будет использовать С++14, но ему уже 8 лет, пора бы перейти уже :) А вот с неупорядоченными контейнерами и правда засада, но меня больше беспокоит скорость поиска в по std::set, который сортирует по одному полю, а искать будет по другому. С учётом устройства std::set время поиска будет линейным.
Я, возможно, понимаю о чём вы говорите, про компенсацию недостатков макросами. В моём понимании, их ещё можно компенсировать метапрограммированием. Но, с моей точки зрения, оба этих решения спорные, потому что в неумелых руках могут принести больше вреда, чем пользы. Среди рисков, использование таких механизмов языка с достаточной вероятностью может увеличить сложность разработки, отладки и может резко увеличить порог входа в решения на её основе.
Да и даже если обозначенные проблемы решаются, то всё-равно частично.
С boost все прекрасно, пока он работает. Но как только ты что-то неправильное с точки зрения буста пихаешь в шаблонные параметры - можно заплакать :)
Так что с одной стороны boost, конечно, сильно упрощает написание и даже чтение кода, но вот его модификация, особенно когда кто-то использовал boost-либу, которую ты плохо знаешь - это иногда бывает очень больно.
В остальном, да, я согласен с тем, что проблемы не решаются полностью и костылестроение не выход.
Как оказалось, я неверно понял механизм работы std::set<T>::is_transparent. Прошу прощения. Таким решением нельзя решить проблему [4](индексации по другим полям).
transparent компаратор позволяет сравнивать только по тому полю структуры, которое используется для определения отношения порядка в контейнере. В нашем случае, в методе operator()(Person const &, Person const &), это поле name. То есть is_transparent не решает проблему поиска по нескольким полям, а только позволяет выполнять поиск по значению, не создавая промежуточного пустого объекта Person (решает проблему [1]).
Если же говорить о том, что произойдёт если попробовать сделать индексацию по нескольким полям в transparent компараторе, то @0o00oo00o0 выяснил эмпирически, что поиск по контейнеру с таким компаратором ведёт себя нестабильно и может привести к падению:
mscv2019 программа падает, если заменить в find(41) из примера значение 41 на 40 или 60.
Поэтому решение на основе transparent компаратора становится не таким привлекательным.
В целом, интересный подход с boost. Похоже, multiindex инкапсулирует реализации нескольких ассоциативных структур для разных критериев поиска. В принципе, для себя можно было бы обойтись подобием в виде нескольких unordered_map, ведь именно map - не "карта", а сокращение от "mapping", - отображение.
В принципе, для себя можно было бы обойтись подобием в виде нескольких
unordered_map
Вероятнее всего, решение на основе нескольких STL-ных контейнеров будет проигрывать multi_index_container как по производительности, так и по сложности поддержки и расширения функциональности. Но если мы говорим про что-то не требовательное к этим параметрам, то почему-бы и нет :)
К сожалению сам Boost.MultiIndex остался "черным ящиком" - неизвестно внутреннее строение контейнера.
Я придумал схему, по которой сами объекты хранятся в "стандартном" контейнере, а "индекс" это объект `std::multiset<const Person*, comp>`, то есть в индексе лежит указатель на них.
Тут реализация: https://godbolt.org/z/ne895x73f, но не придумал как быстро искать объект по ключу, потому что std::find_if линейный
Возможно я неверно понял вашу проблему про линейный поиск, но предположу, что речь про то, что не получается придумать как искать элементы в вашем самопальном индексе быстрее. Конкретно насчёт вашей реализации, в ней каждый 'индекс', это аналог ordered_unique индекса из Boost.MultiIndex. Хоть и используется std::multiset, но специфика его элементов(указателей на значения из другого контейнера) такова, что два указателя на один и тот же объект точно не попадут в этот контейнер. Поэтому, если использовать std::multiset<T>::find то можно добиться логарифмического времени поиска.
Если же хочется реализовать аналоги для всех видов индексов, то для каждого из индексов в статье я привёл в аналогию STL-ный контейнер, и именно при помощи указанного контейнера можно реализовать аналог того или иного индекса.
Но в любом случае, ограничения по скорости поиска элемента по индексу всегда будут ограничены внутренним устройством аналогичного STL-ного контейнера. Поэтому, если вы хотите более быстрого поиска, то возможно вам нужен аналог hashed_unique индекса на основе std::unordered_set, с его средним константным временем поиска (чем меньше коллизий, тем вероятнее оно будет таким).
Предположим, что ты - С++ программист и тебе нужно создать справочник
Можно попросить какой-то реальный пример? Потому что после прочтения статьи у меня осталось впечатление, что решение задачи - БД, а вот такая структура данных - какой-то странный велосипед.
Меня также смущает, что предложенная структура данных требует обозначить индексацию при создании контейнера, хотя из условия задачи у меня сложилось впечатление, что этот критерий динамический
Можно попросить какой-то реальный пример?
В общем случае подойдет любая задача, в рамках которой:
Требуется реализовать отображение одного множества на другое по более чем 1 критерию.
И при этом вам не нужно(не требуется или накладно или избыточно) втаскивать только ради решения этой задачи интеграцию с БД.
осталось впечатление, что решение задачи - БД, а вот такая структура данных - какой-то странный велосипед.
В частности подойдут задачи, в рамках которых функционала обычного STL-ного контейнера уже не хватает, но трудозатратно пересесть сразу на БД.
Или же если требуется что-то вроде in-memory БД, но с функционалом, который покрывает boost::multi_index::multi_index_container(т.е. как минимум без транзакционной модели из коробки).
Если говорить конкретнее, то лично мне данный контейнер пригодился в реализации:
Биржевого стакана(в оперативном контейнере заявок и в снапшоте текущего состояния стакана).
Фильтрации tcp пакетов по нескольким признакам.
Фильтрации записей при парсе файлов разных форматов.
Меня также смущает, что предложенная структура данных требует обозначить индексацию при создании контейнера, хотя из условия задачи у меня сложилось впечатление, что этот критерий динамический
Способ индексации динамический с точки зрения изменения требований, а не с точки зрения runtime исполнения кода программы. То есть в данной статье не рассматривается механизм наиболее гибкого способа выпускать и применять патчи к программе(имею ввиду ситуацию, в которой новые требования к индексации появляются и должны быть учтены в уже выпущенной версии программы, в частности во время её исполнения на машине).
Гибкая индексация элементов в контейнере на С++ и при чём тут Boost.MultiIndex