словарь — какая альтернатива вектору C ++, когда дело доходит до быстрого удаления?
вектор является первым выбором во многих ситуациях, потому что произвольный доступ — это O (1), так как не так много контейнеров, которые достаточно быстры, или, по крайней мере, O (log (n)).
Моя проблема с вектором vector<>::erase() является O (n), map<>::erase() быстрее и лучше контейнер.
Альтернативой может быть использование пула объектов, но он не является стандартным контейнером, и реализации могут варьироваться в зависимости от использования, поэтому я не очень заинтересован в использовании чего-то, о чем я не очень-то понимаю или о чем знаю.
Кажется, карта — очень хорошая альтернатива вектору<> Когда есть часто встречающиеся удаления, но я хотел знать, есть ли лучшие альтернативы этому.
Так есть ли контейнер с быстрым произвольным доступом и удалением?
Есть ли обычный способ сделать пул объектов?
Решение
Какая альтернатива вектору C ++, когда дело доходит до быстрого удаления?
Стирание последнего элемента вектора (то есть операция pop) имеет постоянную сложность, поэтому, если вам не нужно упорядочивать свою последовательность, эффективное решение состоит в том, чтобы заменить целевой элемент последним и вытолкнуть его.
Связанный список имеет постоянную сложность удаления, которая поддерживает порядок последовательности, но индексированный поиск является линейным (т.е. не произвольный доступ).
Конечно, (неупорядоченная) карта имеет асимптотически эффективный поиск и стирание, но вы не получите такого же поведения, как вектор. Если вы создаете индекс -> элемент карты и удаляете элемент из индекса iтогда будет разрыв между i - 1 а также i + 1в то время как вектор будет сдвигать элементы с индексами больше i оставил.
Индексируемый список пропусков имеет логарифмический (в среднем; наихудший случай — линейный) поиск и удаление. Однако в стандартной библиотеке его нет.
Другие решения
Других решений пока нет …