CODEWITHSUNDEEP
c++stringsearchrange
Andrew LeFevre
Andrew LeFevre

Reputation: 101

Using std::equal_range to find the range of prefixes that occur in a vector of strings

I'm trying to come up with a lambda that will allow std::equal_range to return a range in which the string searched for exists as a prefix. As that probably isn't worded right, an example:

Given the vector of strings:

I would expect the iterators returned to be

How would I write a comparison lambda for std::equal_range that accomplishes this, or is std::equal_range not the right tool for this job?

Upvotes: 3

Views: 874

Answers (1)

Galik
Galik

Reputation: 48615

I think you simply need to make the comparator compare only the length of the prefix against the elements like this:

std::vector<std::string> v
{
    "C:/users/andy/documents/screenshot.jpg",
    "C:/users/bob/desktop/file.txt",
    "C:/users/bob/desktop/picture.png",
    "C:/users/bob/desktop/video.mp4",
    "C:/users/john/desktop/note.txt",
};

std::sort(std::begin(v), std::end(v));

std::string const prefix = "C:/users/bob/desktop/";

auto lb = std::lower_bound(std::begin(v), std::end(v), prefix);

// For the upper bound we want to view the vector's data as if
// every element was truncated to the size of the prefix.
// Then perform a normal match.
auto ub = std::upper_bound(lb, std::end(v), prefix,
[&](std::string const& s1, std::string const& s2)
{
    // compare UP TO the length of the prefix and no farther
    if(auto cmp = std::strncmp(s1.data(), s2.data(), prefix.size()))
        return cmp < 0;

    // The strings are equal to the length of the prefix so
    // behave as if they are equal. That means s1 < s2 == false
    return false;
});

// make the answer look like we used std::equal_range
// (if that's what's needed)
auto range = std::make_pair(lb, ub);

for(auto itr = range.first; itr != range.second; ++itr)
    std::cout << *itr << '\n';

Output:

C:/users/bob/desktop/file.txt
C:/users/bob/desktop/picture.png
C:/users/bob/desktop/video.mp4

To explain why this works imagine taking the vector and sorting it. Then imagine visiting every element and truncating them to the length of the prefix. You would be left with a sorted vector with no elements longer than the prefix. At that point a simple std::equal_range would do what you require. Thus, all we need to do is construct a comparator that behaves as if the container elements had been truncated to the length of the prefix and use that comparator in our std::equal_range search (or twin std::lower_bound/upper_bound search).

Upvotes: 2

Related Questions