stxxl map<int, string>

Question

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

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

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

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

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

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> В паре вы просто обновляете начальную и конечную позиции во втором векторе (индексированный доступ) и помещаете значение в конец первого вектора (смещение не требуется).

РЕДАКТИРОВАТЬ: вместо vector (of pair of two 'size_type's)Вы также можете использовать map< int, pair<size_type, size_type> > что компенсирует лучшее решение, я думаю. Сделайте ваш выбор.