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

From: Andrei Alexandrescu (andrewalex_at_[hidden])
Date: 2002-02-09 16:19:44

> 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.

Yes. As you point out yourself below, the abstraction you're looking at is
"storage".

> 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

I'm not sure I make sense of this all, but the way I see it is:

* You abstract Storage. The Storage has an allocation method, which can be
in-situ, use new, use malloc etc. In C++ defining in-situ allocation from
the outside is not possible but if you encapsulate it in Storage you don't
care about that much. Also, for the same allocation method you can use
different storage strategies (e.g, store size and/or capacity in-situ or
dynamically). So a good design is to pass an allocator to Storage, and have
InSituStorage ignore it.

> 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.

Of course it is practical. As you say you come from Fortran, there's a large
underground movement who cares /only/ about fixed-size vectors :o).

> 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

I believe Storage parameterized by Allocator is better.

> 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
> };

See above. With your approach you will have to duplicate all the Storage
code if you want to use (1) malloc or SysAlloc instead of new (2) another
way of storing the additional data while still using new.

Andrei

---------------------------------
Check out THE C++ Seminar:  3 Days with 5 Experts
http://www.gotw.ca/cpp_seminar/