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

#c #stl

Вопрос:

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

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

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

Ответ №1:

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

 template<typename Map>
void erase_last_elements(Map amp; 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 amp; 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());
}

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

1. Есть ли какая-либо причина, по которой std::map не предоставляется O(log(n)) решение для доступа к n-му элементу?

2. Должно быть эффективнее удалять «end() — 1» k раз.

3. Это звучит как разумное решение, Стефан.

4. @Leonid — у них нет быстрого доступа к N-му элементу, потому что им пришлось бы поддерживать отдельный индекс, что потребовало бы больше памяти или замедлило бы вставку или удаление.

5. @Stefan — как ты думаешь, почему это было бы быстрее сделать? Асимптотически сложность та же, и потенциально требуется меньше перебалансировок дерева, если удалить их все одним вызовом erase.

Ответ №2:

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