Хеш-карта и упорядоченный обход
Я должен реализовать с нуля в C ++ хэш-карту как полнофункциональный абстрактный тип данных. В частности, я должен предоставить итератор для этого контейнера данных, который мог бы проходить по всем записям в порядке возрастания идентифицирующих ключей. И эта часть меня смущает, я понятия не имею, как это сделать. Кстати, из-за функциональности хеширования я решил использовать отдельную цепочку с однонаправленными списками. Единственное решение, которое пришло мне в голову, — это создать еще один список, который бы связывал все элементы в соответствующем порядке, функциональность которого была бы обеспечена во время самого процесса вставки. Но мне кажется, что это сильно ухудшит преимущества хэширования, по крайней мере, в отношении вставки; особенно если смотреть на цель моего ADT, функция обхода будет использоваться относительно редко. Короче говоря, какое решение я должен предоставить? Обратите внимание, что я не могу использовать какие-либо специализированные библиотеки.
НОТА:
Я знаю, что такое хэш-карта и что она по своему академическому определению изначально неупорядочена. Возможно, мне следовало бы сказать это иначе, я должен создать гибридную, практичную ADT, которая будет состоять в основном из хеш-карты плюс некоторый дополнительный облегченный модуль, который обеспечит функциональность итератора, чтобы пользователь такого ADT мог переходить от время от времени записи в порядке возрастания ключей.
Решение
Хеш-карты изначально неупорядочены. Вот почему они обычно называются unordered_map в c ++. Итератор для хэш-карты посетит каждый элемент один раз, но в неопределенном порядке.
На практике вы, вероятно, либо не используете хеш-карту, либо используете какой-либо другой контейнер ассоциативных карт, например, красно-черное дерево. Или вы будете поддерживать параллельный упорядоченный индекс, если обновления происходят редко. Или создайте отсортированный индекс по требованию, если обновления происходят часто, но обходы редки.
Другие решения
Хеш-карты не сортируются по своей природе, поскольку весь смысл в том, чтобы использовать хэш, чтобы знать, где хранить значения.
Единственный способ увидеть это может быть Работа (с некоторыми затратами на производительность и удобство использования в реальном мире) — это если вы гарантируете, что хеш всегда увеличивается, то есть хеш является функцией порядка вставки и дает упорядоченные хеш-коды. Это позаботится только о не сталкивающихся хешах. Вам все еще нужно пройтись по списку внутри корзины в правильном порядке, так что для этого просто сохраняйте список отсортированным во время вставки
Может быть, это не сработает, это просто идея
Если нет, единственный другой способ — сохранить все значения в удобной для сортировки структуре и выполнять итерации оттуда. Если вы сделаете это в классе hashmap, это будет выглядеть так, как будто вы перебираете hashmap, но на самом деле это не так. Имейте в виду, что этот подход удвоит ваши требования к памяти во время итерации
Дайте нам знать, как это происходит, это странное требование