std::find_if在其中一个重载函数中获取谓词.Binders可以为用户定义的类型编写EqualityComparators,并将它们用于动态比较或静态比较.
相比之下,标准库的二进制搜索功能采用比较器和a const T&应该用于比较的值.这感觉与我不一致,并且可能更低效,因为每次都必须使用两个参数调用比较器而不是将常量参数绑定到它.虽然有可能以std::binary_search某种方式实现,std::bind但这需要所有比较器继承std::binary_function.我见过的大多数代码都没有这样做.
比较器std::binary_function在使用算法时是否可以继续使用算法const T&而不是让我使用绑定器？是否有理由不在这些函数中提供谓词重载？
单参数谓词版本std::binary_search无法在O(log n)时间内完成.
考虑旧游戏"猜猜我正在考虑的信".你可以问:"它是A吗？" "是B吗？"等等,直到你收到这封信.这是一个线性或O(n)算法.但更聪明的是问"它在M之前吗？" "它在G之前吗？" "它在我之前吗？" 等等,直到你收到有问题的信.这是一个对数或O(log n)算法.
这就是做什么std::binary_search,并且要做到这一点需要能够区分三个条件:
单参数谓词P(x)仅表示"x具有属性P"或"x没有属性P".你不能从这个布尔函数得到三个结果.
比较器(比方说<)可以通过计算C <X和X <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使用<,而不是<=.编辑编辑:感谢Rob Kennedy的澄清.
| 归档时间： |
|
| 查看次数： |
2524 次 |
| 最近记录： |