Re: [boost] interest in sorted vector containers?

From: me22 (me22.ca_at_[hidden])
Date: 2006-07-29 23:29:24

On 7/29/06, Lewis Hyatt <lhyatt_at_[hidden]> wrote:
> Is there any interest in providing Boost container classes with the same
> functionality as set/map implemented with sorted vectors?
>
These are fairly common things, so I think they'd be good in boost.

> I have four
> simple classes vset, vmap, vmultiset, vmap which do this.
>
I'm not convinced those names are the best.  I can't currently do
better, but I'm sure someone will.

One open question though: should they be forced to use vector?  Would
it be worth it to make it be map_adapter< vector< pair<key,data> > >
(or similar) instead of vmap< key, data >?

> 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.
>
The most efficient usage pattern for a vmap is all the insertions,
sorting, then all the lookups.  The 'obvious' interface would make the
sorting the equivalent of an insertion sort, which could easily be
terribly inefficient (and might be a reason to try deque instead of
vector, in cases).  That said, I'm not sure the butchering of the
invariant and interface needed to allow the 2-step process would be
worth it.  Though I suppose the sorting could be made lazy without
changing the interface.  OTOH, for interleaved insertion and lookup
would turn to nlogn instead of just n for the insertions in the lazy
method, but for that case perhaps the ordinary map's logn is better
anyways.

> 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 think those key-only and value-only iterators would have value
outside just this library and would perhaps be better as a more
general separate utility (so they could be used on ordinary maps as
well).

Mostly just thinking out loud,
~ Scott McMurray