c++ - 相当于 `find_if` 的二进制搜索

Question

假设一个容器(在本例中是一个普通数组)存储如下元素

struct Foo
    {
    char id[8];
    // other members
    };

现在我想找到一个 Foo，其 id 以特定字符串 S 开头。由于数组是按 id 排序的，我想使用二进制搜索，所以我寻找一个与 find_if 具有相同接口(interface)的执行二进制搜索的函数。 STL中有没有这样的函数，可以利用algorithm中的其他元素构造，还是需要自己实现。

Answer 1

您正在寻找 std::lower_bound、std::upper_bound 和 std::equal_range，它们接受一个输入范围，一个搜索值和一个可选的比较器，并要求根据比较器对范围进行排序。

对于您的具体示例，我将使用 std::lexicographical_compare 作为比较器:

#include <algorithm>
#include <iterator>

struct IdCmp
{
  bool operator()(const Foo & lhs, const Foo & rhs) const
  {
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id),
                                        std::begin(rhs.id), std::end(rhs.id));
  }
};

int main()
{
  Foo a[100];           // populate
  Foo b = make_needle();

  auto p = std::equal_range(std::begin(a), std::end(a), b, IdCmp());

  /* The elements with key equal to that of b are in [p.first, p.second). */
}

如果您希望能够直接搜索字符串，您的比较器需要可以通过一个 Foo 参数和一个字符串参数进行异构调用。例如:

struct IdCmp
{
  bool operator()(const Foo & lhs, const Foo & rhs) const
  {
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id),
                                        std::begin(rhs.id), std::end(rhs.id));
  }

  bool operator()(const Foo & lhs, const char * id) const
  {
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id),
                                        id, id + 8);
  }

  bool operator()(const char * id, const Foo & rhs) const
  {
    return std::lexicographical_compare(id, id + 8,
                                        std::begin(rhs.id), std::end(rhs.id));
  }
};

现在您可以搜索:

std::lower_bound(std::begin(a), std::end(a), "ABCD1234", IdCmp())