Elegant way to find keys with given prefix in std::map or elements in std::set

Question

I have map, which keys are std::string. I want to find those elements in the map which starts with "DUPA/" prefix. Finding lower bound is easy but upper bound is a bit problematic. I wrote such piece of code:

const char* prefix = "DUPA/";
const char* firstAfterPrefix = "DUPA0";
auto prefixedBeginIt = myMap.upper_bound(prefix);
auto prefixedEndIt = myMap.lower_bound(firstAfterPrefix);

The code works fine but I don't consider it to be elegant, as one has to know that 0 is first next to / in ASCII table. Second way would be to copy prefix and increment last sign. Do you know more elegant solution?

Answer 1

If you can assume that CHAR_MAX would not be a valid character in your strings, then you can create firstAfterPrefix by appending CHAR_MAX (or the maximum value of your character type if it's not char).

std::string prefix = "DUPA/";

constexpr auto char_max = std::numeric_limits<decltype(prefix)::value_type>::max();
std::string firstAfterPrefix = prefix + char_max;

auto prefixedBeginIt = myMap.lower_bound(prefix);
auto prefixedEndIt = myMap.lower_bound(firstAfterPrefix);

Note the use of lower_bound for both bounds. Like Gill I am using std::string to simplify the exposition.

---

If you can use C++14 and specify the Compare template argument of the container then another way is to use a custom probe object:

struct PrefixProbe { std::string_view prefix; };
bool operator<(PrefixProbe a, std::string_view b) { return a.prefix < b.substr(0, a.prefix.size()); }
bool operator<(std::string_view a, PrefixProbe b) { return a.substr(0, b.prefix.size()) < b.prefix; }

std::map<std::string, myValue, std::less<>> myMap;
//                             ^~~~~~~~~~~
//                             where the magic happens

auto prefixBegin = myMap.lower_bound(PrefixProbe { prefix });
auto prefixEnd = myMap.upper_bound(PrefixProbe { prefix });

std::string_view is C++17 but is not required to make this work.

equal_range would reduce the last two lines to a single line:

auto [ prefixBegin, prefixEnd ] = myMap.equal_range(PrefixProbe { prefix });

If you are prepared to use the STL algorithms instead of the container member functions then this can be done without altering the container type, but would be less efficient:

auto prefixBegin = std::lower_bound(cbegin(myMap), cend(myMap), PrefixProbe { prefix }, std::less<>{});
auto prefixEnd = std::upper_bound(cbegin(myMap), cend(myMap), PrefixProbe { prefix }, std::less<>{});

auto [ prefixBegin, prefixEnd ] = std::equal_range(cbegin(myMap), cend(myMap), PrefixProbe { prefix }, std::less<>{});

Answer 2

I think the solution you mentioned is already the most elegant. The KISS way loses a lot of performance, that is, checking the key each time:

while(prefixedBeginIt->first == prefix)
{
 //...
 ++prefixedBeginIt;
}

Thus I think calculating the next char is the best approach:

std::string firstAfterPrefix = prefix;
++firstAfterPrefix[firstAfterPrefix.length() - 1];
auto prefixedEndIt = myMap.lower_bound(firstAfterPrefix);