c++ - `find_if` 的二分查找等效项

假设一个容器(在这种情况下是一个普通数组)存储元素，如

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

现在我想找到一个 Foo ，其 id 以特定字符串 S 开头。由于数组是按id排序的，我想使用二分查找，所以我找了一个和find_if接口(interface)一样的执行二分查找的函数。 STL中是否有这样的函数，是否可以通过使用algorithm中的其他元素来构建，或者我需要自己实现它吗？

最佳答案

您正在寻找 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())

关于c++ - `find_if` 的二分查找等效项，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27094039/