Я думаю, что мне нужна структура связанного списка с ключами. Какие-либо предложения?

Question

Я хочу хранить данные в структуре map, потому что мне нужно получить доступ к элементам, используя ключ. Я также буду перебирать последовательные элементы, так что структура list будет моим лучшим выбором здесь. Я думаю, что мне нужна гибридная структура данных, которая предлагает лучшее из обоих миров.

Так что в основном я хочу произвольный доступ со O (log (n)) сложностью и итерацией со O (c) сложностью. Существуют ли какие-либо встроенные структуры из cstdlib или Qt, которые стоит рассмотреть? Существуют ли альтернативные подходы, которые могут быть более подходящими в этом случае?

Answer 1

Если вам важен порядок, в котором вы выполняете итерацию:

Перемещение итератора от одного элемента к следующему является операцией O (c) как в list, так и в (multi)map, за исключением того, что c немного меньше для list, поэтому вряд ли вы получите много, объединив два.

Вы, вероятно, лучше всего используете только map. map естественно сортирует свои элементы в порядке ключа (время начала встречи в вашем случае), поэтому вы можете легко выполнять итерации в том же порядке. Поиск отдельного элемента - это O (log (n)). Это подходит, когда коллекция должна быть изменчивой.

В качестве альтернативы, вы можете просто сохранить элементы в vector, а затем отсортировать их, прежде чем выполнять итерацию. После сортировки вы можете найти отдельный элемент с помощью binary_search (O (log (n))) и, естественно, выполнять итерацию с превосходной производительностью (но все же O (c)). Сортировка стоит дорого, поэтому она подходит только тогда, когда сбор (в основном) неизменен.

Если вас не волнует порядок, в котором вы выполняете итерацию:

Просто используйте unordered_(multi)map - при правильном хешировании он будет быстрее, чем map.

Answer 2

Новелократ, вероятно, имеет это правильно.Идея - это контейнер встреч, доступный с ключом времени запуска.

Если это действительно тот случай, когда итерация последовательных элементов мультикарты слишком медленная, одна альтернатива - сохранить данные в списке, а затем отдельно сохранить мультикарту, где ключи могут использоваться для поиска shared_ptr илиитератор в список.Затраты на вставки и удаления увеличиваются, но оптимизируется доступ как для случайного поиска, так и для последовательной итерации.

Если вы не имеете дело с чрезвычайно большими объемами данных и строгими требованиями к производительности, одна карта может работать достаточно хорошо.В крайних случаях размещение данных в списке + с использованием карты или мультикарты для поиска обеспечивает более высокую производительность за счет дополнительного кода и вероятности возникновения ошибок, если ключи не синхронизированы с данными.