search for multiple indecies with Boost Multi-Index

Question

how do I limit the search in a boost::multi_index by the result of a previous search? As an example: suppose I have a rectangle class with an internal value like this:

    class MyRect
    {
    public:
        int    width;  
        int    height; 

        double value;
    }

and I need a data structure of such object to answer queries like "given an input_rectangle - which object MyRect is contained in that rectangle and has the highest value?"

I could use a 'multi_index' like this:

    struct given_value{};
    struct given_width{};
    struct given_height{};

    typedef multi_index_container<MyRect,
        indexed_by<
            ordered_non_unique< tag<given_value>, 
                member<MyRect, double, &MyRect::value>,
            ordered_non_unique< tag<given_width>, 
                member<MyRect, int, &MyRect::width>,
            ordered_non_unique< tag<given_height>, 
                member<MyRect, int, &MyRect::height>, >
        >
    > MyDataStructure;

    typedef MyDataStructure::index<given_width>::type MyDataStructureGivenWidth;
    typedef MyDataStructureGivenWidth::iterator WidthIterator;

If my input_rectangle has width input_width I could use something like this:

WidthIterator start_iter = data_object.get<given_width>().begin();
WidthIterator end_iter   = data_object.get<given_width>().upper_bound(input_width);

But how do I limit the search for the coresp height by the two given iterators? (And after that find the object with the highest value in that result?)

Answer 1

I don't think you can do an inplace limitation.
Store the resulting iterators of the matching widths query in another container and use that container to find the matching heights with remove_if. Then use max_element to find the largest.

If you store the elements as pointers, you could use the same MIC to store the results.

Answer 2

If I understand your problem correctly, there may be a simpler solution. Just put your MyRects into an STL-Set ordered by value (need to define comparison operator or custom comparison function). The you can create a custom predicate that and use that checks if a given MyRect is within a certain range. Then you use the STL-Algorithm find_if, and hand it the custom predicate. If you make sure that it traverses the sequence in decreasing order (e.g. by using reverse_iterator), it should return the MyRect you are looking for.

Hope that is understandable and applies to your problem.