Использовать шаблон функции двоичного предиката в качестве параметра (std :: better, std :: equal_to) c++

Почему мне нужно использовать 2 шаблона, по одному для каждого бинарного предиката, в определении функции?

Я пишу функцию, которая почти такая же, как или std :: min_element или std :: max_element, только вместо того, чтобы вернуть 1 элемент, вернуть все позиции, которые равны этому пределу (или мин., или макс.)

В последний раз я читал boost :: minmax_element.hpp, копирую функцию и меняю вывод и цикл while для создания функции.

И работает, если использую

if( *first > *lim.front() ) 

Но не если использую

if( comp(*first, *lim.front()) )

Здесь функция

template <typename INPUT_ITERATOR, class Compare>
std::vector<INPUT_ITERATOR>
basic_limit_positions( INPUT_ITERATOR first, INPUT_ITERATOR last, Compare comp, Compare comp_equal ) {

  std::vector<INPUT_ITERATOR> lim;

  if ( first == last ) {
    lim.push_back( last );
    return lim;
  }

  lim.push_back(first);
  while (++first != last) {

    if ( comp( *first, *lim.front() ) ) {
      lim.clear();
      lim.push_back( first );
    }
    else if ( comp_equal( *first, *lim.front() ) )
      lim.push_back( first );

  }

  return lim;
}

Как я его использую:

  std::vector< std::vector<uint64_t>::iterator > it = basic_limit_positions(v.begin(),
                                                                               v.end(),
                                                                               std::greater< uint64_t >(),
                                                                               std::equal_to< uint64_t > ()
                                                                               );

И ошибка:

test.cpp:40:80: error: no matching function for call to ‘basic_limit_positions(std::vector<long unsigned int>::iterator, std::vector<long unsigned int>::iterator, std::greater<long unsigned int>, std::equal_to<long unsigned int>)’
                                                                                );
                                                                                ^
In file included from test.cpp:10:0:
newton/algorithm/superior_positions.hpp:7:1: note: candidate: template<class INPUT_ITERATOR, class Compare> std::vector<INPUT_NUMBER> basic_limit_positions(INPUT_ITERATOR, INPUT_ITERATOR, Compare, Compare)
 basic_limit_positions( INPUT_ITERATOR first, INPUT_ITERATOR last, Compare comp, Compare comp_equal ) {
 ^~~~~~~~~~~~~~~~~~~~~
newton/algorithm/superior_positions.hpp:7:1: note:   template argument deduction/substitution failed:
test.cpp:40:80: note:   deduced conflicting types for parameter ‘Compare’ (‘std::greater<long unsigned int>’ and ‘std::equal_to<long unsigned int>’)
                                                                                );
                                                                                ^

Итак, я думаю: «проблема в шаблоне, потому что, если вывели конфликтующие типы для параметра «Сравнить» и тип правильный, уникальный случай остатка изменяет имя шаблона»

template <typename INPUT_ITERATOR, class Compare1, class Compare2>
std::vector<INPUT_ITERATOR>
basic_limit_positions( INPUT_ITERATOR first, INPUT_ITERATOR last, Compare1 comp, Compare2 comp_equal )

И ... Работает, Но ? Это тот же тип, поэтому я использую то же имя шаблона для первый и последний Почему !? нельзя использовать то же имя для comp и comp_equal

На самом деле для меня бессмысленно.

Вашему шаблону требуются два разных параметра шаблона компаратора: один для comp, а другой - для comp_equal. Хотя необходимости в двух компараторах нет вообще, так как равенство можно вычислить только по comp.

user7860670 11.04.2018 12:06

Как? Вы не можете использовать! Comp

Moises Rojo 11.04.2018 12:33
!((a < b) || (b < a))
user7860670 11.04.2018 12:44

Ага! Меняю его, if( comp( *first, *limit.front() ) )else if( !comp( *limit.front(), *first ) ), он такой же, что и !((a < b) || (b < a)), потому что автор De Morgan(!(a < b) && !(b < a))

Moises Rojo 11.04.2018 13:17
1
4
1 088
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

deduced conflicting types for parameter ‘Compare’

Это потому, что std::greater<T> и std::equal_to<T> относятся к разным типам. Это не функции вида bool (*)(T,T), а функторы.

С другой стороны, ваши первый и последний итераторы - это два разных экземпляра одного и того же типа.

И, как говорит VTT, вам в любом случае не нужны два устройства сравнения; предполагая, что комп - нормальный <,

const bool equal = !(comp(a,b) || comp(b,a));

т.е. !((a<b) || (b<a)) => ((a>=b) && (b>=a)) => (a==b)


This is because std::greater<T> and std::equal_to<T> are different types

Why are different types, are not both functors?

Определения выглядят примерно так

template <typename T>
struct greater {
  constexpr bool operator()(const T& lhs, const T& rhs) {
    return lhs > rhs;
  }
};
template <typename T>
struct equal_to {
  constexpr bool operator()(const T& lhs, const T& rhs) {
    return lhs == rhs;
  }
};

Каждый определяемый вами struct или class относится к разным типам. Каждый шаблон определяет новый тип для каждого отдельного экземпляра (набор параметров шаблона).

Они оба являются функторами, потому что у них обоих есть operator(). В частности, они оба являются двоичными предикатами, потому что у них обоих есть оператор вызова функции в форме bool operator()(T,T). Но даже когда вы создаете их оба для одного и того же T, один имеет тип greater<T>, а другой - тип equal_to<T>.

Как я уже упоминал выше, хотя greater<T> и equal_to<T> относятся к разным типам, bool (*)(T,T) - это единственный тип (указатель на функцию бинарного предиката, не являющуюся членом), который может использоваться для:

template <typename T>
bool f_greater(T const &lhs, const T& rhs) {
  return lhs > rhs;
}
template <typename T>
bool f_equal_to(T const &lhs, const T& rhs) {
  return lhs == rhs;
}

typedef bool(*binary_predicate)(int const&, int const&);
bool greater_or_equal(int a, int b,
                      binary_predicate g,
                      binary_predicate e)
{
  return g(a,b) || e(a,b);
}

// ... example use ...
greater_or_equal(17, 12, &f_greater<int>, &f_equal_to<int>);

Ага. См. Комментарий выше, я меняю последнее if, но без использования !((a<b) || (b<a))

Moises Rojo 11.04.2018 13:19

Почему разные типы, а не оба функтора? то есть ... того же типа.

Moises Rojo 11.04.2018 13:21

Мне трудно сказать, действительно ли вы знаете, что такое тип. «Функтор» - это концепция, которая применяется к любому типу с правильным интерфейсом - больше похоже на класс типов, чем на конкретный тип.

Useless 11.04.2018 14:58
Ответ принят как подходящий

Причина, по которой вам нужны два разных параметра типа шаблона для типов comp и comp_equal, заключается в том, как VTT заявил в комментарии, что типы различаются.

std::greater<uint64_t> и std::equal_to<uint64_t> - это совсем не один и тот же тип. Это шаблоны с одним и тем же параметром, но в остальном они не связаны.

Вы можете использовать один параметр типа для итератора, потому что first и last имеют один и тот же тип.

Вы можете написать свои собственные объекты функции сравнения следующим образом:

struct my_greater {
    bool operator()(uint32_t a, uint32_t b) {
        return a > b;
    }
};

Примерно так выглядит std :: better, за исключением того, что это шаблон, в котором вы можете выбрать тип ввода.

Несмотря на то, что сигнатура оператора вызова std :: equal одинакова, компилятор должен вызывать другую функцию.

Как написал пользователь Useless в отнюдь не бесполезном ответе, параметр шаблона не обязательно является указателем на функцию, который будет совместим, как только подписи совпадают.

Поскольку в качестве оператора сравнения можно использовать произвольный тип, можно сделать много полезных вещей. Я буду использовать минимальную функцию в качестве примера, чтобы лучше показать концепции:

// here I provided a default for the less comparison, 
// so you do not have to write it
// first we have a default for the type
// and then we have a default for the actual value
template <typename T, typename Less = std::less<T>>
T myMin(T a, T b, Less less=Less{}) {
   return less(b, a) ? b : a;
}

Прежде всего, если ваши компараторы просты, как std :: больше и std :: equal, компилятор может встроить operator() и сгенерировать оптимальный код, как в следующем примере:

int min_int(int a, int b) {
  return myMin(a, b);
}

int max_int(int a, int b) {
  return myMin(a, b, std::greater<int>{});
}

gcc генерирует хороший код для этого, обратите внимание, как были встроены less и greater:

min_int(int, int):
  cmp edi, esi
  mov eax, esi
  cmovle eax, edi
  ret
max_int(int, int):
  cmp edi, esi
  mov eax, esi
  cmovge eax, edi
  ret

Если типом был указатель на функцию, компилятор мог бы сделать это встраивание только в том случае, если сама внешняя функция встроена, а аргументы являются константами времени компиляции (если только он не использует некоторые довольно продвинутые оптимизации).

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

int pointy_min(int a, int b, bool(*less)(int, int)) {
    return myMin(a, b, less);    
}

В этом примере компилятор ничего не знает об аргументе less и поэтому должен сгенерировать больше кода для вызова указателя функции.

Или вы можете написать объекты функций с их собственным состоянием, как хотите, без ущерба для эффективности общего случая.

Что касается сравнения на равенство, которое вы можете построить из большего или меньшего, обратите внимание, что компилятор хорошо осведомлен о значении меньшего и большего и правил Де Моргана, поэтому он обычно хорошо оптимизируется после встраивания std::greater::operator(). Просто напишите то, что вы считаете наиболее очевидным и читаемым, если только вы не подозреваете, что кто-то собирается использовать ваш шаблон с тяжелой функцией сравнения.

template<typename T, typename Less = std::less<T>>
bool myEqual(T a, T b, Less less=Less{}) {
    return !(less(a,b) || less(b,a));
}

bool intEqual(int a, int b) {
    return myEqual(a, b);
}

bool otherEqual(int a, int b) {
    return a == b;    
}

Посмотрите, как компилятор вычислил оптимальный код после встраивания:

intEqual(int, int): # @intEqual(int, int)
  cmp edi, esi
  sete al
  ret
otherEqual(int, int): # @otherEqual(int, int)
  cmp edi, esi
  sete al
  ret

Другие вопросы по теме