Эта небольшая статья для тех, кто имеет некоторое представление об ассоциативных контейнерах стандартной библиотеки 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++, получить в новом году возможность использовать наиболее современные стандарты языка и забыть про макросы.