Наслаждение обоими мирами: вектор с эффективностью вставки / стирания списка

Question

Мне нужен контейнер, который дает мне быстрый индексатор и также может быть очень эффективен в произвольных операциях вставки и удаления (имеется в виду в любой позиции контейнера).

Я помню, как читал о таком контейнере, в котором используются корзины, но я не могу найти его или проследить шаги, которые привели меня к нему (я начну использовать закладки, обещаю!)

Спасибо, любезно.

Answer 1

Возможно, вы ищете какую-то хэш-карту, например boost::unordered_map (скоро будет в стандарте C ++). Существует множество других реализаций хеша.

Answer 2

Вы ищете std :: deque, который превосходит std :: list при многих (но не во всех) обстоятельствах, когда требуется вставка в местах, отличных от концов.Для этого он использует «корзины» и поддерживает произвольный доступ.Действительно, для любого стандартного контейнера библиотеки вам необходимо проверить его производительность на предмет его использования вашим приложением - мы не можем предсказать для вас, что будет лучше.

Answer 3

Мне нужен контейнер такого типа для контейнера с разреженным вектором, который я написал, я не могу использовать map <>, потому что он занимает слишком много памяти (вектор не такой уж редкий).

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

Я все еще хотел бы найти эффективный гибрид вектор / список, который равен O (1) при произвольном доступе и по крайней мере O (log N)) в стирании / вставке.