- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
std::find_if
在其重载函数之一中采用谓词。绑定(bind)器使得为用户定义的类型编写 EqualityComparators 并将它们用于动态比较或静态比较成为可能。
相比之下,标准库的二进制搜索函数采用比较器和 const T&
来比较应该用于比较的值。这对我来说感觉不一致,并且可能效率更低,因为每次都必须使用两个参数调用比较器,而不是将常量参数绑定(bind)到它。虽然有可能以使用 std::bind
的方式实现 std::binary_search
,但这需要所有比较器都继承自 std::binary_function
。我见过的大多数代码都不会这样做。
当将比较器与以 const T&
为值的算法一起使用时,让比较器从 std::binary_function
继承而不是让我使用 Binder ?是否有理由不在这些函数中提供谓词重载?
最佳答案
std::binary_search
的单参数谓词版本无法在 O(log n) 时间内完成。
想一想“猜猜我想到的字母”这个老游戏。你可以问:“是 A 吗?” “是 B 吗?”.. 依此类推,直到找到字母。这是一个线性或 O(n) 算法。但更聪明的做法是问“它在 M 之前吗?” “是在G之前吗?” “是在我之前吗?”依此类推,直到找到有问题的字母。这是一个对数或 O(log n) 算法。
这就是std::binary_search
确实如此,要做到这一点需要能够区分三个条件:
单参数谓词 P(x) 仅表示“x 具有属性 P”或“x 不具有属性 P”。您无法从此 bool 函数获得三个结果。
比较器(比如 <
)让您通过计算 C < X 和 X < C 得到三个结果。然后您有三种可能性:
!(C < X) && !(X < C)
C等于XC < X && !(X < C)
C小于X!(C < X) && X < C
C大于X请注意,X 和 C 都绑定(bind)到 <
的两个参数在不同的时间,这就是为什么你不能只将 X 绑定(bind)到 <
的一个参数并使用它。
编辑:感谢 jpalecek 提醒我 binary_search 使用 <,而不是 <=。编辑编辑:感谢 Rob Kennedy 的澄清。
关于c++ - binary_search、find_if 和 <functional>,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2371833/
我正在尝试在 1 文件 .cpp 文件中构建以下代码块: #include #include using namespace std; class test { public: int a
我正在尝试了解 find_if 函数的工作原理,并且我正在按照此引用中的示例进行操作: http://www.cplusplus.com/reference/algorithm/find_if/ 当我
我根据第一个字母从数组中查找所有字符串: #include #include #include int main(){ const std::string strArray[] = {"an","b
所以我有一个名为 Song 的类,还有一个名为 SongLibrary 的类。歌曲库仅包含一组所有歌曲和适当的方法。 我目前正在尝试制作一个搜索歌曲库并检查歌曲是否具有特定标题的功能。 我遇到的问题是
我第一次在 C++ 代码中使用 std::find_if 函数。我想要执行的示例和逻辑非常简单,但不知何故我无法使其工作。 我以这种方式创建了“finder”类: /** * @class m
#include #include using namespace std; int main() { int matrix[9] = { 1,0,0,0,1,0,0,0,5 };
在我的 main.cpp 中: using namespace std; #include #include #include #include #include #include #in
我遇到过 set::find 不是查找对象的正确方法的情况,因为我找到对象的方式(通过 std::find_if)不同于它在集合中的排序方式。我没有找到任何关于以这种方式查找元素的复杂性信息。我假设它
我收到错误: no matching function for call to ‘findByPosition::findByPosition(std::vector::size_type&, std
如何检查 find_if 是否找到匹配项?当我尝试下面的代码时: SparseMatrix& SparseMatrix::operator+=(const SparseMatrix &other) {
在 std::vector 中,我想找到最大数小于某个数的元素的位置。例如: v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 我想找到一个最大小于 8 的数字。那个数字是 7。
我有一个填充字符串 vector 的实例方法。我试图找到包含特定子字符串的一个 vector 条目(目前,该子字符串是固定的 - 简单)。 我有一个.h: namespace Data { names
下面的代码有什么问题?如果结构的第一个成员等于 0,它应该在结构列表中找到一个元素。编译器提示 lambda 参数不是谓词类型。 #include #include #include #incl
谓词函数: bool Schedule::predicateFunc(map,pair >::iterator it,string &a) { return (it->first).first
使用 std::find_if 我们可以找到一个元素是否存在于普通的一维数组中。 灵感来自 this question ,我想知道,我们是否可以提供一个算法函数来检查任何类型和任意数量元素的二维数组(
我正在尝试在具有 Lambda 表达式的函数中使用 find_if。我想获取 vector 的最后一个迭代器,但我不确定如何编写它。 我可以用这段代码得到第一个迭代器。在这段代码中,struct 有一
这是我的代码片段: #include #include #include using namespace std; bool next(int j) { return(j>m; int
我正在研究从另一个 SO 帖子中获得的以下示例。示例是这样的 class checker { public: bool operator()(unsigned int i) {
关闭。这个问题需要debugging details .它目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and th
对于从 find_if 到对象的映射指针,我应该使用示例 1 还是示例 2哪个最好? struct test { INT id } std::vector> vec; int ID = 75; au
我是一名优秀的程序员,十分优秀!