Что такое прозрачные компараторы?

106

В C ++ 14 ассоциативные контейнеры, похоже, изменились с C ++ 11 - [associative.reqmts] / 13 говорит:

Шаблоны функций - членов find, count, lower_bound, upper_bound, и equal_rangeне должен участвовать в разрешении перегрузки , если тип Compare::is_transparentне существует.

Какова цель сделать компаратор «прозрачным»?

C ++ 14 также предоставляет такие шаблоны библиотек:

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

Так, например, std::set<T, std::less<T>>было бы не иметь прозрачный компаратор, но std::set<T, std::less<>> будет иметь один.

Какую проблему это решает и меняет ли это принцип работы стандартных контейнеров? Например, параметры шаблона std::setпо - прежнему Key, Compare = std::less<Key>, ..., так же набор по умолчанию потеряет find, countи т.д. член?

Керрек С.Б.
источник
Например, см. Это описание cppreference . И сейчас я чувствую себя глупо, потому что
замечаю
5
Возможно, связано: stackoverflow.com/questions/18939882/…
cppreference также имеет аннотацию
Cubbi 01

Ответы:

60

Какую проблему это решает,

См ответ Дитмар в и ответ remyabel в .

и меняет ли это принцип работы стандартных контейнеров?

Нет, не по умолчанию.

Новые перегрузки шаблонов функций-членов findи т. Д. Позволяют использовать тип, сопоставимый с ключом контейнера, вместо использования самого типа ключа. См. N3465 Хоакина Му Лопеса Муньоса для обоснования и подробного, тщательно написанного предложения по добавлению этой функции.

На встрече в Бристоле LWG согласилась, что функция гетерогенного поиска полезна и желательна, но мы не могли быть уверены, что предложение Хоакина будет безопасным во всех случаях. Предложение N3465 вызвало бы серьезные проблемы для некоторых программ (см. Раздел « Влияние на существующий код »). Хоакин подготовил обновленный черновой вариант предложения с некоторыми альтернативными реализациями с разными компромиссами, что было очень полезно, помогая LWG понять плюсы и минусы, но все они рисковали каким-то образом нарушить некоторые программы, поэтому не было единого мнения о добавлении этой функции. Мы решили, что, хотя добавлять эту функцию безоговорочно было бы небезопасно, было бы безопасно, если бы она была отключена по умолчанию и была только «включаться».

Ключевым отличием предложения N3657 (которое было доработкой в ​​последнюю минуту мной и STL на основе N3465 и более позднего неопубликованного проекта Хоакина) было добавление is_transparentтипа в качестве протокола, который можно использовать для выбора новой функциональности.

Если вы не используете «прозрачный функтор» (т.е. тот, который определяет is_transparentтип), тогда контейнеры будут вести себя так же, как и всегда, и это по-прежнему по умолчанию.

Если вы решите использовать std::less<>(что является новым для C ++ 14) или другой тип «прозрачного функтора», вы получите новую функциональность.

Использование std::less<>легко с помощью шаблонов псевдонимов:

template<typename T, typename Cmp = std::less<>, typename Alloc = std::allocator<T>>
  using set = std::set<T, Cmp, Alloc>;

Название is_transparentпроисходит от STL N3421, который добавил «алмазные операторы» в C ++ 14. «Прозрачный функтор» - это тот, который принимает любые типы аргументов (которые не обязательно должны быть одинаковыми) и просто перенаправляет эти аргументы другому оператору. Такой функтор оказывается именно тем, что вам нужно для гетерогенного поиска в ассоциативных контейнерах, поэтому этот тип is_transparentбыл добавлен ко всем операторам ромба и использовался как тип тега, чтобы указать, что новые функции должны быть включены в ассоциативных контейнерах. Технически контейнерам не нужен «прозрачный функтор», только тот, который поддерживает его вызов с разнородными типами (например, pointer_compтип в https://stackoverflow.com/a/18940595/981959 не является прозрачным согласно определению STL,pointer_comp::is_transparentпозволяет использовать его для решения проблемы). Если вы когда-либо выполняете поиск только std::set<T, C>с ключами типа Tили intтогда Cнужно вызывать только аргументы типа Tи int(в любом порядке), это не обязательно должно быть действительно прозрачным. Мы использовали это имя отчасти потому, что не смогли придумать лучшего имени (я бы предпочел, is_polymorphicпотому что такие функторы используют статический полиморфизм, но уже есть std::is_polymorphicхарактеристика типа, которая относится к динамическому полиморфизму).

Джонатан Уэйкли
источник
3
Привет, а вы были тем, кому STL сказал: «Конечно, вы можете делать вывод аргументов шаблона в своей голове» в разговоре, на который ссылается Woolstar?
Kerrek SB 04
10
Нет, меня там не было, но есть люди с гораздо более совместимыми компиляторами в голове, чем у меня :)
Джонатан Уэйкли
Я предполагаю, что термин «оператор ромба» упоминается <>в связанном предложении, но это предложение не вводило <>- это существующий синтаксис для пустого списка параметров шаблона. "Функторы алмазных операторов" были бы немного менее запутанными.
Qwertie
33

В C ++ 11 есть не шаблоны членов find(), lower_bound()и т.д. То есть, ничего не теряется этим изменением. Шаблоны элементов были введены в n3657, чтобы можно было использовать гетерогенные ключи с ассоциативными контейнерами. Я не вижу конкретного примера, где это было бы полезно, кроме хороших и плохих примеров!

is_transparentИспользование предназначено , чтобы избежать нежелательных переходов. Если бы шаблоны элементов были неограниченными, существующий код мог бы напрямую проходить через объекты, которые были бы преобразованы без шаблонов элементов. Пример использования n3657 - это поиск объекта в a std::set<std::string>с помощью строкового литерала: с определением C ++ 11 std::stringобъект создается при передаче строковых литералов соответствующей функции-члену. С изменением можно напрямую использовать строковый литерал. Если базовый объект функции сравнения реализован исключительно в терминах std::string, это плохо, потому что теперь a и строковый литерал, это может избежать создания временного объекта.std::string будет создаваться для каждого сравнения. С другой стороны, если базовый объект функции сравнения может приниматьstd::string

Вложенный is_transparentтип в объекте функции сравнения предоставляет способ указать, следует ли использовать шаблонную функцию-член: если объект функции сравнения может работать с разнородными аргументами, он определяет этот тип, чтобы указать, что он может эффективно работать с различными аргументами. Например, новые объекты операторной функции просто делегируются operator<()и утверждают, что они прозрачны. Тот, по крайней мере, работает для std::stringтех , у кого перегрузок меньше, чем операторов, принимающих в char const*качестве аргумента. Поскольку эти функциональные объекты также являются новыми, даже если они делают неправильную вещь (например, требуют преобразования для какого-то типа), это, по крайней мере, не будет тихим изменением, приводящим к снижению производительности.

Дитмар Кюль
источник
Спасибо - см. Мой комментарий по другому вопросу: получаете ли вы прозрачное поведение по умолчанию?
Kerrek SB 01
8
@KerrekSB: прозрачное поведение включается, если is_transparentоно определено в объекте функции сравнения в соответствии с пунктом 13 раздела 23.2.4 [associative.reqmts]. Объекты функции сравнения по умолчанию std::less<Key>соответствуют 23.4.2 [associative.map.syn] и 23.4. 3 [associative.set.syn]. Согласно 20.10.5 [сравнение] пункта 4 общий шаблон для std::less<...>ничего не определить вложенный тип , is_transparentно std::less<void>специализация делает. То есть нет, по умолчанию вы не получаете прозрачный оператор.
Дитмар Кюль,
У вас есть идеи по названию? Я имею ввиду почему is_transparent?
Plasmacel
Вам нужен «конкретный пример, где это полезно»? Вот мой вариант использования
spraff
19

Далее следует вся копипаста от n3657 .

В. Какова цель сделать компаратор «прозрачным»?

A. Функции поиска в ассоциативном контейнере (find, lower_bound, upper_bound, equal_range) принимают только аргумент key_type, требуя от пользователей конструировать (неявно или явно) объект key_type для выполнения поиска. Это может быть дорогостоящим, например создание большого объекта для поиска в наборе, когда функция компаратора просматривает только одно поле объекта. Пользователи сильно хотят иметь возможность выполнять поиск с использованием других типов, сопоставимых с key_type.

В. Какую проблему это решает

A. LWG высказывала опасения по поводу следующего кода:

std::set<std::string> s = /* ... */;
s.find("key");

В C ++ 11 это создаст единый временный std :: string, а затем сравнит его с элементами, чтобы найти ключ.

С изменением, предложенным N3465, функция std :: set :: find () будет неограниченным шаблоном, который будет передавать const char * в функцию компаратора std :: less, которая создаст временную std :: string для каждое сравнение. LWG посчитала эту проблему производительности серьезной проблемой. Функция шаблона find () также предотвратит нахождение NULL в контейнере указателей, что приведет к тому, что ранее действующий код больше не будет компилироваться, но это рассматривалось как менее серьезная проблема, чем тихая регрессия производительности

Q. меняет ли это принцип работы стандартных контейнеров?

A. Это предложение изменяет ассоциативные контейнеры внутри и путем перегрузки функций-членов поиска с помощью шаблонов функций-членов. Никаких языковых изменений.

В. Значит, набор по умолчанию теряет свои члены find, count и т. Д.

A. Почти весь существующий код C ++ 11 не затрагивается, поскольку функции-члены отсутствуют, если только новые функции библиотеки C ++ 14 не используются в качестве функций сравнения.

Процитировать Якка ,

В C ++ 14 std :: set :: find является функцией шаблона, если существует Compare :: is_transparent. Тип, который вы передаете, не обязательно должен быть Key, он просто эквивалентен вашему компаратору.

и n3657,

Добавить параграф 13 в 23.2.4 [associative.reqmts]: шаблоны функций-членов find, lower_bound, upper_bound и equal_range не должны участвовать в разрешении перегрузки, если тип Compare :: is_transparent не существует.

n3421 представляет собой пример «прозрачных операторных функторов» .

Полный код здесь .

Сообщество
источник
1
Действительно ли std::set<std::string>польза от «прохождения char const *через», или вам нужно сделать это std::set<std::string, std::less<>>?
Kerrek SB 01
@Kerrek Я думаю, что "передача char const *" была проблемой, которую они пытались избежать, если я не ошибаюсь. Посмотрите на формулировку:With the change proposed by N3465 the std::set::find() function would be an unconstrained template which would pass the const char* through to the comparator function, std::less<std::string>, which would construct a std::string temporary for every comparison. The LWG considered this performance problem to be a serious issue.
Ваша и моя цитата из параграфа 13 говорят об обратном: «если тип не существует / не существует» ...?!
Kerrek SB 01
4
@KerrekSB, это моя вина, N3657 должен был сказать «существует», но я написал «не существует» ... это была запоздалая статья, написанная в последнюю минуту. Проект стандарта правильный.
Джонатан Уэйкли,
3
Да, было бы проще процитировать то, что я имел в виду, чтобы сказать, а не то, что я сказал в то время :)
Джонатан Уэйкли
7

Стефан Т. Лававей рассказывает о проблемах, при которых компилятор продолжает создавать временные библиотеки, и о том, как его предложение прозрачных операторных функторов решит эту проблему в C ++ 1y.

GoingNative 2013 - Не помогайте компилятору (примерно на отметке часа)

шерстяная звезда
источник