当键为结构体数据成员时，如何使用std::lower_bound进行搜索？

问题背景 #

我定义了如下结构体：

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做二分搜索，但直接传入chunk_id类型的键值会报错——因为std::lower_bound默认要求传入完整的chunk_offset对象：

chunk read_chunk(chunk_id id) {
    // 错误：id不是chunk_offset类型
    auto itr = std::lower_bound(offsets.get(), offsets.get()+chunk_count, id); 
}

请问仅用键值时，怎么调用std::lower_bound？

解决方案 #

方法1：自定义比较函数 #

给std::lower_bound传一个自定义的比较谓词，让它只对比chunk_id字段就行：

// 自定义比较逻辑：判断结构体的chunk_id是否小于目标id
bool compare_chunk_id(const chunk_offset& co, chunk_id id) {
    return co.chunk_id < id;
}

chunk read_chunk(chunk_id id) {
    auto itr = std::lower_bound(offsets.get(), offsets.get()+chunk_count, id, compare_chunk_id);
    // 后续可检查itr是否有效，再读取对应chunk
}

注意参数顺序：第一个是数组里的chunk_offset元素，第二个是目标键值——std::lower_bound靠这个函数判断“元素是否小于目标值”。

方法2：用Lambda表达式（更简洁，推荐） #

不用单独写函数，直接在调用时内嵌lambda表达式：

chunk read_chunk(chunk_id id) {
    auto itr = std::lower_bound(
        offsets.get(), 
        offsets.get()+chunk_count, 
        id,
        [](const chunk_offset& co, chunk_id target_id) {
            return co.chunk_id < target_id;
        }
    );
    // 处理搜索结果
}

方法3：C++20及以后的投影参数 #

如果你的编译器支持C++20，可以用更简洁的投影语法，直接指定要比较的字段：

#include <functional> // 需包含头文件以使用std::less

chunk read_chunk(chunk_id id) {
    auto itr = std::lower_bound(
        offsets.get(), 
        offsets.get()+chunk_count, 
        id,
        std::less<>{},
        &chunk_offset::chunk_id // 直接投影到chunk_id字段
    );
    // 处理搜索结果
}

这里std::less<>是默认的比较器，投影参数告诉lower_bound把每个元素映射到chunk_id后再做比较。

内容的提问来源于stack exchange，提问作者user3001150