I want the lower bound iterator of search string from set. Here, strings length in set are less than search string length.
I mean, set has strings like { "/Applications", "/Bpplications", "/Cpplications", "/Dpplications", "/Library/caches", "/opt/local", "/usr/local" };.
My search string is like /Cpplications/test/sample.txt
Here I need the the lower bound iterator from set which matches substring of search string i.e. iterator from /Cpplications . But, I am getting iterator of /Dpplications with my below code snippet.
Can anyone help to fix this?
#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;
}
Your comparator only does what you want if the left argument is longer than the right argument. std::lower_bound will call it with the searched-for value in both positions to determine equivalence.
This comparison will do the correct thing for your case, but it isn't a strict weak order, so it can't be used where you need a Compare, e.g. for sorting.
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);
}
A different approach is to look at the element prior to the upper bound, and see if that has the correct prefix. N.b. you will have to be careful with the edges of the search range.
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;
}