двоичный_поиск, find_if и <functional>

Question

std::find_if принимает предикат в одной из перегруженных функций. Связыватели позволяют писать EqualityComparators для пользовательских типов и использовать их либо для динамического сравнения, либо для статического сравнения.

В отличие от бинарных функций поиска стандартной библиотеки берут компаратор и const T& к значению, которое должно использоваться для сравнения. Это кажется мне непоследовательным и может быть более неэффективным, поскольку компаратор должен вызываться с обоими аргументами каждый раз вместо того, чтобы иметь постоянный аргумент, связанный с ним. Хотя можно было бы реализовать std::binary_search таким образом, чтобы использовать std::bind, это потребовало бы, чтобы все компараторы наследовали от std::binary_function. Большая часть кода, который я видел, не делает этого.

Есть ли возможная выгода от того, что компараторы наследуют от std::binary_function при использовании его с алгоритмами, которые принимают const T& в качестве значения вместо того, чтобы позволять мне использовать связующие? Есть ли причина не предоставлять предикатные перегрузки в этих функциях?

Answer 1

Версия предиката с одним аргументом std::binary_search не сможет завершиться за O (log n).

Рассмотрим старую игру "угадай букву, о которой я думаю". Вы можете спросить: "Это А?" «Это Б?» .. и так до тех пор, пока вы не дошли до письма. Это линейный или O (n) алгоритм. Но разумнее было бы спросить: «Это до М?» "Это до G?" "Это раньше, чем я?" и так далее, пока не дойдете до рассматриваемого письма. Это логарифмический или O (log n) алгоритм.

Это то, что делает std::binary_search, и для этого нужно уметь различать три условия:

• Кандидат C - искомый элемент X
• Кандидат С больше, чем Х
• Кандидат С меньше, чем Х

Предикат с одним аргументом P (x) говорит, что только "x имеет свойство P" или "x не имеет свойства P". Вы не можете получить три результата от этой логической функции.

Компаратор (скажем, <) позволяет получить три результата путем вычисления C

• !(C < X) && !(X < C) C равно X
• C < X && !(X < C) C меньше, чем X
• !(C < X) && X < C C больше, чем X

Обратите внимание, что X и C связываются с обоими параметрами < в разное время, поэтому вы не можете просто связать X с одним аргументом < и использовать его.

Редактировать: спасибо jpalecek за напоминание о том, что binary_search использует <, а не <=. Редактировать редактировать: спасибо Робу Кеннеди за разъяснения. </p>

Answer 2

Это совершенно разные алгоритмы: find_if ищет линейно для первого элемента, для которого предикат является истинным, binary_search использует преимущество, что диапазон сортируется для проверки в логарифмическом времени если в нем задано значение.

Предикат для binary_search указывает функцию, в соответствии с которой упорядочивается диапазон (вы, скорее всего, захотите использовать тот же предикат, который вы использовали для его сортировки).

Вы не можете воспользоваться сортировкой для поиска значения, удовлетворяющего некоторому совершенно не связанному предикату (вам все равно придется использовать find_if). Однако обратите внимание, что с отсортированным диапазоном вы можете сделать больше, чем просто проверить существование с lower_bound, upper_bound и equal_range.

---

Интересен вопрос, какова цель std::binary_function.

Все, что он делает, это предоставляет typedefs для result_type, first_argument_type и second_argument_type. Это позволило бы пользователям, используя функтор в качестве аргумента шаблона, обнаруживать и использовать эти типы, например,

template <class T, class BinaryFunction>
void foo(const T& a, const T& b, BinaryFunction f)
{
     //declare a variable to store the result of the function call
     typename BinaryFunction::result_type result = f(a, b);
     //...
 }

Однако я думаю, что единственное место, где они используются в стандартной библиотеке, - это создание других оболочек функторов, таких как bind1st, bind2nd, not1, not2. (Если бы они использовались для других целей, люди бы кричали на вас всякий раз, когда вы использовали функцию в качестве функтора, поскольку это было бы непереносимо.)

Например, binary_negate может быть реализовано как (GCC):

template<typename _Predicate>
class binary_negate
: public binary_function<typename _Predicate::first_argument_type,
             typename _Predicate::second_argument_type, bool>
{
protected:
  _Predicate _M_pred;

public:
  explicit
  binary_negate(const _Predicate& __x) : _M_pred(__x) { }

  bool
  operator()(const typename _Predicate::first_argument_type& __x,
     const typename _Predicate::second_argument_type& __y) const
  { return !_M_pred(__x, __y); }
};

Конечно, operator() может быть просто шаблоном, и в этом случае эти typedefs будут ненужными (какие-либо недостатки?). Вероятно, существуют также методы метапрограммирования, позволяющие выяснить типы аргументов, не требуя, чтобы пользователь явно их определял. Я полагаю, что это немного отразится на мощи, которую дает C ++ 0x - например, когда я хотел бы реализовать отрицатель для функции любой арности с переменными шаблонами ...

(IMO функторы C ++ 98 немного негибки и примитивны по сравнению, например, с std::tr1::bind и std::tr1::mem_fn, но, вероятно, в то время поддержка компилятором методов метапрограммирования, необходимых для выполнения этой работы, была не такой хорошей, и, возможно, методы все еще открывались.)

Answer 3

Это неправильное понимание концепции Functor в C ++.

Это не имеет ничего общего с наследованием. Свойство, которое делает объект функтором (пригодным для передачи в любой из алгоритмов), является допустимостью выражения object(x) или object(x, y), соответственно, независимо от того, является ли это указателем функции или объектом с перегруженным оператором вызова функции. Определенно не наследство от чего-либо. То же самое относится к std::bind.

Использование бинарных функторов в качестве компараторов связано с тем фактом, что компараторы (например, std::less) являются бинарными функторами, и хорошо иметь возможность использовать их напрямую.

ИМХО, не было бы никакой выгоды в предоставлении или использовании предлагаемой вами версии предиката (в конце концов, требуется только передача одной ссылки). При использовании связывателей не будет никакого (повышения производительности), потому что он делает то же самое, что и алгоритм (связка будет передавать дополнительный аргумент вместо алгоритма).