Какой контейнер из std::map или std::unordered_map подходит для моего случая
Я не знаю, как красное черное дерево работает со строковыми ключами. Я уже видел это с номерами на YouTube, и это меня сильно расстроило. Однако я очень хорошо знаю, как работает unoredred_map (внутренняя часть хеш-карт). std::map остается для меня эзотерическим, но я прочитал и проверил, что если у нас не так много изменений в std:: map, он может превзойти хэш-карты.
Мой случай прост, у меня есть std:: map of <std::string,bool>, Ключи содержат пути к элементам XML (пример ключа: "Instrument_Roots/Instrument_Root/Rating_Type"), и я использую логическое значение в моем синтаксическом анализаторе SAX, чтобы узнать, достигли ли мы определенного элемента.
Я строю эту карту "только один раз"; и затем все, что я делаю, это использую std:: find для поиска, существует ли определенный "ключ" ("путь"), чтобы установить для его логического значения значение true, или для поиска первого элемента, который имеет "true" в качестве связанного значения, и использую его соответствующий "ключ", и, наконец, я установил для всех логических значений значение false, чтобы гарантировать, что только один "ключ" имеет "истинное" логическое значение.
2 ответа
Вам не нужно понимать, как работают красно-черные деревья, чтобы понять, как использовать std::map, Это просто ассоциативный массив, в котором ключи расположены по порядку (лексикографический порядок, в случае строковых ключей, по крайней мере, с функцией сравнения по умолчанию). Это означает, что вы можете не только искать ключи в std::mapВы также можете делать запросы, которые зависят от порядка. Например, вы можете найти самый большой ключ на карте, который не больше, чем у вас есть ключ. Вы можете найти следующий больший ключ. Или (опять же в случае строк) вы можете найти все ключи, которые начинаются с того же префикса.
Если вы перебираете все пары ключ-значение в std::map, вы увидите их в порядке по ключу. Это может быть очень полезно, иногда.
Дополнительная функциональность поставляется по цене. std::map обычно медленнее, чем std::unordered_map (хотя и не всегда; для больших строковых ключей издержки на вычисление хэш-функции могут быть заметны), а базовая структура данных имеет определенное количество служебных данных, поэтому они могут занимать больше места. Обычный совет заключается в использовании std::map если вы обнаружите, что ключи заказаны как необходимые или даже полезные.
Но если вы оценили и пришли к выводу, что для вашего приложения, std::map тоже быстрее, тогда иди и пользуйся:)
Иногда полезно иметь карту с отображенным типом bool, но только если вам нужно различать ключи, соответствующие значения которых false и ключи, которых нет на карте вообще. По сути, std::map<T, bool> (или же std::unordered_map<T, bool>) предоставляет троичный выбор для каждого возможного ключа.
Если вам не нужно различать два false случаев, и вы не часто меняете значение ключа, тогда вам может быть лучше std::set (или же std::unordered_set), которая является точно такой же структурой данных, но без накладных расходов bool в каждом элементе. (Хотя только один бит bool Это полезно, соображения по выравниванию могут в конечном итоге использовать 8 дополнительных байтов для каждой записи.) Однако, за исключением места для хранения, не будет большой (если таковая имеется) разницы в производительности, хотя.
Если вы действительно нуждаетесь в троичном кейсе, то вам следует сделать это enum а не bool, Что true а также false значит в контексте вашего использования? Я предполагаю, что они не имеют в виду "правда" и "ложь". Вместо этого они означают что-то вроде "является путем атрибута" и "является путем элемента". Это различие можно было бы сделать намного более четким (и, следовательно, менее подверженным несчастным случаям), используя enum PathType {ATTRIBUTE_PATH, ELEMENT_PATH};, Это не потребует дополнительных ресурсов, так как bool в любом случае занимает восемь байтов памяти (из-за выравнивания).
Между прочим, нет никакой гарантии, что базовая структура данных является именно красно-черным деревом, хотя гарантии производительности было бы трудно достичь без какого-либо самобалансирующегося дерева. Я не знаю такой реализации, но было бы возможно использовать k-арные деревья (для небольшого k), чтобы использовать, например, операции сравнения векторов SIMD. Конечно, это должно быть настроено для соответствующих типов ключей.
Если вы хотите понять красно-черные деревья, вы можете сделать хуже, чем стандартный учебник Роберта Седжвика по алгоритмам. На веб-сайте книги вы найдете краткое иллюстрированное объяснение в главе о сбалансированных деревьях.
Я бы порекомендовал вам использовать std::unordered_set, потому что вам действительно не нужно хранить этот логический флаг, и вам также не нужно хранить эти теги xml в отсортированном порядке, поэтому std::unordered_set кажется мне логичным и наиболее эффективный выбор.