C++ Integer Trie реализация с использованием hash_map для уменьшения потребления памяти
Я должен реализовать три кодов заданной фиксированной длины. Каждый код представляет собой последовательность целых чисел, и, учитывая, что некоторые шаблоны являются обычными, я решил реализовать Trie для хранения всех кодов. Мне также нужно перебирать коды, учитывая их лексикографический порядок, и я рассчитываю работать с миллионами (возможно, миллиардами) кодов.
Вот почему я рассмотрел реализацию этого конкретного Trie как словаря, где каждый ключ является индексом данного префикса. Допустим, у ключа 0 есть список его дочерних префиксов, и для каждого я сохраняю соответствующую запись в словаре... Пример: если моя первая вставка - это код 231, то словарь будет выглядеть так:
[0]->{(2,1)}
[1]->{(3,2)}
[2]->{(1,3)}
Таким образом, если моя вторая вставка будет 243, словарь будет обновлен следующим образом:
[0]->{(2,1)}
[1]->{(3,2),(4,3)} *Here each list is sorted using a flat_map
[2]->{(1,endMark)}
[3]->{(3,endMark)}
Моя проблема в том, что я использовал вектор для этой цели и потому что наличие всего словаря в непрерывной памяти позволяет мне иметь лучшую производительность при переборе по нему. Теперь, когда мне нужно работать с БОЛЬШИМИ экземплярами моей проблемы, из-за изменения размера вектора я не могу работать с миллионами кодов (потребление памяти может достигать 200 ГБ). Теперь я попробовал скудный хэш от Google для вектора, и мой вопрос: есть ли у вас какие-либо предложения? любая другая альтернатива в виду? Есть ли другой способ работы с целыми числами в качестве ключей для повышения производительности? Я знаю, что у меня не будет никакого столкновения, потому что каждый ключ будет отличаться от остальных.
С наилучшими пожеланиями, Квентин