[boost] re: How much should I care about allocators?

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

Dan,

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 
requirement!

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

Hope this help,
        Michael
-- 
___________________________________
Michael Stevens Systems Engineering
Navigation Systems, Estimation  and
                 Bayesian Filtering
    http://bayesclasses.sf.net
___________________________________