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

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

Answer 1

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

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

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

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

Новый шаблон функции-члена перегружает find и т.д. позволяют использовать тип, сопоставимый с ключом контейнера, вместо использования самого типа ключа. См. N3465 от Joaquín Mª López Muñoz для обоснования и подробного, тщательно написанного предложения по добавлению этой функции.

На встрече в Бристоле 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 происходит от ST34 N3421, который добавил "операторы алмазов" в C++14. "Прозрачный функтор" - это тот, который принимает любые типы аргументов (которые не должны быть одинаковыми) и просто перенаправляет эти аргументы другому оператору. Такой функтор оказывается именно тем, что вам нужно для гетерогенного поиска в ассоциативных контейнерах, поэтому тип is_transparent был добавлен ко всем операторам diamond и использовался в качестве типа тега, чтобы указать, что новая функциональность должна быть включена в ассоциативных контейнерах. Технически, контейнерам не нужен "прозрачный функтор", только тот, который поддерживает вызов его с гетерогенными типами (например, pointer_comp введите /questions/6519255/poisk-neobrabotannyih-ukazatelej-dlya-naborov-uniqueptrs/6519275#6519275 не прозрачный в соответствии с определением STL, но определяющий pointer_comp::is_transparent позволяет использовать его для решения проблемы). Если вы только когда-либо искать в вашем std::set<T, C> с ключами типа T или же int затем C должен вызываться только аргументами типа T а также int (в любом порядке), он не должен быть действительно прозрачным. Мы использовали это имя отчасти потому, что не могли придумать лучшего имени (я бы предпочел is_polymorphic потому что такие функторы используют статический полиморфизм, но уже есть std::is_polymorphic черта типа, которая относится к динамическому полиморфизму).

Answer 2

В 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* в качестве аргумента. Поскольку эти функциональные объекты также являются новыми, даже если они делают неправильные вещи (т.е. требуют преобразования для некоторого типа), это, по крайней мере, не будет тихим изменением, приводящим к снижению производительности.

Answer 3

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

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

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

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

О. У 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. это меняет работу стандартных контейнеров

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

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

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

Процитирую Якка,

В 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 приведен пример "Прозрачные операторные функторы".

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

Answer 4

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

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