[review] a mini-review of containers
Hi Ion & John, I apologize for not having time to do a full review. I base these comments mainly on the documentation. I have been using the flat_map/flat_set stuff for years, both in my own PhD work and in production code in my company. A. I find the motivation sufficient; I guess the new allocator concept in C++11 would allow one to use interprocess allocators, but as this won't work with older compiler, I can see the need. Also, since the standard does not e.g. guarantee nothrow of default constructors, this library provides an escape route if one wishes to have portable code. The recursive structure is also a nice feature. B. The new containers are very useful. I have not used stable vector before, but I note that boost::ptr_vector provides similar guarantees. C. slist should probably be called forward_list like in the new standard, and should probably be interface compatible with the standard design. D. I skimmed some of the unit-tests. I saw that some sections are commented out. Maybe a little more testing could be done. E. I didn't look at the map/set implementation; do you use the same optimization as Boost.MultiIndex that saves the color in the parent pointer (as a bit). F. I noticed that you use std::reverse_iterator. Why not use boost::reverse_iterator? IIRC, it has some minor benefits. G. flat_xxx. (a) We already discussed the issue of exposing the underlyng container. I think that would be most natural, and provides use with an escape hatch when they need it. (b) I think all these containers should allow one to decide the wrapped sequence. I have several types of sequences I would like to be able to use. Sure it takes some work to handle alocators and such, but it makes these much more useful IMO. (c) At some point, long time ago, I suggested that one should be able to construct a set/map with an already sorted sequence. This was based on actual use cases; one sometimes have access to an already sorted sequence. I think the most elegant way to support this would be to make a new constructor that forwards; that is, use the same approach as boost::optional such that we can say flat_xxx cont( boost::in_place(...) ); ------------------------------------- So, should this library be accepted into Boost? Yes. But I would like to see G.b and G.c addressed first. kind regards Thorsten
El 12/08/2011 14:07, Thorsten Ottosen escribió:
Hi Ion & John,
I apologize for not having time to do a full review. I base these comments mainly on the documentation.
Thanks for your time Thorsten.
C. slist should probably be called forward_list like in the new standard, and should probably be interface compatible with the standard design.
My idea is to add another container with forward_list guarantees and standard interface. slist would be there for backwards compatibility (with constant-time size()).
D. I skimmed some of the unit-tests. I saw that some sections are commented out. Maybe a little more testing could be done.
Ok.
E. I didn't look at the map/set implementation; do you use the same optimization as Boost.MultiIndex that saves the color in the parent pointer (as a bit).
Yes, it's based on Boost.Intrusive rbtree container and that optimization is activated.
F. I noticed that you use std::reverse_iterator. Why not use boost::reverse_iterator? IIRC, it has some minor benefits.
Ok, I will look at it.
G. flat_xxx. (a) We already discussed the issue of exposing the underlyng container. I think that would be most natural, and provides use with an escape hatch when they need it.
Right, would this be acceptable: flat_xxx flat; //Move returned flat_xxx::impl_t i(flat.extract_implementation()); //Modify i.insert() std::sort(i.begin(), i.end()); //Integrate it again, checks in //debug mode flat.inject_implementation(::boost::move(i))
(b) I think all these containers should allow one to decide the wrapped sequence. I have several types of sequences I would like to be able to use. Sure it takes some work to handle alocators and such, but it makes these much more useful IMO.
Yes, we should decide the underlying interface, say std:vector C++11.
(c) At some point, long time ago, I suggested that one should be able to construct a set/map with an already sorted sequence. This was based on actual use cases; one sometimes have access to an already sorted sequence. I think the most elegant way to support this would be to make a new constructor that forwards; that is, use the same approach as boost::optional such that we can say
flat_xxx containers have those functions: flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, , const Pred& comp = Pred(), const allocator_type& a = allocator_type()) flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const Pred& comp = Pred(), const allocator_type& a = allocator_type()) I don't know if that would be enough for your use cases. Best, Ion
participants (2)
-
Ion Gaztañaga -
Thorsten Ottosen