Элегантный способ найти ключи с заданным префиксом в std::map или элементы в std::set

Question

У меня есть карта, ключи которой являются std::string. Я хочу найти те элементы на карте, которая начинается с "DUPA/" префикс. Найти нижнюю границу легко, но верхняя граница немного проблематична. Я написал такой кусок кода:

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

Код работает нормально, но я не считаю его элегантным, так как нужно знать, что 0 первый рядом с / в таблице ASCII. Второй способ - скопировать префикс и увеличить последний знак. Знаете ли вы более элегантное решение?

Answer 1

Я думаю, что решение, которое вы упомянули, уже является самым элегантным. Способ KISS теряет много производительности, то есть каждый раз проверяет ключ:

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

Таким образом, я думаю, что вычисление следующего символа - лучший подход:

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

Answer 2

Если вы можете предположить, что CHAR_MAX не будет действительным символом в ваших строках, то вы можете создать firstAfterPrefix добавив CHAR_MAX (или максимальное значение вашего типа персонажа, если это не так 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);

Обратите внимание на использование lower_bound для обеих границ. Как Гилл я использую std::string упростить экспозицию.

---

Если вы можете использовать C++14 и указать Compare Аргумент шаблона контейнера, то другой способ заключается в использовании пользовательского объекта исследования:

struct PrefixProbe { string_view prefix; };
bool operator<(PrefixProbe a, std::string_view b) { return a.prefix < b; }
bool operator<(std::string_view a, PrefixProbe b) { return a < b.prefix && 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 });

string_view является C++17, но не требуется, чтобы сделать эту работу.

equal_range свел бы последние две строки к одной строке:

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

Если вы готовы использовать алгоритмы STL вместо функций-членов контейнера, то это можно сделать без изменения типа контейнера, но будет менее эффективным:

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<>{});