Boost logo

Boost :

From: Michael Stevens (mail_at_[hidden])
Date: 2005-03-21 03:53:28


I looked into allocators last year when implementing uBLAS's storage
abstraction using allocators. You should definitely make use of the ISO
standard text when working with allocators!

On Monday 21 March 2005 04:19, Dan Rosen <dan.rosen_at_[hidden]> wrote:

> In other words, to respect the allocator I've been given, I need to
> make sure my internal node structure uses the rebound node allocator's
> pointer and value types, and so forth. So my first question is, is
> this assumption correct?
This is correct but requires a lot of library programmer discipline!

> The reason I ask is that looking over the
> standard library implementation that comes with gcc 4.0, I noticed
> that their implementation of std::list<> has nodes which contain
> straight pointers, rather than the allocator typedef equivalents. To
> me that seems to contradict my assumption, assuming the gcc
> implementation is correct.

GCC is correct. There is a get out clause in the library standard. Look at
section 20.1.5 "Allocator requirements" paragraph 4:

Implementations of containers described in this International Standard are
permitted to assume that their Allocator template parameter meets the
following two additional requirements beyond those in Table 32. All
instances of a given allocator type are required to be interchangeable and
always compare equal to each other. The typedef members pointer,
const_pointer, size_type, and difference_type are required to be T*, T
const*, size_t, and ptrdiff_t, respectively.

I suspect many implementation (including those not in the standard) have this

> My second question is about allocator's construct() method. The
> implementation of std::allocator has construct() invoking the copy
> ctor using placement new(). That much is self-explanatory. It also
> seems reasonable to me that allocator does not have construct()
> methods taking arbitrary parameters. But I'm not sure I understand the
> reason why it does not have a construct() method to invoke an object's
> default ctor.?

In Table 32 "Allocator requirements" construct is specified as
a.construct(p,t) Effect: new((void*)p) T(t)

>From this I conclude the construct is semantically identical to calling
placement new. In effect construct does nothing other then provide a nice bit
of syntax. I could just as well use placement new syntax directly or indeed
call placement new for any other constructor such as the default constructor.

> What that implies to me, and seems to be supported by
> gcc's list implementation, is that the nodes in my tree mustn't have a
> default ctor that actually does anything, because the only way to
> properly initialize objects using an allocator is through copying. Is
> that correct

I think not. My interpretation is that allocators require that their
value_type is Copy Constructable but place no restriction on other ways they
may be constructed.

That said, STL containers have been carefully designed to avoid the need
default construct an object which will be subsequently assigned to. They can
keep memory in an uninitialised state until an element is needed and then use
copy construction.

All the standard containers require their value_type to be Assignable but not
Default Constructable. Interestingly no mention is made of Copy Constructable
in the value_type requirements. I assume this is inherited in the Allocator

Hope this help,

Michael Stevens Systems Engineering
Navigation Systems, Estimation  and
                 Bayesian Filtering

Boost list run by bdawes at, gregod at, cpdaniel at, john at