Существует ли непрерывно хранимая структура данных хэш-карты?

Question

Думайте о коллекциях различных типов как Position, Color, Name, Экземпляры могут быть связаны с использованием того же ключа в коллекции. Ключи являются глобальными уникальными идентификаторами длиной 64 бита. В настоящее время я использую хэш-карту, но это не идеально.

// custom types
struct Position { float x, y, z; bool static; };
enum Color { RED, BLUE, GREEN };

// collections
std::unordered_map<uint64_t, Position> positions;
std::unordered_map<uint64_t, Color> colors;
std::unordered_map<uint64_t, std::string> names;

// add some data
// ...

// only access positions collection,
// so the key is not needed here
for (auto i = positions.begin(); i != positions.end(); ++i) {
    if (i->second.static) continue;
    i->second.x = (rand() % 1000) / 1000.f;
    i->second.y = (rand() % 1000) / 1000.f;
    i->second.z = (rand() % 1000) / 1000.f;
}

// access to all three collections,
// so we need the key here
for (auto i = positions.begin(); i != positions.end(); ++i) {
    uint64_t id   = *i->first;
    auto position = i->second;
    auto color    = colors.find(id);
    auto name     = names.find(id);
    if (color == colors.end() || name == names.end()) continue;
    draw(*name, *position, *color);
}

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

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

Я думаю, что структура данных должна внутренне использовать массив. Какой тип данных мне следует использовать здесь? И есть ли такая структура данных, реализованная в стандартной библиотеке C++?

Answer 1

Создать unordered_map смещать в std::vector,

Храните свои элементы в std::vector, Если вы хотите удалить элемент, поменяйте его местами с последним элементом std::vectorи удалите последний элемент. Пройти через unordered_maps, которые хранят индексы в вашем std::vector и исправьте те, которые указывали на последний элемент, чтобы указать, где находится последний элемент.

Удаление элемента теперь O(n). Если вы удалите кучу элементов одновременно, вы можете сделать все из них за один O (n) проход с небольшим творческим потенциалом.

При добавлении элемента остается O(1).

Итерация по всем элементам включает в себя итерацию по std::vector, Если вам нужно хеш-значение во время итерации, сохраните его там избыточно или вычислите его на лету.

Обернуть std::vector а также std::unordered_map за тип, который обеспечивает соблюдение вышеуказанных правил, так как в противном случае инварианты никогда не будут сохраняться, который выставляет map-подобный интерфейс внешне.

В качестве альтернативы удалению O (n) создайте параллель std::vector хранения std::unordered_map<???>::iterators. Внимательно следите за тем, когда в std::unordered_map (перефразировка является детерминированной, но вы должны решить, когда это произойдет самостоятельно), и когда это перестроит (как все iterators будет аннулирован перефразировкой). Перефразы происходят редко, поэтому амортизированные постоянные затраты¹. Когда вы хотите стереть, вы можете обновить индекс в unordered_map в O (1) раз (не забудьте обновить второй std::vector а также - замена позиции с последнего на удаленный элемент). Вы можете хранить это в том же std::vector как необработанные данные, но это увеличит их объем (что замедлит итерацию).

---

¹ Переполнения происходят, когда контейнер проходит max_load_factor()*bucket_count() размер. bucket_count затем экспоненциально растет, и элементы перемещаются. Очень похоже на std::vectorВ алгоритме роста это гарантирует общее количество перемещенных элементов по линейному количеству элементов, поэтому он поддерживает постоянную вставку в амортизированном виде. Ручная перестройка вашей обратной таблицы не дороже, чем перемещение всех существующих элементов, поэтому она также вносит амортизированный постоянный фактор времени вставки.