Как стереть последние n элементов в карте C ++?

Question

Есть ли хороший и простой способ найти nth element в C++ std::map? В частности, я ищу алгоритм для удаления последних k элементов из map. Это имеет смысл вернуть итератор в nth element и вызвать std::map::erase. Требование состоит в том, что сложность не страдает - это должно быть возможным, чтобы стереть диапазон элемента в O(N).

Копирование данных не должно быть сделано только для стирания элементов. Например, одно из решений состоит в том, чтобы скопировать данные в std::vector, затем выполнить std::nth_element в std::vector, а затем std::map::find, чтобы найти итератор, чтобы выяснить, откуда его удалить.

Одно из других решений - просто перебрать std::map, поддерживая переменную counter для количества удаляемых элементов. Это дало бы O(n). Можно ли заменить петлю for на STL algorithm?

Answer 1

Карты не обеспечивают лучше, чем линейный доступ к элементам по индексу, например vector или deque.Вы можете сделать это, используя std::advance, но это занимает время, пропорциональное k.Если k мало, оно часто будет достаточно быстрым - оно в основном включает в себя следующие k указатели.Вот пример:

template<typename Map>
void erase_last_elements(Map & map, ptrdiff_t k)
{
    assert(k >= 0);
    assert(map.size() >= (size_t)k);
    typename Map::iterator i = map.end();
    std::advance(i, -k);
    map.erase(i, map.end());
}

В качестве альтернативы, если вы используете Boost, вы можете использовать boost::prior:

template<typename Map>
void erase_last_elements(Map & map, ptrdiff_t k)
{
    assert(k >= 0);
    assert(map.size() >= (size_t)k);
    typename Map::iterator i = boost::prior(map.end(), k);
    map.erase(i, map.end());
}

В противном случае вам придется поддерживать отдельный индекс,или используйте другой контейнер.Может пригодиться что-то вроде отсортированного vector, если вы не слишком много вставляете и удаляете элементы.

Answer 2

Редактировать : Ответ не применяется после редактирования исходного сообщения.