[boost] [MultiIndex] STL algorithm support for multi_index_containers

Subject: [boost] [MultiIndex] STL algorithm support for multi_index_containers
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-11-09 08:44:25

Hello,

we have added support for using multi_index ordered index iterators in lieu of random access iterators in standard algorithms that require sorted ranges, e.g. lower_bound, upper_bound, equal_range, and binary_search. This is useful when using these iterators in generic algorithms that internally call lower_bound/upper_bound/etc. Our implementation is attached. We are currently overloading std::lower_bound/... which is illegal. I propose introducing a boost::lower_bound/..., where we can ignore the C++ standard restriction, and where the standard implementation forwards to std::lower_bound.

Runtime is O(log N), where N is the total number of elements in the container, rather than, as it would be optimal, the number of elements within the (sub)range on which the algorithm is called. The problem is that the red-black tree nodes do not store the tree level number, so we cannot find the parent node that encompasses the whole subrange in linear time. I am not sure this is practically relevant. In any case, using the sortedness of the tree rather than treating the iterators as arbitrary bidirectional iterators is a step forward.

Any opinions?

Regards,

Arno

--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229