Boost.MultiIndex spatial operations

I needed a spatial map for an application. I found Boost.MultiIndex.

I followed its tutorial and understood how to create a type:

typedef boost::multi_index_container<MapNode,
    indexed_by<
        ordered_non_unique<member<MapNode, int, &MapNode::X>>,
        ordered_non_unique<member<MapNode, int, &MapNode::Y>>
    >
> Map_T;

And how to insert to it:

Map.insert(Node);

How do I retrieve a value based on its x and y coordinates? 开发者_JAVA技巧and how do I check if there is a value there?

---

First of all, you do not need boost::multi_index to solve this problem. Simply overload operator< for your type MapNode and use std::set (resp. std::map if multiple nodes with identical coordinates can occur). Therby, operater< compares (e.g.) for x-values first. Iff they are equal, proceed comparing the y coordinate.

There is only one reason for using boost::multi_index: If different access methodes are required. For instance, if you want an additional "view" where the nodes are first sorted by y and than by x too. However, the member approach of multi_index (as in your code above) is not a good idea. Use identity twice, but provide two different comparison functions. Details can be found in the boost docu.

Finally, all these approches may not be the best possible ones - depending on your application. Specialized data structures are e.g. described in the book "Computational geometry" by Berg et. al. Unfortunaetlly, I do not know any free implementation of these algorithms...