>You missed the point : if rebind<U> would define "other" as allocator<U>
>(as in the original post), not myalloc<U>, that copying won't help (even
>if it works), as allocator<U> does not know anything about private heap.

I'm not quite sure that I follow, an allocator that defined "other" as
always allocator<U> and not myalloc<U> would result in the custom
allocator being completely broken (at least as far as the standard
goes).

Consider:

std vector<int, myalloc<double> > v;

this is allowed by the standard, the first thing any container should
do is rebind the passed allocator type to the type it actually needs:
in this case myalloc<int>, but could equally be
myalloc<my_internal_struct>.

In other words to be conforming the allocators rebind member must
return an object of type myalloc<U> and further:

typename myalloc<T>::template rebind<U>::other::template
rebind<T>::other

must be myalloc<T>.


How allocators handle instance data is implimentation defined, but:

typedef myalloc<T> alloc_type;

alloc_type x1;
typename alloc_type::template rebind<U>::other y(x1);
alloc_type x2(y);

then:

x1 == y

and

x1 == x2


The implication being that each of x1, y and x2 use the same (or
related) heap if they are instance based - although not necessarily so
- its up to the allocator implimentor, the point is that all
allocators used by the container must be *copies* of the original, so
if the allocator internals allow for heap sharing between x1, y and x2
above, then they will do so - it is certainly possible to impliment
allocators that do this.

Of course all this means nothing if the compiler does not support the
language features required - whatever you do then will necessarily be
a non-standard cludge.  Personally I think I prefer byte based
allocators - because at least then instance based heaps are possible -
but I can see the other point of view - one trick for allocator users
is to always use allocator<char>, then it doesn't matter which cludge
the implimentation has chosen.


John Maddock
http://ourworld.compuserve.com/homepages/John_Maddock/

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Maddock wrote:
....
> std vector<int, myalloc<double> > v;
>
> this is allowed by the standard, the first thing any container should

Section 23.1, p8 says "All other constructors for these container types
take an Allocator& argument (20.1.5), an allocator whose value type is
the same as the container's value type." This implies, unfortunately
without saying so directly, that Allocator::value_type must be the same
as container<T,Allocator>::value_type.

> do is rebind the passed allocator type to the type it actually needs:
> in this case myalloc<int>, but could equally be
> myalloc<my_internal_struct>.

A standard container is not required to do the rebinding.
vector<T,Allocator> is required to:

 typedef typename Allocator::reference reference;
 typedef T    value_type;

vector<> is also required to meet the standard container requirements,
which say that container::reference must be an lvalue of
container::value_type. In general that's not possible if
Allocator::value_type isn't the same as T.

The various members of vector<> use a mixture of T, value_type, pointer,
and reference, with the result that if Allocator::value_type isn't the
same as T, things can go badly wrong (or not! - for instance, on an
implementation where 'int' and 'long' were the same width, vector<int,
Allocator<long>>  would probably work with few problems).

I've thought about a vector<> implementation that would use a
type-punning iterator that iterates through an array of
Allocator::value_type, but when dereferenced, returns the corresponding
T&. I've been trying to figure out a good use for such a container, but
haven't found one yet. There are rather severe slicing problems if T is
a base class of Allocator::value_type.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

  John_Maddock@compuserve.com (John Maddock) wrote:
>
> >Yep, you did - the crucial point which makes allocator useful is that
> >rebind should define different instantiation of the same template:
> >
> >      struct rebind       {
> >           typedef myalloc<U> other;
> >      };
> >
>
> Yes, but the separate instance is still copied (perhaps "cloned" would
> be a better word) from the original allocator, and still uses the same
> underlying heap - therefore if the container is correctly implemented
> all memory allocation (regardless of type) will be done using the same
> underlying heap.

You missed the point : if rebind<U> would define "other" as allocator<U>
(as in the original post), not myalloc<U>, that copying won't help (even
if it works), as allocator<U> does not know anything about private heap.

>
> >Painfully true. Without member template classes support, it is
> >not possible to implement the above.
>
> And there is no sign of that support appearing anytime soon :-(
>
> Fortunately, Borland C++ Builder 4 does support "real" allocators, you
> may get some mileage with egcs also, although I think that by default
> it doesn't use the conformant allocators - maybe you can comment on
> STLPort?

STLport 3.12 uses allocator<T> as the default parameter for containers
(I suppose this is the point of your questions). Conforming of
allocator<T>
depends of whether the above class template feature is supported by the
compiler. In 3.2, however, I am rolling back to the SGI scheme - that
is, allocator<T> will be used as the default parameter for containers
only if it is fully standard-conforming. The point of that is : if
rebind<> does not work, STLport has to use "chunking" - using
allocator<T> to allocate, say, _List_node<T>. That leads to memory
overuse since allocator<T> allocates space in chunks of (sizeof(T)).
For big classes, waste may be significant.
STLport does not change allocator<T>::allocate(n) to allocate n bytes
instead of n*sizeof(T) to work around this, like Rogue Wave does,
as it would make allocator<T> unusable in standalone context.

As (without rebind) it makes little difference to programmer which
allocator is being used as the default one, 3.12 will use SGI "alloc"
unless conformant allocator<T> can be used with the compiler.

Another important point is - do containers handle copying of
(possibly custom) allocators when it is required by the standard.
Again, in SGI STL and STLport it is being done only if fully
conformant allocators are used (__STL_USE_STD_ALLOCATORS defined).
Maybe it should be revised to allow non-instanceless allocators for
not-fully-conformant compilers. Thanks for making me think of it.

-Boris.


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---


      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>Yep, you did - the crucial point which makes allocator useful is that
>rebind should define different instantiation of the same template:
>
>      struct rebind       {
>           typedef myalloc<U> other;
>      };
>

Yes, but the separate instance is still copied (perhaps "cloned" would
be a better word) from the original allocator, and still uses the same
underlying heap - therefore if the container is correctly implemented
all memory allocation (regardless of type) will be done using the same
underlying heap.

>Painfully true. Without member template classes support, it is
>not possible to implement the above.

And there is no sign of that support appearing anytime soon :-(

Fortunately, Borland C++ Builder 4 does support "real" allocators, you
may get some mileage with egcs also, although I think that by default
it doesn't use the conformant allocators - maybe you can comment on
STLPort?

John Maddock
http://ourworld.compuserve.com/homepages/John_Maddock/

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Maddock wrote:
>
> >        Is there a mechanism within the C++ standard that will allow me to put
> >the whole thing in my custom allocator?
>
> Yes there is, but it ain't trivial, one possiblity:
>
...
>
> and the actual allocator:
>
> template <class T>
> class myalloc
> {
...
>       template <class U>
>       struct rebind
>       {
>            typedef allocator<U> other;
>       };
...
> };
>
> Hopefully I haven't missed anything, I'm sure that someone will tell
> me if I have!  The important point, is that if a container is
> constructed with a particular allocator instance A, then all
> allocation must be done with a copy of A.

Yep, you did - the crucial point which makes allocator useful is that
rebind should define different instantiation of the same template:

      struct rebind       {
           typedef myalloc<U> other;
      };

This makes the "myalloc" template useful in maps, etc - all structures
would be then allocated with correct allocator.

>
> Finally, depending upon whose compiler you are using, your mileage may
> vary with the code as posted above (for example if you're using Visual
> C++ then you're basically stuffed, sorry!)
>

Painfully true. Without member template classes support, it is
not possible to implement the above.

Hope that helps,
-----------------------------------------------------
Boris Fomitchev   |  Boris.Fomitchev@Eng.Sun.Com
-----------------------------------------------------


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

        I love the concept of the allocators for the STL but they seem to fall
short of their intended use in terms of flexibility. I need to be able to
place a container (the whole container, nodes, content, instance variables,
etc...) in a fixed sized memory space. The first idea I get is to implement my
own allocator and everything will be great.

        Unfortunately, the allocator will only be used for the actual
instances of the paramaterized type of the container. For a map< int, string
>, for instance, only the pair< int, string > items will be in my container.
The links and pointers that make up the map will be allocated on the normal
heap or wherever my particular implementation decides to put it.

        I need to be able to guarantee that I'm not going to use any data
beyond what's been allocated for this specific heap. I can stand a little
space on the stack for base container data but as my map grows, memory usage
because of internal links will grow as well regardless of my allocator
specification.

        Is there a mechanism within the C++ standard that will allow me to put
the whole thing in my custom allocator?

        thanx & later,

                Ben Scherrey

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>        Is there a mechanism within the C++ standard that will allow me to put
>the whole thing in my custom allocator?

Yes there is, but it ain't trivial, one possiblity:

Impliment class heap that allocates blocks of bytes inside your fixed
memory area, implement heap in such a manner that the heap instance
can be determined from a pointer to a block allocated by the heap: for
example use the 4 bytes (or whatever) prior to each allocated block to
store a pointer to the heap instance. Finally make the heap reference
counted, doing an addref on allocate and a release on deallocate (this
is important - the heap may be referenced by no allocators but still
have outstanding blocks waiting to be freed, blocks can be freed by
any allocator, but will be allocated only by a copy of the allocator
passed to the containers constructor).

Your heap class now looks like:

class heap
{
 heap(); // default constructor, sets ref count to 1
 void addref();
 void release();
 void* allocate(size_t); // must do addref
 void deallocate(void*, size_t); // must do release
 static heap* getheap(void* block); // determines the
  //instance of heap that did the allocation
};


and the actual allocator:

template <class T>
class myalloc
{
private:
 heap* ph;
     public:
      typedef size_t    size_type;
      typedef ptrdiff_t difference_type;
      typedef T*        pointer;
      typedef const T*  const_pointer;
      typedef T&        reference;
      typedef const T&  const_reference;
      typedef T         value_type;
      template <class U>
      struct rebind
      {
           typedef allocator<U> other;
      };
      myalloc() throw() { ph = new heap; }
      myalloc(const myalloc&a) throw(){ ph = a.ph; ph->addref(); }
      template <class U>
 myalloc(const myalloc<U>&) throw(){ ph = a.ph; ph->addref(); }
     ~myalloc() throw(){ ph->release(); }
      pointer address(reference x) const { return &x; }
      const_pointer address(const_reference x) const { return &x; }
      pointer allocate(size_type n, void* hint = 0)
 { return (pointer)ph->allocate(sizeof(T) * n); }
      void deallocate(pointer p, size_type n)
 ( ph->getheap(p)->deallocate(p, sizeof(T)*n); }
      size_type max_size() const throw() { return -1; }
      void construct(pointer p, const T& val) { new (p) T(val); }
      void destroy(pointer p) { p->~T(); }
};


Hopefully I haven't missed anything, I'm sure that someone will tell
me if I have!  The important point, is that if a container is
constructed with a particular allocator instance A, then all
allocation must be done with a copy of A.

Finally, depending upon whose compiler you are using, your mileage may
vary with the code as posted above (for example if you're using Visual
C++ then you're basically stuffed, sorry!)

John Maddock
http://ourworld.compuserve.com/homepages/John_Maddock/

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]