stxxl map <int, string>

Question

Я ищу место для хранения очков в 2-х измерениях. Чтобы быть более конкретным, я хотел бы сохранить геометрию путей (или ребер) в OpenStreetMap и иметь возможность поиска. Запросы к хранилищу будут искать геометрию на основе двух конечных точек пути. Этот запрос будет выполнен для восстановления геометрии найденного пути с помощью алгоритма, аналогичного Dijkstra, поэтому важна скорость поиска геометрии.

Узлы в моем случае - это просто неподписанные ints и геометрия могут быть закодированы в виде строки или в качестве вектора точек, в любом случае это сработает.

Количество узлов будет около 1 миллиарда, поэтому хранение всего в памяти не будет работать, поэтому было бы неплохо найти внешнее или дисковое хранилище.

Я уже пробовал Stxxl, но он не поддерживает типы не-POD, такие как string или векторы в качестве значений.

Спасибо за предложения, заранее

Answer 1

Вы можете моделировать карту как поведение, поддерживая два отдельных векторов. Скажем, у вас есть две пары <key, value><0, "hello">, <1, "world">. Первый vector (of char) затем содержит

h, e, l, l, o, \0, w, o, r, l, d, \0 

второй vector (of pair of two 'size_type's) содержит begin position и one past end position каждого string, как это,

<0, 6>, <6, 12> 

Как вы можете видеть, это не требуется, чтобы "world" приходит после "hello". Таким образом, для любого нового <key, value> пары, вы просто обновить начальную и конечную позицию во втором векторе (индексированного доступа), и поместить значение в конце первого вектора (не требуется переключение).

EDIT: Вместо vector (of pair of two 'size_type's) вы также можете использовать map< int, pair<size_type, size_type> >, который, в свою очередь, подходит для лучшего решения. Выбирайте.