On 7/29/06, Lewis Hyatt <lhyatt@princeton.edu> 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