std :: map против самописного словаря на основе std :: vector

Question

Я строю систему хранения контента для своего игрового движка и ищу возможные альтернативы для хранения данных.Поскольку это игра, очевидно, что производительность важна.Особенно учитывая, что различные объекты в движке будут запрашивать ресурсы у структур данных менеджера контента после их создания.Я хотел бы иметь возможность искать ресурсы по имени, а не по порядковому номеру, поэтому подойдет какой-то словарь.

Каковы плюсы и минусы использования std :: map исоздать свой собственный класс словаря на основе std :: vector?Существуют ли какие-либо различия в скорости (если да, то где производительность снизится? Т.е. добавление или доступ), и есть ли смысл выделять время на написание своего собственного класса?

Для некоторой предыстории того, что нужноСлучается: запись в структуры данных происходит только в одно время, когда двигатель загружается.Таким образом, в процессе игры никаких писем не происходит.Когда двигатель завершает работу, эти структуры данных должны быть очищены.Чтение с них может происходить в любое время, когда бы ни была создана сущность или поменялась карта.Одновременно может быть создано не более одного объекта или не более 20, причем каждому требуется переменное количество ресурсов.Размер ресурса также может варьироваться в зависимости от размера файла, который читается при запуске механизма, изображения являются самыми маленькими, а музыка - самой большой, в зависимости от формата (.ogg или .midi).

Answer 1

Карта: std::map имеет гарантированную логарифмическую сложность поиска.Обычно он выполняется экспертами и будет высокого качества (например, безопасность исключений).Вы можете использовать собственные распределители для пользовательских требований к памяти.

Ваше решение: оно будет написано вами.Вектор предназначен для непрерывного хранения с произвольным доступом по позиции, так как вы будете реализовывать поиск по значению?Можете ли вы сделать это с гарантированной логарифмической сложностью или лучше?У вас есть конкретные требования к памяти?Вы уверены, что можете правильно и эффективно реализовать алгоритм поиска?

3-й вариант: если ваш тип ключа string (или что-то дорогое для сравнения), также рассмотрите std::unordered_map, который имеет постоянный -временный поиск по значению в типичных ситуациях (но не совсем гарантированный).

Answer 2

Если вам нужна гарантия скорости std::map, а также низкое использование памяти std::vector, вы можете поместить свои данные в std::vector, std::sort и затем использовать std::lower_bound для поиска элементов.

Answer 3

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

Какчасто вы будете читать / писать на карте, и как долго каждый элемент будет на ней?Кроме того, вы должны учитывать, как часто вам нужно будет изменять размер и т. Д. Каждый из этих вопросов имеет решающее значение для выбора правильной структуры данных для вашей реализации.

В целом, одна из функций std, вероятно, будет той, которую вы хотите, если вам не нужна функциональность, которой нет ни в одной из них, или если у вас есть идея, которая может улучшить их временную сложность.

РЕДАКТИРОВАТЬ: На основании вашего обновления я согласен с KerrekSB что если вы используете C ++ 0x, тогда std::unordered_map будет хорошей структурой данных для использования в этом случае.Однако имейте в виду, что ваша производительность может ухудшиться до линейной сложности времени, если у вас есть конфликтующие хэши (это не может произойти с std::map), поскольку они будут хранить две пары в одном сегменте.Хотя это редко, вероятность этого очевидно увеличивается с количеством элементов.Поэтому, если вы пишете огромную игру, возможно, что std::unordered_map станет менее оптимальным, чем std::map.Просто соображение.:)