interest in sorted vector containers?
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
On 7/29/06, Lewis Hyatt <lhyatt@princeton.edu> wrote:
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?
I'm interested!
-Lewis _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Cory Nelson http://www.int64.org
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
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).
they are essentially already in boost, they are just typedefs for boost::transform_iterator (although you have to provide select1st and select2nd function objects, but altogether it's only a few lines of code). -lewis
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.
I think that std::map is well suited to the interleaved insertion and lookup use-case, but I think the advantage of having a vmap for the query-intensive situation is an attactive option in many situations. Nigel
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?
Did the Summer of Code project on this fallthrough? Or is someone actually working on this already? http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summer... flat_map, flat_set, etc, are probably better names. Kevin
On 7/30/06, Kevin Spinar <spinarkm@gmail.com> wrote:
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?
Did the Summer of Code project on this fallthrough? Or is someone actually working on this already?
http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summer...
It doesn't appear to have made the final cut. See http://code.google.com/soc/boost/about.html
flat_map, flat_set, etc, are probably better names.
vector_map, vector_set, etc? --Beman
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
participants (8)
-
Beman Dawes -
Cory Nelson -
Deane Yang -
Kevin Spinar -
Lewis Hyatt -
Lewis Hyatt
-
me22 -
Nigel Stewart