On Mon, Jan 7, 2013 at 3:57 PM, Szymon Wojciechowski <sw10@interia.pl>wrote:
On Wed, Jan 2, 2013 at 4:46 PM, Szymon Wojciechowski wrote:
Hi,
I would like to propose to add new data structure - order statistics
"Gottlob Frege" <gottlobfrege@gmail.com> pisze: tree.
Briefly, it is container which allows logarithmic inserting, searching and erasing as in set, but additionally it permits to access elements via numerical value - key order. I have some ready implementation with all appropriate functions (without their all overloaded forms) with gtest regression list, but the code isn't boostified. The regression passes on gcc 4.6.3 and vs2010.
Is there anybody interested in?
Best regards, Szymon Wojciechowski
This should be compared against using boost multi-index. I suspect it has significant differences, but might still be enlightening. Tony
Could you explain to me, what do you mean, please?
Best regards, Szymon Wojciechowski
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Basically both an order statistics tree and boost multi-index are examples of containers with multiple indices. I suspect there may be interesting results from a compare/contrast type of study. Boost MultiIndex allows indexing of a container via any number/type of indices. So you could have a container indexed via key, and also indexed via integer. Now the difference, I think, is that MultiIndex uses independent indexes - changing a entry's key from "alpha" to "beta" doesn't change its integer index from 1 to 2. So that is a significant difference. Might be worth mentioning in docs or somewhere, just to avoid confusion. But furthermore, I could probably implement the same behaviour as a order statistics tree by using Boost.MultiIndex internally (and maintaining the interrelationships of the indices as needed). Would that be drastically less efficient? And also, how do the interfaces compare? Should there be any alignmen/consistency t in the interfaces, so that some template code could use either? Not sure how much template code exists that requires "any container with 2 indices, one of which is an int". Probably consistency of interface is more important for learning/understanding/remembering than for template code. Tony