修正std::lower_bound获取set中搜索串前缀下界迭代器的问题

你的代码返回错误结果的核心原因有两个：

1. 自定义比较函数starts_with的逻辑不符合std::lower_bound的要求，且与std::set默认的字典序排序规则不一致，导致二分查找出现未定义行为。
2. starts_with的实现没有正确表达“元素是否应排在搜索串之前”的逻辑，无法定位到目标前缀元素。

以下提供两种可行的修正方案：

方案一：利用默认排序结合前缀验证（无需修改set结构） #

该方案借助std::set默认的字典序排序，通过upper_bound找到边界后向前回溯，再验证元素是否为搜索串的前缀，兼容性更强。

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main()
{
    std::set<string> s{ "/Applications", "/Bpplications", "/Cpplications", "/Dpplications", "/Library/caches", "/opt/local", "/usr/local" };
    const string search_str = "/Cpplications/test/sample.txt";
    
    auto it = s.upper_bound(search_str);
    if (it != s.begin()) {
        --it;
        // 验证当前元素是否是搜索串的前缀
        if (search_str.size() >= it->size() && search_str.substr(0, it->size()) == *it) {
            cout << "找到目标元素: " << *it << endl;
            // 遍历后续元素
            for (; it != s.end(); ++it) {
                cout << "\n" << *it;
            }
        } else {
            cout << "未找到匹配的前缀元素" << endl;
        }
    } else {
        cout << "set为空或所有元素都大于搜索串" << endl;
    }

    return 0;
}

逻辑说明 #

• upper_bound(search_str)返回set中第一个大于搜索串的元素（即/Dpplications）
• 向前移动迭代器，得到set中最大的小于等于搜索串的元素
• 通过字符串截取验证该元素是否为搜索串的前缀，确保结果符合需求

方案二：自定义排序规则（适合频繁按前缀查找的场景） #

该方案让std::set和std::lower_bound使用一致的自定义排序规则，直接通过lower_bound定位目标元素。

#include <iostream>
#include <set>
#include <string>

using namespace std;

// 自定义比较函数：元素x排在搜索串s前，当且仅当x不是s的前缀且x字典序小于s
bool prefix_compare(const string& x, const string& s) {
    if (s.size() >= x.size() && s.compare(0, x.size(), x) == 0) {
        // x是s的前缀，不排在s前面
        return false;
    }
    return x < s;
}

int main()
{
    // 使用自定义比较函数初始化set
    std::set<string, decltype(&prefix_compare)> s(prefix_compare);
    s.insert("/Applications");
    s.insert("/Bpplications");
    s.insert("/Cpplications");
    s.insert("/Dpplications");
    s.insert("/Library/caches");
    s.insert("/opt/local");
    s.insert("/usr/local");
    
    const string search_str = "/Cpplications/test/sample.txt";
    auto low11 = std::lower_bound(s.begin(), s.end(), search_str, prefix_compare);
    
    std::cout << "lower_bound结果:\n";
    for (; low11 != s.end(); ++low11) {
        std::cout << "\n" << (*low11);
    }

    return 0;
}

逻辑说明 #

• 自定义prefix_compare函数，将“元素是搜索串前缀”的情况视为不排在搜索串前面
• 初始化set时传入该比较函数，确保set内部按此规则排序
• 调用lower_bound时使用相同的比较函数，会直接返回目标前缀元素/Cpplications

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