binary_search, 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
• кандидата C больше, чем X
• кандидат С меньше X

один аргумент-предикат Р (х) говорит только «х имеет свойство Р» или «х не обладают свойством P». Вы не можете получить три результата этой булевой функции.

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

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

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

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

Answer 2

Это недоразумение концепции Functor в C++.

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

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

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

Answer 3

Они совершенно разные алгоритмы: 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() может, возможно, просто шаблон, и в этом случае эти определения типов были бы не нужны (любые недостатки?). Возможно, есть методы метапрограммирования, чтобы выяснить, какие типы аргументов не требуют, чтобы пользователь явно вводил их явно. Полагаю, что это немного сработает с силой, которую дает C++ 0x, например, когда я хотел бы реализовать отрицатель для функции любой арности с вариативными шаблонами ...

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