Как с концепциями выбирается лучший шаблон ограниченной функции? - PullRequest
Новая
       71

Как с концепциями выбирается лучший шаблон ограниченной функции?

3 голосов
/ 06 мая 2020

В презентации концепций было показано что-то вроде этого: 

template <bidirectional_iterator It>
void sort(It begin, It end);            // #1

template <random_access_iterator It>
void sort(It begin, It end);            // #2

std::list<int> l{};
sort(l.begin(), l.end()); // #A  -> calls #1

std::vector<int> v{};
sort(v.begin(), v.end()); // #B  -> calls #2

Для вызова #A это просто: только sort #1 жизнеспособен, поскольку ограничение random_access_iterator не выполняется поэтому он вызывает #1.

Но для вызова #B оба sort являются жизнеспособными, так как оба ограничения (random_access_iterator и bidirectional_iterator удовлетворены). Так как же выбрать «более эффективный» sort #2? Ведущий сказал: «Просто работает».

1 Ответ

3 голосов
/ 06 мая 2020

Итак, как выбирается «более эффективный» sort #2?

Он работает, потому что существует частичное упорядочивание ограничений (определяется включает отношение ).

sort #2 (один с randomaccess_iterator) более ограничен , чем sort #1 (тот, у которого bidirectional_iterator), потому что randomaccess_iterator Subumes bidirectional_iterator: 

template <class It>
concept bidirectional_iterator = requires /*...*/;

template <class It>
concept randomaccess_iterator = bidirectional_iterator<It> && requires /*...*/;

Чтобы эта работа учитывала ограничения на уровне языка союзов и дизъюнкций.

Процесс определения того, является ли объявление более или менее ограниченным, чем другой выглядит так: Нормализация ограничений -> ограничение включает отношение -> (определяет) частичное упорядочение ограничений -> (определяет) объявления являются более / менее ограничивающими отношениями.

Упрощенно, нормализация - это подстановка параметров шаблона концептов в сопоставлении параметров ограничений.

Пример: 

template <class T> concept integral        = std::is_integral_v<T>;
template <class T> concept signed_integral = integral<T> && std::is_signed_v<T>;
template <class T> concept integral_4      = integral<T> && sizeof(T) == 4;

void foo_1(integral auto)        // #0
void foo_1(signed_integral auto) // #1 
void foo_1(integral_4 auto)      // #2

auto test1()
{
    foo_1(std::uint16_t{});  // calls #0
    foo_1(std::uint32_t{});  // calls #2

    foo_1(std::int16_t{});   // calls #1
    //foo_1(std::int32_t{}); // error ambiguous between #1 and #2
}
  • нормальная форма integral это std::is_integral_v<T>
  • нормальная форма signed_integral равно std::is_integral_v<T> ∧ std::is_signed_v<T>

  • в нормальной форме integral_4 равно std::is_integral_v<T> ∧ sizeof(T) == 4

  • signed_integral включает integral

  • integral_4 включает integral

  • #1 больше ограничений, чем #0

  • #2 больше ограничение, чем #0

Пример: 

template <class T> concept integral            = std::is_integral_v<T>;
template <class T> concept signed_integral_sad = std::is_integral_v<T> &&
                                                     std::is_signed_v<T>;
template <class T> concept integral_4_sad      = std::is_integral_v<T> && sizeof(T) == 4;


void foo_2(integral auto)             // #0
void foo_2(signed_integral_sad auto); // #1
void foo_2(integral_4_sad auto);      // #2


auto test2()
{
    foo_2(std::uint16_t{});   // calls #0
    //foo_2(std::uint32_t{}); // error ambiguous between #0 and #2

    //foo_2(std::int16_t{});  // error ambiguous between #0 and #1
    //foo_2(std::int32_t{});  // error ambiguous between #0, #1 and #2
}
  • нормальная форма integral это std::is_integral_v<T>
  • нормальная форма signed_integral_sad равно std::is_integral_v<T> ∧ std::is_signed_v<T>
  • нормальная форма integral_4_sad это std::is_integral_v<T> ∧ sizeof(T) == 4

Однако есть правило

§13.5 .1.2 Atomi c ограничения [temp.constr.atomic]

Два ограничения atomi c, e1 и e2, идентичны, если они сформированы из одного и того же внешнего вида одного и того же выражения [...]

This означает, что выражения std::is_integral_v<T> atomi c из трех нормальных форм не идентичны между собой, потому что они не были образованы из одного и того же выражения. Итак:

  • нет включает отношение
  • нет дополнительных ограничений отношения

Что приводит к дополнительной неоднозначности.

§ 13.5.1 Ограничения [temp.constr.constr]

  1. Ограничение представляет собой последовательность логических операций и операндов, определяющую требования к аргументам шаблона. Операнды логической операции - это ограничения. Существует три различных типа ограничений:

    • (1.1) конъюнкции (13.5.1.1)
    • (1.2) дизъюнкции (13.5.1.1) и
    • ( 1.3) atomi c ограничения (13.5.1.2).

§13.5.1.1 Логические операции [temp.constr.op]

  1. Есть две бинарные логические операции над ограничениями: конъюнкция и дизъюнкция. [Примечание: эти логические операции не имеют соответствующего синтаксиса C ++. Для наглядности соединение пишется с помощью символа ∧, а дизъюнкция - с помощью символа ∨]

§13.5.3 Нормализация ограничений [temp.constr .normal]

  1. Нормальная форма выражения E - это ограничение (13.5.1), которое определяется следующим образом:

    • (1.1 ) Нормальная форма выражения ( E ) - это нормальная форма E.
    • (1.2) Нормальная форма выражения E1 || E2 - это дизъюнкция (13.5.1.1) нормальных форм E1 и E2.
    • (1.3) Нормальный форма выражения E1 && E2 - это соединение нормальных форм E1 и E2.
    • (1.4) Нормальная форма идентификатора концепции C<A1, A2, ..., An> является нормальной формой ограничения -выражение C после замены A1, A2, ..., An на соответствующие параметры шаблона C в сопоставлениях параметров в каждом ограничении atomi c. [...]
    • (1.5) Нормальная форма любого другого выражение E - это ограничение atomi c, выражение которого равно E, а отображение параметров - отображение идентичности.

  2. Процесс получения нормальной формы выражение-ограничение называется нормализацией.

§13.5.4 Частичное упорядочение по ограничениям [temp.constr.order]

  1. Ограничение P включает ограничение Q тогда и только тогда, когда для каждого дизъюнктивного предложения Pi в дизъюнктивной нормальной форме 130 из P, Pi включает каждое конъюнктивное предложение Qj в конъюнктивную нормальную форму 131 из Q, где

    • (1.1) дизъюнктивное предложение Pi включает конъюнктивное предложение Qj тогда и только тогда, когда существует ограничение atomi c Pia в Pi, для которого существует ограничение atomi c Qjb в Qj такое, что Pia включает Qjb, и
    • (1.2) atomi c ограничение A включает другой атом * 13 14 * ограничение B тогда и только тогда, когда A и B идентичны, используя правила, описанные в 13.5.1.2.

    [Пример: Пусть A и B будут атомами c ограничения (13.5.1.2). Ограничение A ∧ B включает A, но A не включает A ∧ B. Ограничение A включает A ∨ B, но A ∨ B не включает A. Также обратите внимание, что каждое ограничение включает себя. - конец примера]

  2. [Примечание: отношение подчинения определяет частичный порядок ограничений. Это частичное упорядочение используется для определения

    • (2.1) наилучшего жизнеспособного кандидата не шаблонных функций (12.4.3),
    • (2.2) адреса нешаблонных функций. function (12.5),
    • (2.3) сопоставление аргументов шаблона шаблона (13.4.3),
    • (2.4) частичное упорядочение специализаций шаблона класса (13.7.5.2) и
    • (2.5) частичный порядок шаблонов функций (13.7.6.2).

- конец примечания]

Объявление D1 по крайней мере так же ограничено, как объявление D2, если

  • (3.1) D1 и D2 являются ограниченными объявлениями и D1 связанные ограничения включают ограничения D2; или
  • (3.2) D2 не имеет связанных ограничений.

Объявление D1 более ограничено, чем другое объявление D2, когда D1 как минимум так же ограничен, как D2, а D2 не как минимум как D1.

130) Ограничение имеет дизъюнктивную нормальную форму когда это дизъюнкция предложений, где каждое предложение представляет собой соединение атомарных ограничений. [Пример: для ограничений atomi c A, B и C дизъюнктивная нормальная форма ограничения A ∧ (B ∨ C) - (A ∧ B) ∨ (A ∧ C). Его дизъюнктивные предложения - (A ∧ B) и (A ∧ C). - конец примера]

131) Ограничение имеет конъюнктивную нормальную форму, когда оно представляет собой соединение предложений, где каждое предложение является дизъюнкцией атомарных ограничений. [Пример: для ограничений atomi c A, B и C ограничение A ∧ (B ∨ C) находится в конъюнктивной нормальной форме. Его конъюнктивные придаточные предложения - A и (B ∨ C). - конечный пример

...