Re: [boost] Submission: Fixed-Capacity STL Containers Library (Re:STLcontainer of fixed capacity but

From: Synge Todo (wistaria_at_[hidden])
Date: 2002-02-09 06:54:42

Dear Andrei,

From: "Andrei Alexandrescu" <andrewalex_at_[hidden]>
Date: Fri, 8 Feb 2002 07:08:45 -0800
> > I believe that non-POD objects are now constructed and destructed in a
> > proper way.  As for the alignment problem, however, I'm not sure if
> > the current implementation is portable or not.
> 
> The implementation is not portable, and potentially wasteful (jeopardizing
> the very intent of fixed_vector). I privately emailed you (and Ralf) some
> stuff that might be of interest. As you follow Variant.zip, also look up
> explanations in
> http://oonumerics.org/tmpw01/alexandrescu.pdf.

Thank you very much!  I was deeply impressed by your articles and
codes!  Your technique on alignment problem in "discriminated unions"
is very powerful, elegant, and portable.  I think your implementation
can be adopted in fixed-capacity containers.  I heard from Ralf that
he already started to work on "non_initialized_array" by using your
technique.  I hope he could help me a lot on completing the
implementation.

> 2. Duplicating code to treat PODs and non-PODs is NOT the way to go. Use one
> implementation for both. You may want to segregate implementations in a
> limited way just for optimization's sake.

I agree.  There is little need to split code for two different types,
once the above alignment technique is adopted.

> I wonder why wouldn't you give it a shot at writing a full-blown vector in
> which your storage method is a policy. You're not that far from such an
> approach (your fixed_vector_base basically defines your storage policy).

Unfortunately, a good design always comes into my mind only after
finishing one (or more) concrete and specific implimentation(s).
Mayby, I was so spoiled by my long career as a Fortran programmer.

On writting fixed_capacity_vector class, however, I always realized
that what I was writting is a kind of "allocator".  I think one of the
essential differences between the standard allocator and the present
fixed-capacity concept is: a standard allocator object doesn't have
any data of its own, while the latter does.  Formally speaking, this
difference is orthogonal to the "fixed-capacity policy", and also
nearly orthogonal to the dynamic or static allocation policy.

policy
allocator (shared or not)    : provide constant-time swap and slice in
                               list or not
fixed-capacity               : capacity is fixed (at compile time) or not
dynamic or static allocation

Of cource, if data are allocated in a static way, the capacity is
fixed at the same time.  In addition, I'm not sure if a std::vector
with (compile-time) fixed capacity is practically useful or not.
Thus, the orthogonality is far from perfect.

On the other hand, in practice, we might need only one category of policy:

  A: shared allocator, growable capacity, dynamic allocation (= std::vector)
  B: non-shared allocator, fixed capacity, static allocation

One possible implementation for this policy design, I think, is
introducing an additional abstraction layer between std::vector and
std::allocator

template<class T, class Storage = DynamicStorge<T> >
vector {
Storage storage;
...
};

template<class T>
DynamicStorage {
allocator<T> alloc;
allocate();
void swap(); // swapping pointer
... etc
};

template<class T, std::size_t N>
StaticStorage {
non_initialized_array<N> data;
allocate();
void swap(); // copying elements;
... etc
};

Synge Todo
wistaria_at_[hidden]