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

Question

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

В 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и т.д. участники?

89

c++c++-faq c++14

Решение

Другие решения

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

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

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

29

_{Ниже приведены все копии-макароны из n3657.}

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

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

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

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

Q. так что набор по умолчанию теряет свои элементы find, count и т. д.

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

Цитировать Yakk,

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

и n3657,

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

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

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

17

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

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

4

Источник

Accepted Answer

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

Смотри Дитмар и ремиабель ответ.

и это меняет, как работают стандартные контейнеры?

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

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

На встрече в Бристоле 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’s N3421 который добавил «операторы алмазов» в C ++ 14. «Прозрачный функтор» — это тот, который принимает любые типы аргументов (которые не обязательно должны быть одинаковыми) и просто передает эти аргументы другому оператору. Такой функтор оказывается именно тем, что вам нужно для гетерогенного поиска в ассоциативных контейнерах, поэтому тип is_transparent был добавлен ко всем операторам diamond и использовался в качестве типа тега, чтобы указать, что новая функциональность должна быть включена в ассоциативных контейнерах. Технически, контейнерам не нужен «прозрачный функтор», только тот, который поддерживает вызов его с гетерогенными типами (например, 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 черта типа, которая относится к динамическому полиморфизму).

45