当键是数据的一部分并且我想搜索键时如何使用std::lower_bound？

Question

我有一个结构如下：

struct chunk_offset {
    chunk_id chunk_id;
    unsigned int offset;
    unsigned int offset_size;
};
unsigned int chunk_count;
std::unique_ptr<chunk_offset[]> offsets;

我有一个数组，按

chunk_offset::chunk_id

排序。 由于数据已排序，我想使用

std::lower_bound

执行二分搜索。 然而，

std::lower_bound

需要一个代表对象本身的参数：

chunk read_chunk(chunk_id id) {
    // error, since id is not a chunk_offset
    auto itr = std::lower_bound(offsets.get(), offsets.get()+chunk_count, id); 
}

如何仅使用我的钥匙使用

std::lower_bound

？

Answer 1

当您调用

std::lower_bound(begin, end, value, comparator)

时，它会调用比较器（默认情况下为

operator<

），其中集合元素作为第一个参数，

value

作为第二个参数。两个参数可以有不同的类型。

因此，为了得到你想要的，你可以编写一个带有签名

bool compare(const chunk_offset &offset, chunk_id id)

的比较器（或为这些类型定义

operator<

）。

例如，使用 lambda：

auto itr = std::lower_bound(offsets.get(), offsets.get()+chunk_count, id,
    [](const chunk_offset &offset, chunk_id id) {
         return offset.id < id;
    });

Answer 2

虽然（正如另一个答案所说）您可以给

std::lower_bound

一个具有两种不同参数类型的比较器（因为

value

始终是第二个参数），但在这些情况下，我发现使用

std::partition_point

不会那么混乱。

std::partition_point

做同样的事情，但使用一元谓词并且没有

value

参数：

chunk_id id = ...;
auto iter = std::lower_bound(a, b, [&](const chunk_offset &o){return o.chunk_id < id;});