Re: [boost] interest in sorted vector containers?

From: Nigel Stewart (ns_at_[hidden])
Date: 2006-08-02 17:11:00

Lewis,

Very interested!

Do you have any data handy on the time and space trade offs using
say vmap versus std::map?  I've been implementing something similar
to vmap in query-intensive context using binary search, in the hope
of avoiding the memory/cache-miss overhead with the std::map tree.

The model I'm working with is to do insertion into a std::map and
then flatten it into a std::vector once insertion is done.

Nigel

> Hi Everyone-
> 
> Is there any interest in providing Boost container classes with the same 
> functionality as set/map implemented with sorted vectors? I have four 
> simple classes vset, vmap, vmultiset, vmap which do this. It seems like 
> it would be quite useful, especially since, in my experience, set and 
> map are heavily overused because of their convenience even when the 
> insertion efficiency and iterator invalidation guarantees are not 
> necessary. My classes provide the same interface as the STL equivalent, 
> with additional functions such as nth_element() that take advantage of 
> the random access iterators, and some conveniences like key-only and 
> value-only iterators for vmap and vmultimap. I can post the code with a 
> first attempt at making it appropriate for Boost if people think it is 
> worth it?
> 
> -Lewis