[boost] [review] a mini-review of containers

Subject: [boost] [review] a mini-review of containers
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2011-08-12 08:07:17

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