неупорядоченная карта — эквивалент LinkedHashmap в C ++?
У меня есть Java-программа, которую я хочу преобразовать в C ++. Итак, есть Linkedhashmap Структура данных используется в коде Java, и я хочу преобразовать ее в C ++. Есть ли эквивалентный тип данных для LinkedHashmap в С ++?
Я пытался использовать std::unordered_mapОднако он не поддерживает порядок вставки.
Решение
C ++ не предлагает шаблон коллекции с поведением, которое имитирует Java LinkedHashMap<K,V>, поэтому вам нужно будет поддерживать порядок отдельно от отображения.
Это может быть достигнуто путем сохранения данных в std::list<std::pair<K,V>>и ведение отдельного std::unordered_map<k,std::list::iterator<std::pair<K,V>>> карта для быстрого поиска предмета по ключу:
- При добавлении элемента добавьте соответствующую пару ключ / значение в конец списка и сопоставьте ключ с итератором.
std::prev(list.end()), - После удаления элемента по ключу найдите его итератор, удалите его из списка и затем удалите сопоставление.
- При замене элемента сначала найдите итератор списка из неупорядоченной карты, а затем замените его содержимое новой парой ключ-значение.
- При повторении значений просто повторяйте
std::list<std::pair<K,V>>,
Другие решения
Контракт порядка вставки для итерации ключа может быть достигнут с помощью сбалансированного дерева для производительности log (n). Это лучше, чем сохранение ключей в списке, так как удаление элемента требует n времени поиска. Моя мантра никогда не помещает то, что вы ищете в списке. Если это не нужно сортировать, используйте хеш. Если это должно быть отсортировано, используйте сбалансированное дерево. Если все, что вы собираетесь сделать, это итерировать, то список в порядке.
В С ++ это было бы std::map где ключ — ссылка на элемент, а значение — порядок вставки, ключи сортируются с использованием красно-черных деревьев. Увидеть: Есть ли отсортированный контейнер в STL?
Неупорядоченный Map или любой другой метод STL, встроенный в C ++, не может дать тот же порядок, что и LinkedHashMap, хотя вы можете поддерживать порядок вставки и обращаться к unordered_map, используя поддерживаемый порядок.
Ниже изображение, чтобы показать, как ведет себя unordered_map. У него нет порядка.
Карта — это дерево RB, и она дает отсортированный порядок, если используется итератор.
Отсюда и нет конкретного решения этого вопроса.
