Эта небольшая статья для тех, кто имеет некоторое представление об ассоциативных контейнерах стандартной библиотеки C++ (std::map, std::set и т.д.), но пока не использовал «множество» (std::set) в повседневной жизни. Этот контейнер позволяет наиболее изящно организовать коллекцию «самоидентифицируемых» объектов, не трубующих внешнего «ключа» для поиска. Но работа с std::set имеет свои особенности, о них и пойдет речь. Каких-то принциапиальных открытий статья не содержит, я просто решил собрать в одном месте некий минимально необходимый набор приемов для работы со множествами и, таким образом, несколько сэкономить время читателя, впервые решившего использовать «множества» в реальных проектах. Сразу оговорюсь, я сознательно снизил планку стандарта C++ до минимально необходимой, чтобы код, приведенный здесь, мог использоваться максимально широко (так что просьба не удивляться громоздким «устаревшим» конструкциям вроде enable_if).
... Отлично, std::set — это то, что нужно! Зачем мне std::map, если ключ уже находится внутри моего объекта! Такова была моя первая восторженная реакция после знакомства с «множеством» (std::set) стандартной библиотеки шаблонов C++. Это было давно... очень давно.
И тогда же (то есть очень давно) внимательное прочтение документации быстро привело меня к разочарованию. Этим «множеством» пользоваться невозможно. Unusable. Я надолго вычеркнул std::set из памяти, чтобы не питать лишних иллюзий. И да, пользовался вовсю std::map, «вынимая» копию ключа из объекта и записывая объект в std::map под этим же ключом. Некрасиво, не очень эффективно, но что делать.
Ситуация изменилась, начиная со стандарта C++14. Я сейчас расскажу подробнее об основных проблемах «множества» и о том, как они решаются в современном языке.
Проблем, собственно две (или полторы). Первая и главная — гетерогенныые запросы. Для поиска объекта во «множестве» (пусть экземпляр множества называется set) с помощью метода find(), раньше нужно было предъявить «образцовый» объект того же типа. И тогда, в случае успеха, метод find() вернет итератор, указующий на эквивалентный объект, содержащийся во множестве, или вернет set.end(), если такового объекта там нет. Но ведь «образцовый» объект может быть большим и «тяжелым», и конструировать его только ради того, чтобы просто спросить, содержится ли такой же во множестве, может оказаться весьма и весьма накладно.
Проблема вторая. Во множестве, в отличие от std::map, находятся неизменяемые элементы, то есть с квалификатором const. Это сделано сознательно, поскольку авторы стандартной библиотке сочли, что изменение объекта может нарушить отношение порядка, на котором основан set. Другими словами, если мы поместили два объекта a и b во множество, и объект a был «меньше» объекта b, а потом вдруг изменили объект a таким образом, что он станет «больше» объекта b, то наше множество непоправимо сломается.
Конечно, нарушать отношение порядка нельзя, но очень часто в объекте можно и нужно что-то поменять, какие-то поля, которые никак не учавствуют в операции сравнения, а представляют собой атрибуты, эволюционирующие в процессе жизни объекта.
Пусть, например, во множестве находятся объекты класса Person, описывающие работников некоей компании, упорядоченные и идентифицируемые по имени человека (или по имени и фамилии, для нашего примера неважно, пусть будет просто некая идентифицирующая строка). И есть в объекте поле «зарплата», которое может меняться со временем. Как же его изменить, если объект const?
Да очень просто, объявить «зарплату» с квалификатором mutable. Напомним, что mutable-поля разрешается менять, даже если объект неизменяемый (объявлен как const). А все методы, которые допустимо вызывать над обектом, находящемся во множестве, надо объявлять с квалификатором const (то есть метод, дескать, не меняет объект, а изменение mutable полей не в счет).
Итак, вторая проблема, проблема «неизменности» элементов множества, решается просто — квалификатором mutable для полей, допускающих изменения на протяжении жизни объекта в коллекции.
А как же первая проблема, проблема гетерогенных запросов? Как найти работника по имени, не конструируя «образцового» работника, а просто отправив в метод find() соответствующую строчку с именем?
Напомним определение std::set (отсюда)
template< class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> > class set;
Key — это наш класс-элемент множества (в нашем примере Key — это Person). А Compare — это функтор, реализующий операцию сравнения, точнее, операцию "строго меньше". Операция сравнения — это бинарный предикат, подчиняющийся аксиомам строгого слабого упорядочения (strict weak ordering).
Если читатель подзабыл эти аксиомы, напомню их минимальный состав: это (1) транзитивность и (2) требование к порожденному им отношению «несравнимости» (то есть предикату Uncomparable(a, b) = !(a < b) && !(b < a)) быть отношением эквивалентности (рефлексивным, транзитивным и симметричным).
Фактически строгое слабое отношение порядка является также антирефлексивным (никогда не бывает a < a) и антисимметричным (никогда не бывает a < b и b < a одновременно), но это, как нетрудно убедиться, уже следствия двух первых аксиом. Заметим, что просто потребовать от предиката сравнения быть транзитивным, антирефлексивным и антисимметричным недостаточно: отношение «несравнимости» при этом может не оказаться отношением эквивалентности (соответствующий пример нетрудно привести).
Впрочем, в реальной жизни «множеств» проверка аксиом может и не потребоваться, поскольку сравнение элементов множества часто сводится к уже известной операции сравнения более простых объектов («фактических ключей»), уже содержащихся в элемантах. В этом случае реализовать операцию сравнения совсем несложно. Например,
// Элемент множества: struct Person { std::string name; mutable unsigned salary = 0; }; // Операция сравнения: struct ComparePersons { // Сравниваем две персоны по имени в лексикографическом порядке. bool operator()(const Person& a, const Person& b) {return a.name < b.name;} }; std::set<Person, ComparePersons> persons; // ... auto it_vasya = persons.find(Person{"Vasya"}); // попробуем найти Васю во множестве
Пока запрос не гетерогенный. Нам пришлось сконструировать для запроса «образцовую» персону Person{"Vasya"}. Чтобы спрашивать просто по имени, добавим в наш функтор сравнения две операции сравнения персоны со строками:
struct ComparePersons { // сравнение персоны с персоной (это уже было): bool operator()(const Person& a, const Person& b) const {return a.name < b.name;} // сравнение строки с персоной: bool operator()(const std::string& a, const Person& b) const {return a < b.name;} // сравнение персоны со строкой: bool operator()(const Person& a, const std::string& b) const {return a.name < b;} };
Возможность сравнивать элементы коллекции не только между собой, но и с посторонними предметами, появилась в стандарте C++14. Теперь мы умеем сравнивать не только персону с персоной, но и персону со строкой, а также строку с персоной.
Что же, теперь можно просто спросить persons.find(std::string("Vasya")), не конструируя образцового Васю?
Пока что нет. Нужно добавить специальное заклинание. Разработчики стандарта убоялись побочных эффектов в существующем коде и требуют явно разрешить гетерогенные операции сравнения нашего объекта с посторонними предметами (в данном случае со строкой std::string). Заклинание произносится внутри функтора сравнения и звучит так:
using is_transparent = some_type; // совершенно неважно какой тип
обычно, не мудрствуя, пишут void:
using is_transparent = void;
Немного о причинах появления заклинания is_transparent. Предположим, мы имеем множество строк, но вызываем метод find() не с объектом std::string, а с «сишной» строкой:
std::set<std::string> sset; // ... auto it = sset.find("Vasya");
До эпохи гетерогенных запросов аргумент "Vasya" был бы автоматически сконвертирован (один раз!) во временный объект std::string("Vasya"), и алгоритм поиска использовал бы этот временный объект для дальнейших сравнений. Но как только мы разрешаем гетерогенные запросы, строковый литерал "Vasya" будет отправлен алгоритмом функции find() прямиком в функтор сравнения, авось функтор сумеет гетерогенно сравнить этот литерал с населением нашего множества, состоящего из объектов типа std::string. А функтор сравнения, представьте, окажется не авось! Не умеет он сравнивать std::string со строковым литералом! И ладно бы возникла ошибка компиляции, её нетрудно пофиксить. Намного хуже, если уже внутри алгоритма функции find() начнут происходить указанные конверсии, втихую, при каждом сравнении! А этих сравнений, между прочим, логарифм от размера множества. То есть старый код как работал, так как будто бы и работает, только его производительность катастрофически упала!
Вот и потребовалось заклинание is_transparent, которым функтор сравнения торжественно обещает уметь гетерогенно сравнивать. Метод find() поручит ему гетерогенное сравнение только при наличии такого обещания-заклинания. Кстати, подобные «умелые» функторы обычно содержат внутри шаблоны операторов (таков, например, функтор std::less), так что конверсии «втихую» не случится, а случится ошибка компиляции, в том случае, если функтор действительно не сможет что-либо сравнить (напомним, что при выводе аргументов «шаблонной» функции автоматические конверсии не принимаются во внимание).
Итак, окончательно наш функтор сравнения для персоны выглядит так:
struct ComparePersons { using is_transparent = void; // заклинание, призывающее бога сравнения // разрешить сравнения с посторонними предметами bool operator()(const Person& a, const Person& b) {return a.name < b.name;} bool operator()(const std::string& a, const Person& b) {return a < b.name;} bool operator()(const Person& a, const std::string& b) {return a.name < b;} };
И теперь, наконец, мы можем позвать Васю просто по имени:
std::set<Person, ComparePersons> persons; // ... auto it_vasya = persons.find(std::string("Vasya"));
и повысить ему зарплату:
if(it_vasya != persons.end()){ vasya->salary++; // напомним, salary объявлена как mutable, // поэтому модификация допустима. }
Но будьте осторожны, не скормите случайно методу find() вместо std::string сишную строку! То есть в этом случае всё будет работать, но медленнее. Метод find() поверит обещанию функтора ComparePersons «уметь» гетерогенно сравнивать и будет отправлять ему сишную строку для сравнений, в её первозданном «сишном» виде. Тут-то и будут происходить те самые конверсии, о которых мы уже говорили. Наш ComparePersons торжественно пообещал то, что на самом деле вроде как бы умеет, да не совсем...
В качестве дополнения к изложенному о гетерогенных запросах можно рекомендовать неплохую статью на Хабре. В комментариях к ней можно найти также кое-что полезное о гетерогенных запросах в неупорядоченных контейнерах, которые здесь нами не рассматриваются (хотя аналогичные приёмы применимы и к ним тоже).
«Приручив» множества, вы, скорее всего, будете их использовать довольно часто. А если их использовать часто, захочется вообще избавиться от рутины определения функтора сравнения, по крайней мере в типичном случае, когда сравнение производится по некоему полю (члену класса), выполняющему роль ключа. Наиболее изящно, не прибегая к макросам, это можно сделать, начиная с со стандарта C++17. Заодно мы устраним описанную выше ловушку с деградацией производительности.
Итак, попробуем автоматически сгенерировать наш гетерогенный функтор сравнения, имея класс-элемент множества, а также член этого класса, фактически выполняющий роль ключа. Еще, в качестве параметра, полезно задать «базовую» операцию сравнения фактических ключей, поскольку может оказаться, что их умолчательное сравнение по std::less по каким-то причинам не подойдет.
Причины, по которым не подходит стандартное сравнение, возникают довольно часто. Например, если коллекция с (фактическими) строковыми ключами должна быть нечувствительна к регистру (case insensitive). Другой пример: в классе std::set есть две очень полезные функции, upper_bound() и lower_bound(), обе, как и метод find(), также поддерживают гетерогенные запросы. Однако, вопреки названию, lower_bound() возвращает не нижнюю, а тоже верхнюю грань, только нестрогую (то есть может вернуть и эквавалентный объект, если таковой нашелся во множестве). А вот функции, возвращающих «настоящую» нижнюю грань, то есть ближайший объект, меньший запрашиваемого ключа (или меньший либо эквивалентный в нестрогом случае) в стандартной библиотеке вообще нет. Поэтому приходится использовать std::set с инвертированным стандартным сравнением, чтобы upper_bound() возвращала «ближайший меньший» в стандартном смысле.
Но вернемся к нашему проектируемому шаблону-функтору гетерогенного сравнения элементов множества. Назовём этот функтор CompareByMember, поскольку его идея состоит в том, чтобы свести сравнение с элементом множества к сравнению с одним из полей-членов класса-элемента. Реализовать такое сравнение можно, например, так:
#include <set> // Вспомогательный шаблон, превращающий тип void в std::less, // а любой другой тип оставляющий нетронутым. // Используется для превращения умолчательного void в стандартный сравниватель. template<typename KeyType, typename C> struct CompareFor{using type = C;}; template<typename KeyType> struct CompareFor<KeyType, void>{using type = std::less<>;}; // Вспомогательный шаблон, проверяющий поддержку гетерогенных сравнений // функтором сравнения CompareFunc: template<typename CompareFunc, typename _sfinae = void> struct HasIsTransparent : std::false_type{}; template<typename CompareFunc> struct HasIsTransparent<CompareFunc, typename std::void_t<typename CompareFunc::is_transparent> > : std::true_type{}; // А вот и сам функтор CompareByMember, сводящий сравнение элемента множества // к сравнению одного из полей этого элемента. Но пока эта общая декларация шаблона, // которая почти ничего не делает (фактическая реализация будет в специализации, чуть ниже). template< auto p_member, // (C++17) В специализации auto превратится в указатель на член класса typename BaseKeyCompare = void > struct CompareByMember{}; // Наконец, специализация функтора CompareByMember, // выполняющая всю нужную работу: template< typename ElementType, // (выводится из p_member) typename KeyType, // (выводится из p_member) KeyType (ElementType::*p_member), // Указатель на член класса, //выполняющий роль фактического ключа typename BaseKeyCompare // Функтор сравнения фактических ключей > struct CompareByMember<p_member, BaseKeyCompare> { using is_transparent = void; // заклинание, разрешающее сравнение с посторонними предметами using key_type = KeyType; // Тип базового сравнивателя фактических ключей, // то есть это или BaseKeyCompare или std::less<>, если первый оказался void: using base_key_compare_t = typename CompareFor<KeyType, BaseKeyCompare>::type; // этот навороченный using разрешается в тип элемента множества (ElementType), // если нечто (CompareWith), с чем мы собираемся сравнить элемент множества, // является чем-то посторонним (само не является элементом) // и при этом более или менее подходит для сравнения: template<typename CompareWith> using ElementComparedWith = typename std::enable_if< // CompareWith должен быть посторонним предметом: !std::is_base_of<ElementType, CompareWith>::value && // и... ( // либо базовый сравниватель поддерживает // гетерогенные сравнения HasIsTransparent<base_key_compare_t>::value // либо разрешается сравнивать только с типом // фактического ключа и больше ни с чем // (мы избегаем подкапотных конверсий) || std::is_base_of<key_type, CompareWith>::value ) , ElementType >::type; // сравнение элементов между собой: bool operator() (const ElementType& a, const ElementType& b) const { return scomp_(a.*p_member, b.*p_member); } // Сравнение постороннего предмета с элементом множества: template<typename A> bool operator() ( const A& akey, // это посторонний предмет // А это элемент, но при условии, что предмет akey действительно //посторонний и подходящий для сравнения: const ElementComparedWith<A>& b ) const { return scomp_(akey, b.*p_member); } // Сравнение элемента множества с посторонним предметом: template<typename B> bool operator() ( const ElementComparedWith<B>& a, const B& bkey ) const { return scomp_(a.*p_member, bkey); } // Полезная функция, позволяющая пользователю забыть, какое поле класса-элемента // выполняет роль ключа: static const key_type& get_key_of(const ElementType& e){return e.*p_member;}; private: base_key_compare_t scomp_; // сравниватель фактических ключей };
Теперь множество с гетерогенным сравнением определить совсем просто:
#include <string> #include <iostream> // Элемент множества: struct Person { std::string name; mutable unsigned salary = 0; }; void test(){ std::set<Person, CompareByMember<&Person::name> >persons; // вот и всё: // это множество уже поддерживает гетерогенные запросы persons.insert({"Vasya", 100}); auto it = persons.find("Vasya"); // попробуем найти Васю во множестве по имени if(it != persons.end()){ it->salary++; std::cout << "\n found: " << it->name << " salary: " << it->salary << "\n"; } }
Стоит заметить, что приведенная реализация CompareByMember «наследует» возможности гетерогенных запросов «базового сравнивателя» BaseKeyCompare. Например, если «фактический ключ» — стандартная строка std::string, и базовый сравниватель умеет ее гетерогенно сравнивать с «сишной» строкой char* (закрытой нулём), то и наш элемент множества также будет сравниваться с «сишной» строкой. Напомним, что функтор сравнения std::less<void> это умеет, ибо он просто вызывает оператор «меньше» над аргументами, а опреатор «меньше», в свою очередь, в стандартной библиотеке уже имеет «гетерогенный» вариант сравнения «плюсовой» и «сишной» строк.
Если вы (увы) ограничены стандартом C++14, то данную реализацию тоже можно взять за основу, только шаблон CompareByMember придется определить от всех четырех параметров (как в специализации), а вывести два из них (тип элемента множества и тип «фактического ключа») уже не удастся. Впрочем, дело можно поправить макросом, принимающим имя класса-элемента ElementType и имя поля-фактического ключа key_name и через decltype(std::declval().key_name) подставляющего полученный таким образом тип фактического ключа в шаблон.
Также, формально говоря, используемый нами шаблон std::void_t<...> относится к стандарту C++17, но его нетрудно заменить при необходимости на собственную декларацию
template< class... > using void_t = void;
ибо ничего специфичного для стандарта C++17 в этой декларации нет, просто её включили в стандарт, скажем так, поздновато...
Впрочем, желаю всем читателям, программирующим на C++, получить в новом году возможность использовать наиболее современные стандарты языка и забыть про макросы.
[UPD]
В комментариях был озвучен еще один рецепт «приручения» множества, а именно: предусмотреть некий «легковесный» конструктор «тяжелого» (в общем случае) элемента множества и передавать этот «облегчённый» элемент в поисковае методы std::set, не заморачиваясь вообще гетерогенными запросами. Соглашусь, вариант рабочий и достойный упоминания, хотя и вызывающий вполне понятную эстетическую неудовлетворённость.
Впрочем, эстетическую неудовлетворённость, как оказалось, можно удовлетворить, не поступившись самой идеей. Вместо «легкого» конструктора можно определить специальный «легкий» класс-ключ и унаследовать «тяжелый» класс-элемент от этого «легкого» ключа. Для класса-ключа определяется простейший функтор сравнения. Заклинание is_transparent произносится лишь с целью разрешить сравнение класса-ключа с наследниками этого класса (к которым относится сам «тяжелый» элемент множества).
Это не равноценная замена приведенного выше шаблона CompareByMember, поскольку более разнообразные гетерогенные запросы не поддерживаются (если, конечно, в нашем примере не унаследовать элемент множества напрямую от std::string, на что я бы, пожалуй, не решился). Но в целом вариант приемлемый. Его преимущество — отсутствие зависимостей от какого-либо дополнительного кода.
struct PersonKey { std::string name; }; struct ComparePersonKey { // Разрешаем посторонние сравнения (ради сравнения с наследниками PersonKey): using is_transparent = void; bool operator()(const PersonKey& a, const PersonKey& b) const {return a.name < b.name;} }; struct Person : public PersonKey { mutable unsigned salary = 0; }; void myset_test(){ std::set<Person, ComparePersonKey> persons; persons.insert({"Vasya", 100}); // попробуем найти Васю во множестве по "легкому" ключу: auto it = persons.find(PersonKey{"Vasya"}); if(it != persons.end()){ it->salary++; std::cout << "\n found: " << it->name << " salary: " << it->salary << "\n"; } }
