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@gmail.com> 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.?
From this I conclude the construct is semantically identical to calling
In Table 32 "Allocator requirements" construct is specified as a.construct(p,t) Effect: new((void*)p) T(t) 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 ___________________________________