问std::binary_search()查询
EN

Stack Overflow用户

提问于 2016-02-25 18:06:19

回答 2查看 803关注 0票数 0

我目前正在使用std::binary_search() (来自库)来确定列表中是否存在某个东西的实例。在我开始使用它之前，我想知道它是如何工作的。

我的理解是，它使用比较(对于用户定义的结构/类，它需要访问用户定义的比较函数)来确定一个对象的实例是否存在于一个列表/向量中。根据这个网站(搜索/)，使用的范围是：

[first, last)

所以它不包括最后一个，因为它必须比较最后一个和 have + 1

而且，用户定义的比较函数的逻辑并不重要，只要它区分对象/类中的属性。对吗？

例如，如果我的struct/class包含以下内容：

coord
{
    int X;
    int Y;
}

我必须确保我的比较函数以某种方式(例如大于/小于比较)区分列表/向量中元素a和b的X和Y属性。

binary-search

c++

list

indexing

compare

回答 2

Stack Overflow用户

回答已采纳

发布于 2016-02-25 18:50:55

std::binary_search()作为一种常见的二进制搜索算法实现，它最多执行log2(N)+1元素的比较。(有关如何实现二进制搜索的更多信息，请查看此链接)

所以，它不包括最后，因为它必须比较最后和最后+ 1？

不，原因只是为了方便使用。您可以按以下方式调用该函数：

std::binary_search (v.begin(), v.end(), 42)

注意，v.end()将迭代器返回到序列结束后的元素。因此，它不指向任何元素，因此不应在搜索中进行计算。

而且，用户定义的比较函数的逻辑并不重要，只要它区分对象/类中的属性。对吗？

它用于binary_search()的比较函数，以便知道您要查找的元素是否在它之后正在测试的元素之前。换句话说，如果第一个元素比第二个元素“低”，则比较函数必须能够比较两个元素并返回(必须放在第二个元素之前的容器中)。

对于Coord示例，可以编写一个比较器函数，如下所示：

struct lessThanKey
{
    inline bool operator() (const Coord& lhs, const Coord& rhs)
    {
        return (lhs.x < rhs.x) || ((lhs.x == rhs.x) && (lhs.y < rhs.y));
    }
};

std::binary_search(v.begin(), v.end(), Coord{42, 42}, lessThanKey());

票数 2

Stack Overflow用户

发布于 2016-02-25 18:22:44

范围不包括，而不是，将最后一个元素作为一般的库约定，这意味着第一次迭代器和最后一次迭代器之间的距离等于范围中的元素数，并且可以使用以下方法在循环中测试范围：

while(first != last)
{
    // process stuff
    ++first;
}

必须对使用相同(可能是用户定义的)比较函数排序的已排序数据执行std::binary_search。

该函数需要在两个元素之间建立一个较少的关系。

struct coord
{
    int x;
    int y;
};

struct CoordComparator
{
    bool operator()(const coord& lhs, const coord& rhs) const
    {
        return lhs.x == rhs.x ? lhs.y < rhs.y : lhs.x < rhs.x;
    }
};

std::vector<coord> v { {1, 1}, {2, 1}, {2, 2}, {1, 2} };

std::sort(v.begin(), v.end(), CoordComparator());

if(std::binary_search(v.begin(), v.end(), coord{2, 1}, CoordComparator()))
{
    // element found in range
}