从集合中获取搜索字符串的下界迭代器。这里，集合中的字符串长度小于搜索字符串长度

Question

我想要集合中搜索字符串的下界迭代器。这里，集合中的字符串长度小于搜索字符串长度。

我的意思是，set 有像

{ "/Applications", "/Bpplications", "/Cpplications", "/Dpplications", "/Library/caches", "/opt/local", "/usr/local" };

这样的字符串。

我的搜索字符串就像

/Cpplications/test/sample.txt

这里我需要集合中与搜索字符串的子字符串匹配的下限迭代器，即来自

/Cpplications

的迭代器。但是，我使用下面的代码片段获得了

/Dpplications

的迭代器。

谁能帮忙解决这个问题吗？

#include <iostream>

using namespace std;
bool starts_with(string a, string b) {
    return a.compare(0, a.length(), b) < 0;
}
int main()
{
    // Input set
    std::set<string> s{ "/Applications", "/Bpplications", "/Cpplications", "/Dpplications", "/Library/caches", "/opt/local", "/usr/local" };
    
    std::set<string>::iterator low11;
    low11 = std::lower_bound(s.begin(), s.end(), "/Cpplications/test/sample.txt", starts_with);
    
    std::cout << "lower_bound:\n";
    for (;low11 != s.end(); low11++)
    {
        std::cout << "\n"<< (*low11);
    }

    return 0;
}

Answer 1

仅当左侧参数比右侧参数长时，比较器才会执行您想要的操作。

std::lower_bound

将使用两个位置中搜索到的值来调用它以确定是否相等。

这种比较将为您的情况做正确的事情，但它不是严格的弱顺序，因此概括它可能会导致未定义的行为。

bool starts_with(std::string_view a, std::string_view b) {
    auto size = std::min(a.size(), b.size());
    return a.substr(0, size) < b.substr(0, size);
}

在coliru上查看

更安全的做法是查看正常上限之前的元素，看看它是否具有正确的前缀。注意：您必须小心搜索范围的边缘。

std::set<std::string> s{ "/Applications", "/Bpplications", "/Cpplications", "/Dpplications", "/Library/caches", "/opt/local", "/usr/local" };
std::string n{"/Cpplications/test/sample.txt"};

auto low11 = s.upper_bound(n);
if (low11 != s.begin()) low11--;
if (low11 != s.end() && n.starts_with(*low11)) {
    std::cout << "lower_bound:\n" << *low11;
}

在coliru上查看