#c
#c
Вопрос:
У меня ситуация, когда я хочу использовать ассоциативный контейнер, и я решил использовать std::unordered_map , потому что вполне возможно, что этот контейнер можно использовать для хранения миллионов или более элементов. Но теперь мне также нужно выполнить итерацию по порядку. Я рассматривал возможность того, чтобы типы значений связывались друг с другом в списке, но теперь у меня возникнут проблемы с управлением памятью.
Должен ли я изменить контейнер, скажем, на std::map? Или просто выполните итерацию один раз по моей unordered_map, вставьте в вектор и отсортируйте, затем выполните итерацию? Довольно маловероятно, что мне нужно будет многократно выполнять итерацию упорядоченным образом.
Комментарии:
1. «Довольно маловероятно, что мне потребуется многократно выполнять итерацию упорядоченным образом». — Из интереса, когда вы выбирали
unordered_map, думали ли вы, что маловероятно, что вам вообще понадобится выполнять итерации по порядку? Я бы сказал, чтоmapэто самый простой доступный вариант и, следовательно, базовый уровень, по которому вы должны измерять оптимизации (например,unordered_mapплюс отдельная сортировка или упорядочение).2. @Steve: Я знал, что мне придется, но забыл, так как это не обязательно для первого этапа.
3. конечно, если бы я взял на себя труд написать
hashфункцию для своего ключа, я бы тоже стремился придерживатьсяunordered_map🙂4. @Steve: На самом деле я этого не делал. Просто перенаправил некоторые хэши в стандартный хэш.
Ответ №1:
Ну, вы знаете O() различных операций двух выбранных вами альтернатив. Вы должны выбирать на основе этого и проводить анализ затрат и выгод, основанный на том, где вам нужна производительность, и какой контейнер лучше всего подходит для этого.
Конечно, я не мог знать достаточно, чтобы выполнить этот анализ за вас.
Ответ №2:
Вы могли бы использовать Boost.Мультииндекс, определяющий как неупорядоченный (хэшированный) индекс, так и упорядоченный индекс в одной и той же базовой коллекции объектов.
Возможные проблемы с этим — отсутствует естественное отображение из существующей модели ассоциативного контейнера, и это может быть излишним, если вам не нужен второй индекс постоянно.