0

I am looking for a storage to index points in 2 dimensions. To be more specific, I would like to store the geometry of ways (or edges) in OpenStreetMap and have it searchable. Queries to the storage would be looking up geometry based on two endpoints of a way. This query would be run to reconstruct the geometry of a path found by an algorithm similar to Dijkstra, so the speed of geometry lookup is important.

Nodes in my case are just unsigned ints and geometry can be encoded as a string or as a vector of points, either way would work.

The number of nodes would be around 1 billion so keeping everything in memory does not work, so it would be nice to find an external or disk based storage.

I have already tried Stxxl but it doesn't seem to support non-POD types like string or vectors as values.

Thanks for suggestions in advance

4

1 回答 1

0

您可以通过维护两个单独的向量来模拟类似地图的行为。比如说，你有两<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 positionstring

<0, 6>, <6, 12>

如您所见，后面的不是必需"world"的"hello"。这样，对于任何新 <key, value>对，您只需更新第二个向量中的开始和结束位置（索引访问），然后将值放在第一个向量的末尾（不需要移位）。

编辑：代替vector (of pair of two 'size_type's)，您还可以使用map< int, pair<size_type, size_type> >which 弥补了我猜的更好的解决方案。任你选。

于 2012-09-04T11:09:53.633 回答