Итерация по карте, начиная с указанного ключа c

Question

Я реализую функцию, предназначенную для поиска любых строк, которые имеют префикс с данной строкой. Все возможные строки для сравнения уже есть в карте, и я хотел бы перебрать эту карту, начиная с той, где находится данная строка. В настоящее время я зацикливаюсь на всей карте, но по соображениям производительности мне нужно сделать это более эффективным. Вот как я сейчас перебираю карту:

for(auto const& it : lookup_map){ //performs code }

Я бы хотел, чтобы это начиналось не с начала карты, а везде, где указанная строка находится на карте.

Answer 1

Просто используйте старые добрые итераторы:

for( auto it = lookup_map.find( your_string ); it != lookup_map.end(); ++it ) {
   // using it
}

Answer 2

std::map имеет свою собственную функцию-член lower_bound для того, что вы хотите сделать. Вы можете использовать std :: map :: lower_bound , чтобы получить свою начальную позицию, а затем выполнить сравнение префикса для последующих итераций:

for (auto it = lookup_map.lower_bound(prefix);
    it != std::end(lookup_map) && it->first.compare(0, prefix.size(), prefix) == 0;
    ++it)
{
    ...
}

Это будет более эффективно, чем итерация каждого один ключ Преимущество в этом случае использования lower_bound() состоит в том, что он вернет первый элемент, который эквивалентен или после поискового запроса. Так что если ваш поисковый термин «aa» и у вас есть запись «aab» на вашей карте, lower_bound () вернет итератор в «aab». Я думаю, что это будет более полезно в вашем случае, потому что вы хотите искать по префиксу.