>Now I'm really confused.  Table 32's requirement that
>  X a(b);
>be valid suggests that all allocator types must be interconvertible.
>Can this be what is intended?  As James notes,

Yes

>My understanding was that conforming implementations are permitted to
>assume that all instances of allocator<T> are equivalent and all instances
>of allocator<U> are equivalent, but now it looks like Table 32 says that
>all instances of allocator<T> must be convertible into some instance of
>allocator<U> for all T and U.  Is this really true?  If so, why?

It seems as though the standard is trying to have it both ways:

On the one hand it wants to support instance based allocators ( and
states that implimentations are "encouraged" to support them in
20.1.5), on the other hand this is not required due to the complexitiy
requirements for some containers (notably list<>::splice).  The
question is:  is it legal to allocate memory with Allocator<X> and
deallocate with Allocator<Y> copied from the original?  Provided this
is not allowed then two allocator models appear to possible:

Use alloctors with only static code and data, and optimise on the
parameter type T.

Use instance based allocators (only with a container which is known to
support it), and possibly optimise using "hint", but *not" according
to type T, alignment etc must be independent of T.

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


[ 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              ]

In article <MPG.118fd0a9e33162a59896a9@news.teleport.com>,
smeyers@aristeia.com (Scott Meyers) wrote:

> On 26 Apr 99 03:15:38 GMT, James Kuyper wrote:
> > Problem: I can't imagine what those features would be. 'b' and 'a' can't
> > share the same Stroustrup-style pool, because 'T' and 'U' might be
> > different sizes or have different alignment requirements.
>
> My understanding was that conforming implementations are permitted to
> assume that all instances of allocator<T> are equivalent and all instances
> of allocator<U> are equivalent, but now it looks like Table 32 says that
> all instances of allocator<T> must be convertible into some instance of
> allocator<U> for all T and U.  Is this really true?  If so, why?

The classic reason can be demonstrated with

template <class T, class Allocator = allocator<T> > class list;

Typical implementations of list<T> will need to allocate a "list_node<T>"
(some internal structure), not a T.  But list<T> is only given an
allocator<T>.  So list needs some way to get an allocator<list_node<T> >.
Using rebind it can get one from allocator<T>.

-Howard
---
[ 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              ]

>2. Forced way:
>Allocator<X> is derived from a base class, and contains a
>reference-counted pointer to a base class instance. When 'a' was created
>from 'b', that pointer was set to point at 'b'. When 'Y(a)' was
>constructed, that pointer was checked to see whether the dynamic type of
>the objected pointed to by that pointer was 'Y'. Since it was, the new
>Y() got created as an equivalent copy of 'b'.
>
>Problem: This feels like a cheat to me.
>
> X::pointer px = a.allocate(1);
> Y::pointer py = b.allocate(1, px);
>
>The fact that the hint passed to Y::allocate() can be an X::pointer
>suggests that the "natural way" is intended, because only by sharing
>some implementation features with 'a' could 'b' make any good use of the
>hint.

You're "forced way" was certainly how I expected allocators to work,
until you woke me up and pointed out that the standard doesn't
actually require containers to support this.  The only effective (?)
implimentation I can think of that would use the hint as you suggest,
would be one where the allocator contains a pointer (maybe reference
counted) to an underlying heap which allocates blocks of bytes (as in
malloc), and where the "hint" is taken as a void pointer which can be
used to speed up searching for the next free block:

Imagine that the implimentation of the heap stores blocks in a linked
list, the void* hint would allow the implimentation to obtain a
pointer to the header for that block (typically by subtracting a fixed
offset) and then search for the next free block starting from that
location - this need not in fact be the first free block - but the one
at the next highest address to the hint - imagine a large allocation
folowed by a small one - small free blocks of sufficient size for the
second allocation, but too small for the first may be skipped over.

The question is - is this any good?

I suspect that the only option is try a variety of schemes and examine
their effect on both headline speed and heap fragmentation.  The  use
of the hint in this case would allow "proximity allocation" possibly
improving processor cache hits, but at the expense of a possibly more
extensive memory usage (and fragmentation?).  Note that these are my
(highly prejudiced!) preconceptions - and not actual experience.

Such a scheme also precludes what I tend to call "caching allocators"
- that is allocators that deal in fixed sized blocks - as are
typically required by linked lists for example.  However in this case
the standard containers tend to preclude this anyway - what size of
block does some generic implimentation of std::list<> allocate in any
case?

I'm not sure if these thought help or hinder, but hopefully library
useage will gradually build up the experience required to determine
how allocators should behave.

John Maddock
http://ourworld.compuserve.com/homepages/John_Maddock/
---
[ 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              ]

On 27 Apr 99 02:45:37 GMT, AllanW {formerly AllanW@my-dejanews.com} wrote:
> In article <MPG.1187f598ff8ae5b39896a8@news.teleport.com>,
>   smeyers@aristeia.com (Scott Meyers) wrote:
> >
> > On 21 Apr 99 15:24:48 GMT, James Kuyper wrote:
> > >
> > > The standard says that two allocator instances compare equal if and only
> > > if they can deallocate each other's allocations. Allocators which manage
> > > per-instance memory pools will not, in general, be able to do this.
> >
> > This, I think, is the crux of the matter, and the result is that I cannot
> > portably do what I want to do.
>
> All you have to do is separate the class which manages the memory from
> the class used to request the allocations. After all, the part that the
> standard deals with isn't called a "private heap," it's called an
> "allocator." Where it allocates from is up to the class.

> // A private heap
> class MyHeap {
>     // Usual private data members for a private heap
>     // Probably contains the pointer to per-instance pool data
>     // We add only one private data member and two public member functions
> public:
>     void deallocate(void*);
> };

How is deallocate implemented?  The problem is that it might receive a
pointer to memory not in its pool.  For example, if I have

  MyAllocator<T> instance1;
  MyAllocator<T> instance2;

each instance manages a separate chunk of memory.  The standard says that
memory allocated by instance1 must be deallocatable by instance2, and it
further says that the deallocation must be an amortized constant-time
operation (20.1.5, para 2).  Off the top of my head, I don't see how to
implement this, because there may be n different instances of
MyAllocator<T> collectively managing n different pools, yet we must be able
to find the appropriate pool in amortized O(1) time when any of the
instances' deallocate function is called.

Scott

--
Scott Meyers, Ph.D.                  smeyers@aristeia.com
Software Development Consultant      http://www.aristeia.com/
Visit http://meyerscd.awl.com/ to demo the Effective C++ CD
---
[ 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've been contributing to this thread by writing about allocators as if
I knew all about them, but the reality is that I have far more
experience in C, than in C++. The only things I know about allocators
are what's written in the standard and in Stroustrup. I have a question
of my own about them, which isn't covered in either source:

How would a class work that fully meets the Table 32 requirements, but
which supports inequivalent instances?

For me, the tripping point is the following post-condition:

 typedef Allocator<T> X;
 typedef Allocator<U> Y;

 Y b;
 X a(b);

 // Table 32 - post-condition on X a(b):
 assert(Y(a)==b);

Stroustrup describes a pool allocator, which allows all instances to be
equivalent by making the pool itself static. This can easily be modified
to make inequivalent instances, by instead using a reference-counted
smart pointer to a pool. Equivalent instances would point to the same
pool, inequivalent ones would point to different pools. However, I don't
see any natural way to implement the conversion constructor so as to
meet that post-condition.

1. Natural way:
The implementation features that determine whether b is equivalent to a
different Y instance are shared by a, and indeed by any other allocator
created by an arbitrarily long line of conversion constructions from b
(which goes beyond what the standard requires). Therefore, Y(a) is
naturally equivalent to b.
Problem: I can't imagine what those features would be. 'b' and 'a' can't
share the same Stroustrup-style pool, because 'T' and 'U' might be
different sizes or have different alignment requirements.

2. Forced way:
Allocator<X> is derived from a base class, and contains a
reference-counted pointer to a base class instance. When 'a' was created
from 'b', that pointer was set to point at 'b'. When 'Y(a)' was
constructed, that pointer was checked to see whether the dynamic type of
the objected pointed to by that pointer was 'Y'. Since it was, the new
Y() got created as an equivalent copy of 'b'.

Problem: This feels like a cheat to me.

 X::pointer px = a.allocate(1);
 Y::pointer py = b.allocate(1, px);

The fact that the hint passed to Y::allocate() can be an X::pointer
suggests that the "natural way" is intended, because only by sharing
some implementation features with 'a' could 'b' make any good use of the
hint.

If someone could post or point me at a description of how a fully
standard-conforming allocator works, that supports inequivalent
instances and an allocate() that actually uses the hint, I'd appreciate
it. Actual source code would be even better.
---
[ 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              ]

On 26 Apr 99 03:15:38 GMT, James Kuyper <kuyper@wizard.net> wrote:

> typedef Allocator<T> X;
> typedef Allocator<U> Y;
>
> Y b;
> X a(b);
>
> // Table 32 - post-condition on X a(b):
> assert(Y(a)==b);

It seems to me that if you want to support non-equivalent allocator
instances, then you have to do away with the templated conversion
copy constructor.

I just looked at the standard, and for the default allocator there
is this templated conversion copy constructor
   template <class T>
   template <class U>
   allocator<T>::allocator(const allocator<U>&);
I have no idea why this function exists.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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              ]

In article <MPG.1187f598ff8ae5b39896a8@news.teleport.com>,
  smeyers@aristeia.com (Scott Meyers) wrote:
>
> On 21 Apr 99 15:24:48 GMT, James Kuyper wrote:
> >
> > The standard says that two allocator instances compare equal if and only
> > if they can deallocate each other's allocations. Allocators which manage
> > per-instance memory pools will not, in general, be able to do this.
>
> This, I think, is the crux of the matter, and the result is that I cannot
> portably do what I want to do.

But this is the easiest restriction to get around!

All you have to do is separate the class which manages the memory from
the class used to request the allocations. After all, the part that the
standard deals with isn't called a "private heap," it's called an
"allocator." Where it allocates from is up to the class.

So we can create a "Private Heap" class which manages memory (with
per-instance memory pools, if you like) and an "Allocator" class which
uses it. Here I give an example with reference counting; the reference
counting allows us to automatically delete the heap when the last
allocator has been destroyed. If your heaps outlive all of the containers
that they will be used with, don't implement the reference-counting
stuff.

// A private heap
class MyHeap {
    // Usual private data members for a private heap
    // Probably contains the pointer to per-instance pool data
    // We add only one private data member and two public member functions
private:
    int refcount;   // Initialize this to 0 in ctor
                    // If desired, dtor can assert() this is 0
                    // and allocate/deallocate can assert it's > 0
public:
    void addref()                     { ++refcount; }
    void removeref()                  { if (!--refcount) delete this; }

    // Other public members: ctor, dtor, etc.
    // Implementation is left as an excersize for the reader.
    MyHeap(size_t bytes);
    ~MyHeap();
    void*  allocate(size_t bytes);
    void deallocate(void*);
};

// An allocator points to a private heap
class MyAlloc {
    MyHeap *heap;
    // Don't allow assignment after construction
    void operator=(MyAlloc&); // Private and not implemented
public:
    // Default ctor constructs a new default heap?
    // This might need to change depending on the purpose of your private heap
    MyAlloc() : heap(new MyHeap)      { heap->addref(); }

    // Construct allocator from a specific private heap
    MyAlloc(MyHeap *h) : heap(h)      { heap->addref(); }

    // Copy an allocator, copy uses same heap
    MyAlloc(MyAlloc&a) : heap(a.heap) { heap->addref(); }

    // Destructor removes reference to heap
    // This doesn't destroy the heap unless we were the only reference left
    ~MyAlloc()                        { heap->removeref(); }

    // All other functions pass through, implemented by heap
    void*  allocate(size_t bytes)     { return heap->allocate(bytes); }
    void deallocate(void*v)           { return heap->deallocate(v); }
};

----
Allan_W@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ 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              ]

>The problem is not in the allocator. You don't need a special copy()
>member; the copy constructor is sufficient.

No. The copy c'tor will create a new instance, while a copy function may or
may not craete a new instance. Think of the slice method. If the algorithm
would call the copy method of the allocator, the default allocator will just
return the pointer itself resulting in no performance penalty. Using an
allocator that uses different pools (e.g. file based) it *have to* copy the
memory!

Greetings, J   rg
--
BTW: It is normally better to answer to the group! For direct mail reply
exchange the ".A@T." by "@"





[ 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              ]

On 26 Apr 99 03:15:38 GMT, James Kuyper wrote:
> How would a class work that fully meets the Table 32 requirements, but
> which supports inequivalent instances?
>
> For me, the tripping point is the following post-condition:
>
>  typedef Allocator<T> X;
>  typedef Allocator<U> Y;
>
>  Y b;
>  X a(b);
>
>  // Table 32 - post-condition on X a(b):
>  assert(Y(a)==b);

Now I'm really confused.  Table 32's requirement that
  X a(b);
be valid suggests that all allocator types must be interconvertible.
Can this be what is intended?  As James notes,

> Problem: I can't imagine what those features would be. 'b' and 'a' can't
> share the same Stroustrup-style pool, because 'T' and 'U' might be
> different sizes or have different alignment requirements.

My understanding was that conforming implementations are permitted to
assume that all instances of allocator<T> are equivalent and all instances
of allocator<U> are equivalent, but now it looks like Table 32 says that
all instances of allocator<T> must be convertible into some instance of
allocator<U> for all T and U.  Is this really true?  If so, why?

Scott

--
Scott Meyers, Ph.D.                  smeyers@aristeia.com
Software Development Consultant      http://www.aristeia.com/
Visit http://meyerscd.awl.com/ to demo the Effective C++ CD


[ 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              ]

James Kuyper wrote:
>
> Valentin Bonnard wrote:

> > if (alloc == c.alloc)
> >     // adjust pointers
> > else
> >     // copy data
> >
> > inefficient ?
>
> Yes - because it requires storage of a seperate instance of the
> allocator in each container.

AFAIK, every implementation already does that.

> The complexity
> requirements prohibit the otherwise adequate solution of allocating new
> nodes with the new container's allocator, and deallocating the old ones
> with the original container's allocator.

Perhaps the complexity requirements were written w/o consideration
for different allocators ?

> The actual contents of vector<int.Allocator>(3) take up only
> 3*sizeof(int) bytes. The management operations required by vector<>
> itself can be handled by a rougly equal number of bytes. The requirement
> that it store an actual per-container allocator instance adds noticeable
> overhead, if Allocator has some non-trivial contents.

But you have that cost if you use a non trivial allocator. Pay for
what you use.

> There are at least two ways to handle that case: change the complexity
> requirements to allow an implementation to copy each element to newly
> allocated storage, or to require each element in the list to have an
> associated pointer/reference to the allocator which was used to allocate
> it. I think this is an example of the kind of choices that committee
> felt it was premature to standardize.

<< The pay for what you use >> rule tells us to prefer the
copying approach - al least that's my preference. But I
understand your point. People should understand that splice
can only be efficient in an homogeneous world.

--

Valentin Bonnard
---
[ 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              ]

paulp.removethis@ccnet.com (Paul) writes:

> As for the other stuff, yeah, things like 'splice' mess
> it up and make it not work for all cases. But hey, I was
> just posing a more or less workable solution for a problem.
> 98% of the time, this basic solution given works (as does
> what you wrote as a simplification of it).

splice and swap were some of the reasons for the lattitude granted to
library implementors when dealing with allocators.  There was not
general agreement about what the semantics of those member functions
should be when dealing with non-equivalent allocators, so the
committee made the semantics implementation defined.



[ 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              ]

On 22 Apr 1999 19:50:38 GMT, Paul <paulp.removethis@ccnet.com> wrote:

>As for the other stuff, yeah, things like 'splice' mess
>it up and make it not work for all cases. But hey, I was
>just posing a more or less workable solution for a problem.
>98% of the time, this basic solution given works (as does
>what you wrote as a simplification of it).

Can they make the rule that
   allocator instances are not necessarily equivalent
   but if A1==A2, then trying to destroy with A2 an object created by A1 is ok
   but if A1!=A2, then the result is undefined
   generally, A1==A2 if the private variables of A1 and A2 are equal

Example.  Consider this:
   list<int, GenHeapAllocImplementation> c1(pgh1); // A1 is c1.alloc
   list<int, GenHeapAllocImplementation> c2(pgh1); // A2 is c2.alloc
We see that A1 and A2 are different.  But the private variables of A1
and A2 are the same, so A1 and A2 are equal.  So it is reasonable to
splice c1 and c2, or swap elements from c1 with elements from c2.

Consider this too:
   list<int, GenHeapAllocImplementation> c3(pgh2); // A3 is c3.alloc
The private variables of A3 are different from those of A2 or A1.
So trying to splice c1 and c3, or c2 and c3, or trying to swap
elements from c1 and c3, or c2 and c3 is undefined.  In practice,
undefined means a program crash.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ 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              ]

Valentin Bonnard wrote:
>
> James Kuyper wrote:
> >
> > Valentin Bonnard wrote:
>
....
[Re: list<T,Allocator>::splice()]
> > The complexity
> > requirements prohibit the otherwise adequate solution of allocating new
> > nodes with the new container's allocator, and deallocating the old ones
> > with the original container's allocator.
>
> Perhaps the complexity requirements were written w/o consideration
> for different allocators ?

Certainly. Inequivalent instances of the same allocator are very much an
experimental feature in this version of the standard. It's a rare
implementation that even permits them.

> > The actual contents of vector<int.Allocator>(3) take up only
> > 3*sizeof(int) bytes. The management operations required by vector<>
> > itself can be handled by a rougly equal number of bytes. The requirement
> > that it store an actual per-container allocator instance adds noticeable
> > overhead, if Allocator has some non-trivial contents.
>
> But you have that cost if you use a non trivial allocator. Pay for
> what you use.

It's an unnecessary cost for allocators whose instances are all
equivalent, such as std::allocator<>. Of course, those are precisely the
ones that aren't likely to be very big, so this isn't a major issue. I
included it only for the sake of completness.

> > There are at least two ways to handle that case: change the complexity
> > requirements to allow an implementation to copy each element to newly
> > allocated storage, or to require each element in the list to have an
> > associated pointer/reference to the allocator which was used to allocate
> > it. I think this is an example of the kind of choices that committee
> > felt it was premature to standardize.
>
> << The pay for what you use >> rule tells us to prefer the
> copying approach - al least that's my preference. But I
> understand your point. People should understand that splice
> can only be efficient in an homogeneous world.

A container that isn't written to handle inequivalent instances won't
use either method, and is therefore likely to break. That's my main
point.

The pay-for-what-you-use principle doesn't resolve the issue of what
kind of payment is appropriate for an allocator that actually has
inequivalent instances.
For a given list<T,Allocator>, if T's copy ctor is expensive enough, the
allocator reference method is better. On the other hand, if
sizeof(Allocator &) is large enough compared to sizeof(T), the copying
method is better.
I'm not saying this is an unresolvable issue, merely one that the
standard is avoiding handling until there's more experience.


[ 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              ]

Why not enhance the allocator functionality to copy memory between instances
? std::allocator::copy() may just return the pointer it received as arg.

Greetings, J   rg
--
BTW: It is normally better to answer to the group! For direct mail reply
exchange the ".A@T." by "@"





[ 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              ]

Siemel Naran wrote:
>
> On 22 Apr 1999 19:50:38 GMT, Paul <paulp.removethis@ccnet.com> wrote:
>
> >As for the other stuff, yeah, things like 'splice' mess
> >it up and make it not work for all cases. But hey, I was
> >just posing a more or less workable solution for a problem.
> >98% of the time, this basic solution given works (as does
> >what you wrote as a simplification of it).
>
> Can they make the rule that
>    allocator instances are not necessarily equivalent
>    but if A1==A2, then trying to destroy with A2 an object created by A1 is ok
>    but if A1!=A2, then the result is undefined

That's not significantly different from the current rules, which allow a
standard container to assume the instances are equal.
---
[ 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              ]

Joerg Schaible wrote:
>
> Why not enhance the allocator functionality to copy memory between instances
> ? std::allocator::copy() may just return the pointer it received as arg.
>
> Greetings, J   rg

The problem is not in the allocator. You don't need a special copy()
member; the copy constructor is sufficient.

The problem is that the standard allows a standard container to assume
that all instances of an allocator are equivalent. That means that a
container needn't be careful to check whether the allocator it uses to
deallocate some memory is equivalent to the allocator used to allocate
it. In particular, the container needn't even bother copying the
allocator in the first place.


[ 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 wrote:
> Another problem is that the use of a static class member
> (GenHeapAlloc::pGHAIToUse) renders the code un-thread-safe.

Paul wrote:
> It should be thread-safe. pGHAIToUse is only read on construction,
> and you set its value right before construction in the same
> thread as you create it. Thus, no threading problems could happen.

Uh, no.  You set its value "right before" construction... or right
before another thread sets it to something different.  How do you
know all of this occurs in a single ("the same") thread?

Global variables, which includes static class member variables,
are shared by all the threads in a given process.  They are also
initialized exactly once within the entire process, so it is
meaningless to talk about which thread "creates" them; remember
there is only one instance of each static member variable in a
program.  Unless you protect access to them (with mutexes, monitors,
etc.), you can never assume that there exist times between the
execution of two consecutive statements in a given thread when
those variables are safe from being affected by another thread.

In other words, static member variables are inherently not
thread-safe, and access to them must be controlled appropriately.

Of course, it's not a problem if you don't use threads and
never intend to.

-- David R. Tribble, dtribble@technologist.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              ]

On 21 Apr 99 15:24:48 GMT, James Kuyper wrote:
>
> The standard says that two allocator instances compare equal if and only
> if they can deallocate each other's allocations. Allocators which manage
> per-instance memory pools will not, in general, be able to do this.

This, I think, is the crux of the matter, and the result is that I cannot
portably do what I want to do.

Thanks to everybody for their help.

Scott

--
Scott Meyers, Ph.D.                  smeyers@aristeia.com
Software Development Consultant      http://www.aristeia.com/
Visit http://meyerscd.awl.com/ to demo the Effective C++ CD


[ 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              ]

>Standard containers are allowed, by section 20.1.5 p4 to assume that all
>allocator instances are equivalent. The implication is that they don't
>have to work exactly as you've described. They're permitted to take
>short cuts such as having Container<T,Allocator> use a single static
>Allocator<T> for all allocations. If all instance of Allocator<T> are
>equivalent, it shouldn't matter.

Yep, I see that you're right, looks like there's more to this than
meets the eye!

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


[ 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              ]

Valentin Bonnard wrote:
>
> James Kuyper writes:
>
> > Note: there's a reason the standard makes support for general allocators
> > optional; containers correctly written to handle an allocator that
> > violates those assumptions tend to be difficult to write efficiently.
>
> Hum... is
>
> inline bool std::allocator<T>::operator== (...)
> {
>     return true;
> }

I wasn't talking about std::allocator<T>. I was talking about general
allocators, ones that meet all of the standard's allocator requirements,
but which violate the assumptions which section 20.1.5 p4 permits
standard containers to make.

> if (alloc == c.alloc)
>     // adjust pointers
> else
>     // copy data
>
> inefficient ?

Yes - because it requires storage of a seperate instance of the
allocator in each container. Worse - the complexity requirements of
list<>::splice<> seem to imply that each node must contain a reference
to the allocator instance that was used to allocate the node, since it
needn't be the one belonging to the list itself. The complexity
requirements prohibit the otherwise adequate solution of allocating new
nodes with the new container's allocator, and deallocating the old ones
with the original container's allocator.

> > The most obvious implementation has overhead that doesn't go away when
> > using ordinary allocators - this can be a serious problem for small
> > containers, such as vector<int>(3).
>
> ???

The actual contents of vector<int.Allocator>(3) take up only
3*sizeof(int) bytes. The management operations required by vector<>
itself can be handled by a rougly equal number of bytes. The requirement
that it store an actual per-container allocator instance adds noticeable
overhead, if Allocator has some non-trivial contents.

> > In particular,
> > list<T,MyAllocator>::splice() has some serious problems meeting it's
> > complexity requirements
>
> Then change the complexity requirements (if the allocators compare
> equal, then blah, otherwise blah).

There are at least two ways to handle that case: change the complexity
requirements to allow an implementation to copy each element to newly
allocated storage, or to require each element in the list to have an
associated pointer/reference to the allocator which was used to allocate
it. I think this is an example of the kind of choices that committee
felt it was premature to standardize.
---
[ 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              ]

   >What advantage does this technique have over the following?
   > list<int, GenHeapAllocImplementation> c1(pgh1);
   > list<int, GenHeapAllocImplementation> c2(pgh1);
   > list<int, GenHeapAllocImplementation> c3(pgh2);

Yeah, you're right about this. I didn't realize
there was a constructor for the classes that
took an allocator instance reference as an
argument. I didn't have any references with me
when I wrote that.

As for the other stuff, yeah, things like 'splice' mess
it up and make it not work for all cases. But hey, I was
just posing a more or less workable solution for a problem.
98% of the time, this basic solution given works (as does
what you wrote as a simplification of it).

Paul



[ 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              ]

Scott Meyers asked:
>> Is there a way to get this same kind of behavior using
>> allocators? The straightforward answer seems to be no,
>> because standard-conforming containers are allowed to assume
>> that all instances of an allocator type are equivalent. Still,
>> it doesn't seem to me that my design is unreasonable. Am I
>> overlooking a way to use allocators to do it?

Paul Pedriana wrote:
> In short, yes, you can use (coerce?) STL-conforming allocators to
> do this. My solution requires, however, that you define your own
> allocator or subclass a default implementation provided by the
> vendor. This kind of solution is implied by your question to
> be OK, since you define your own allocators in your example.
>
> The design of STL containers is such that each container creates
> its own instance of the allocator as a class member object. But
> you want it to use a specific instance of your choice. This is
> the crux of the problem. The solution is to use indirection
> within the allocator class itself.
>
>    struct GenHeapAlloc{
>       GenHeapAlloc() : pGHAI(pGHAIToUse) { }
>       int* allocate(size_t n){ return pGHAI->allocate(n); }
>       ...
>       GenHeapAllocImplementation<T>* pGHAI;
>       static GenHeapAllocImplementation<T>* pGHAIToUse;
>    };
>
> The above class can of course be templated if needed or desired.
> Also note that the GenHeapAllocImplementation class can simply be the
> default allocator provided by the vendor; you don't need to write any
> new class here.
>
>...
> Most issues can be addressed with the solution above or some
> variation of the above. The only annoying thing is that you
> are somewhat stuck in passing info to the allocator before it
> gets used (i.e. at construction). ...

Another problem is that the use of a static class member
(GenHeapAlloc::pGHAIToUse) renders the code un-thread-safe.

-- David R. Tribble, dtribble@technologist.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              ]

Scott Meyers wrote:
>
> Suppose I have two different types of heaps, a generic type of heap
> (GenHeap) and a heap designed to be very fast provided certain constraints
> are satisfied (FastHeap):
>
>   class GenHeap { ... };
>   class Fastheap { ... };
>
> All GenHeap instances behave the same way, but they manipulate different
> chunks of memory.  Similarly for FastHeap objects.  As a result, heap
> objects are not interchangable.
>
> The number of GenHeap and/or FastHeap objects is something I can't
> determine until runtime, so my code contains things like this:
>
>   GenHeap *pgh1 = new GenHeap;
>   ...
>   GenHeap *pgh2 = new GenHeap;
>   ...
>   FastHeap *pfh = new FastHeap;
>
> I often want to have two or more of my home-grown containers reside in the
> same heap.  This allows me to improve locality when operating on several
> containers simultaneously.  My current design lets me do this:
>
>   GenHeap *pgh1 = new GenHeap;         // same as above
>   GenHeap *pgh2 = new GenHeap;
>
>   Cont1<T> *pc1 = new Cont1<T>(pgh1);  // create new container and have
>                                        // it use *pgh1 as its heap
>
>   Cont2<T> *pc2 = new Cont2<T>(pgh1);  // create another new container and
>                                        // have it also use *pgh1 as its heap
>
>   Cont1<T> *pc3 = new Cont1<T>(pgh2);  // create a third container, but
>                                        // have it use *pgh2 as its heap
>
> Is there a way to get this same kind of behavior using allocators?  The
> straightforward answer seems to be no, because standard-conforming
> containers are allowed to assume that all instances of an allocator type
> are equivalent.  Still, it doesn't seem to me that my design is
> unreasonable.  Am I overlooking a way to use allocators to do it?  At one
> point I thought this might be a good place to take advantage of
> allocator<T>::allocate's "hint" paremeter, but the standard says that the
> hint must be a prior return value from calling allocate on the same
> allocator<T> object.

What about the following trick:

Call allocate once, and store your data in that memory. Now,
the pointer to the per-instance data _was_ obtained through
allocate, therefore it may legally be passed as hint.

However, how do you get standard containers to pass this
pointer as hint?

BTW, are you sure that for custom allocators hint must be
a pointer to previously allocated memory? I don't have the
standard, but in CD2 I don't see this requirement in the
allocator requirements, but only in the std::allocator<T>
description.
---
[ 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              ]

Christopher Eltschka wrote:

> BTW, are you sure that for custom allocators hint must be
> a pointer to previously allocated memory? I don't have the
> standard, but in CD2 I don't see this requirement in the
> allocator requirements, but only in the std::allocator<T>
> description.

If you can pass any garbage as the hint parameter, than this
parameters become useless...

--

Valentin Bonnard
---
[ 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              ]

Scott Meyers wrote:
....
> I often want to have two or more of my home-grown containers reside in the
> same heap.  This allows me to improve locality when operating on several
....
> Is there a way to get this same kind of behavior using allocators?  The
> straightforward answer seems to be no, because standard-conforming
> containers are allowed to assume that all instances of an allocator type
> are equivalent.  Still, it doesn't seem to me that my design is
> unreasonable.  Am I overlooking a way to use allocators to do it?  At one

The standard does provide a way to do this; it just makes it optional
for a standard container to be written in such a way that it will work.
This in turn means that strictly conforming code can't use such an
allocator for a standard container, which is very annoying. However, if
you're willing to use the allocator exclusively with your own
"home-grown" containers, or exclusively on STL implementations that
support general allocators (I haven't heard of any), you should be fine.

Note: there's a reason the standard makes support for general allocators
optional; containers correctly written to handle an allocator that
violates those assumptions tend to be difficult to write efficiently.
The most obvious implementation has overhead that doesn't go away when
using ordinary allocators - this can be a serious problem for small
containers, such as vector<int>(3). In particular,
list<T,MyAllocator>::splice() has some serious problems meeting it's
complexity requirements - the best solution I've seen so far requires
per-element copies of a pointer to the allocator that allocated the
element.

I think it's possible to write such a container so it has no overhead
when using the default allocator, but I haven't tested my idea yet. My
questions about it to this newsgroup produced no response.

I recommend taking a good look at the allocator and container
requirements, and building your home-grown containers and allocators as
closely as possible in conformance with them. Not so much because
they're well designed (though a lot of thought has gone into them), but
to improve compatibility.

> point I thought this might be a good place to take advantage of
> allocator<T>::allocate's "hint" paremeter, but the standard says that the
> hint must be a prior return value from calling allocate on the same
> allocator<T> object.

'hint' can be used for placing a new allocation near an existing one,
but only if they were done by the same allocator. It's not relevant for
your purpose.
---
[ 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              ]

On 20 Apr 99 00:16:11 GMT, Scott Meyers <smeyers@aristeia.com> wrote:

>  GenHeap *pgh1 = new GenHeap;         // same as above
>  GenHeap *pgh2 = new GenHeap;

How does 'pgh1' know that it must use memory chunk1?
How does 'pgh2' know that it must use memory chunk2?
It seems that class GenHeap has private member variables.
There might be static variables in class GenHeap too.
Is this right?


>  Cont1<T> *pc1 = new Cont1<T>(pgh1);  // create new container and have
>                                       // it use *pgh1 as its heap
>
>  Cont2<T> *pc2 = new Cont2<T>(pgh1);  // create another new container and
>                                       // have it also use *pgh1 as its heap
>
>  Cont1<T> *pc3 = new Cont1<T>(pgh2);  // create a third container, but
>                                       // have it use *pgh2 as its heap
>
>Is there a way to get this same kind of behavior using allocators?  The
>straightforward answer seems to be no, because standard-conforming
>containers are allowed to assume that all instances of an allocator type
>are equivalent.  Still, it doesn't seem to me that my design is
>unreasonable.  Am I overlooking a way to use allocators to do it?  At one
>point I thought this might be a good place to take advantage of
>allocator<T>::allocate's "hint" paremeter, but the standard says that the
>hint must be a prior return value from calling allocate on the same
>allocator<T> object.

We note that std::list has this constructor
   template <class T, class Alloc>
   explicit list<T,Alloc>::list(const Alloc&);

What is the meaning of the sentence "all instances of an allocator type
were equivalent"?

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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 way to get this same kind of behavior using allocators?  The
>straightforward answer seems to be no, because standard-conforming
>containers are allowed to assume that all instances of an allocator type
>are equivalent.  Still, it doesn't seem to me that my design is
>unreasonable.  Am I overlooking a way to use allocators to do it?  At one
>point I thought this might be a good place to take advantage of
>allocator<T>::allocate's "hint" paremeter, but the standard says that the
>hint must be a prior return value from calling allocate on the same
>allocator<T> object.

I think that you can use standard allocators - containers use a *copy*
of the supplied allocator for all allocation - thus a copy of an
allocator must refer to the same heap as the original, whereas
separate instances can refer to different underlying heaps.  A simple
wrapper around your existing heap managers (using reference counting)
seems to be all thats required, perhaps as a refinement ensuring that
all default instances of your allocators refer to the same default
heap - with only specifically constructed allocators using a
non-default constructor refering to specific heaps, I hope I've made
myself clear (I often don't!)

Finally note that few compiler/Standard library implimentations
currently support standard conforming allocators, C++ Builder 4 does,
but neither Visual C++ 6 nor EGCS 1.11 (mingwin port) do at present,
perhaps others will jump in with other compilers.

In other words while the standard does allow you to do want you want
(as you say its not an unreasonable thing to do), your development
tools may not currently allow you to do so.  Unfortunately the
standard definition for allocators uses all of the most advanced
template compiler features, so this may not change anytime soon :-(

John Maddock
http://ourworld.compuserve.com/homepages/John_Maddock/
---
[ 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              ]

   >Another problem is that the use of a static class member
   >(GenHeapAlloc::pGHAIToUse) renders the code un-thread-safe.

It should be thread-safe. pGHAIToUse is only read on construction,
and you set its value right before construction in the same
thread as you create it. Thus, no threading problems could happen.

Paul
---
[ 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              ]

Paul Pedriana wrote:
>
>    >Is there a way to get this same kind of behavior using
>    >allocators? The straightforward answer seems to be no,
>    >because standard-conforming containers are allowed to assume
>    >that all instances of an allocator type are equivalent. Still,
>    >it doesn't seem to me that my design is unreasonable. Am I
>    >overlooking a way to use allocators to do it?
....
> The design of STL containers is such that each container creates
> its own instance of the allocator as a class member object. But
> you want it to use a specific instance of your choice. This is
> the crux of the problem. The solution is to use indirection
> within the allocator class itself.
>
>    struct GenHeapAlloc{
>       GenHeapAlloc() : pGHAI(pGHAIToUse) { }
>       int* allocate(size_t n){ return pGHAI->allocate(n); }
>       ...
>       GenHeapAllocImplementation<T>* pGHAI;
>       static GenHeapAllocImplementation<T>* pGHAIToUse;
>    };

A key question: How do you implement your allocator's copy constructor,
operator==, and conversion from GenHeapAlloc<T1> to GenHeapAlloc<T2>?

A standard container is allowed to assume that all instances of
Allocator<T> compare equal. Two instances of an allocator are allowed to
compare equal only if they can deallocate each other's allocations. The
implication of this assumption is that a standard container may use the
allocator object in one container<T>, to deallocate an object allocated
in another container<T>. One particular place where this assumption is
very important is list<T>::splice().

Another implication is that container<T,Allocator> doesn't need a
per-container Allocator instance; a single static Allocator instance for
each T will do the job, since they would all compare equal.
Such "optimizations" will cause just as much trouble with your code as
with your wrapper class as with the wrapped class.

> The above class can of course be templated if needed or desired.

It's not strictly necessary, but it's very hard to meet all of the
allocator requirements in table 32 that refer to 'Y' or 'b' or 'u' with
a non-templated allocator. Most of the non-sequence standard containers
need to excersize those requirements.

> Also note that the GenHeapAllocImplementation class can simply be the
> default allocator provided by the vendor; you don't need to write any
> new class here.

There's no need to do anything at all in that case; all
std::allocator<T> instances do compare equal.

> Now let's say you want to use your own specific heaps to store
> integers. They could, of course, contain any sufficent type.
> So you declare the three containers like this:
>
>    GenHeapAllocImplementation* pgh1 = new GenHeapAllocImplementation;
>    GenHeapAllocImplementation* pgh2 = new GenHeapAllocImplementation;
>
>    list<int, GenHeapAlloc>* pc1;
>    GenHeapAlloc::pGHAIStatic = pgh1;  //Tell it to use pgh1
>    pc1 = new list<int, GenHeapAlloc>; //Create list that uses pgh1.
>
>    vector<int, GenHeapAlloc>* pc2;
>    GenHeapAlloc::pGHAIStatic = pgh1;    //Tell it to use pgh1
>    pc2 = new vector<int, GenHeapAlloc>; //Create vec that uses pgh1.
>
>    list<int, GenHeapAlloc>* pc3;
>    GenHeapAlloc::pGHAIStatic = pgh2;  //Tell it to use pgh2
>    pc2 = new list<int, GenHeapAlloc>; //Create list that uses pgh2.


What advantage does this technique have over the following?

 list<int, GenHeapAllocImplementation> c1(pgh1);
 list<int, GenHeapAllocImplementation> c2(pgh1);
 list<int, GenHeapAllocImplementation> c3(pgh2);

Standard containers which make the permitted assumption that all
Allocator<T> instances are equal, will have problems with either method.
For the ones that don't, either one is equally workable, and my way is
obviously a lot simpler.

> Most issues can be addressed with the solution above or some
> variation of the above. The only annoying thing is that you
> are somewhat stuck in passing info to the allocator before it
> gets used (i.e. at construction). Well, the get_allocator
> container function could be used to change the used allocator
> after construction, but the fact that get_allocator returns a
> copy and not a reference forces you to use double-deferencing
> in the allocator class, but that is not a big deal.

If you replace a container's allocator instance with another that
doesn't compare equal to it, you're likely to get into big trouble. It
will end up trying to deallocate memory that was allocated using the
original instance.

> Some issues may come up if one container instance tries to
> deallocate memory allocated in another container instance.
> I am not certain off the top of my head if this is normal
> behaviour, and don't have the time to research it.

It's very normal behavior for list<>'s which have been splice()'d.
---
[ 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              ]

Christopher Eltschka wrote:
....
> BTW, are you sure that for custom allocators hint must be
> a pointer to previously allocated memory? I don't have the
> standard, but in CD2 I don't see this requirement in the
> allocator requirements, but only in the std::allocator<T>
> description.

"Table 31 -- Descriptive variable definitions" says:
T,X any type
X an Allocator for type T
Y the corresponding corresponding Allocator class for type U
....
a,a1,a2 values of type X&
....
u a value of type Y::const_pointer obtained by calling
 Y::allocate, or else 0."
n a value of type X::size_type

"Table 32 -- Allocator requirements" defines the hint-taking function as
"a.allocate(n,u)". Therefore, the hint must be either 0, or have been
allocated by a corresponding allocator, but not necessarily an allocator
with the same 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 wrote:
>
> >Is there a way to get this same kind of behavior using allocators?  The
> >straightforward answer seems to be no, because standard-conforming
> >containers are allowed to assume that all instances of an allocator type
> >are equivalent.  Still, it doesn't seem to me that my design is
> >unreasonable.  Am I overlooking a way to use allocators to do it?  At one
> >point I thought this might be a good place to take advantage of
> >allocator<T>::allocate's "hint" paremeter, but the standard says that the
> >hint must be a prior return value from calling allocate on the same
> >allocator<T> object.
>
> I think that you can use standard allocators - containers use a *copy*
> of the supplied allocator for all allocation - thus a copy of an
> allocator must refer to the same heap as the original, whereas
> separate instances can refer to different underlying heaps.  A simple

Standard containers are allowed, by section 20.1.5 p4 to assume that all
allocator instances are equivalent. The implication is that they don't
have to work exactly as you've described. They're permitted to take
short cuts such as having Container<T,Allocator> use a single static
Allocator<T> for all allocations. If all instance of Allocator<T> are
equivalent, it shouldn't matter.
---
[ 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              ]

Siemel Naran wrote:
....
> What is the meaning of the sentence "all instances of an allocator type
> were equivalent"?

The standard says that two allocator instances compare equal if and only
if they can deallocate each other's allocations. Allocators which manage
per-instance memory pools will not, in general, be able to 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              ]

James Kuyper writes:

> Note: there's a reason the standard makes support for general allocators
> optional; containers correctly written to handle an allocator that
> violates those assumptions tend to be difficult to write efficiently.

Hum... is

inline bool std::allocator<T>::operator== (...)
{
    return true;
}

if (alloc == c.alloc)
    // adjust pointers
else
    // copy data

inefficient ?

> The most obvious implementation has overhead that doesn't go away when
> using ordinary allocators - this can be a serious problem for small
> containers, such as vector<int>(3).

???

> In particular,
> list<T,MyAllocator>::splice() has some serious problems meeting it's
> complexity requirements

Then change the complexity requirements (if the allocators compare
equal, then blah, otherwise blah).

--

Valentin Bonnard


[ 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              ]

Siemel Naran wrote:
>
> On 20 Apr 99 00:16:11 GMT, Scott Meyers <smeyers@aristeia.com> wrote:
>
> >  GenHeap *pgh1 = new GenHeap;         // same as above
> >  GenHeap *pgh2 = new GenHeap;
>
> How does 'pgh1' know that it must use memory chunk1?
> How does 'pgh2' know that it must use memory chunk2?

Simple: each GenHeap uses its memory chunk.

> It seems that class GenHeap has private member variables.

It seems to me too.

> What is the meaning of the sentence "all instances of an allocator type
> were equivalent"?

It means that it can use any instance of an allocator instead
of using a specific instance of that allocator. So in theory
you cannot rely to per-instance pools to work correctly.

The problem is the specification of functions which deal
with more than containners: swap, splice. What do you do
if the containers don't use the same pool ? You probably
have to copy the memory content (which contradicts the fact
that swap doesn't invalidate anything).

BTW, where is swap defined ? Does swap swaps the allocators
(I understand that the intent is that it doesn't) ?

--

Valentin Bonnard


[ 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              ]

Suppose I have two different types of heaps, a generic type of heap
(GenHeap) and a heap designed to be very fast provided certain constraints
are satisfied (FastHeap):

  class GenHeap { ... };
  class Fastheap { ... };

All GenHeap instances behave the same way, but they manipulate different
chunks of memory.  Similarly for FastHeap objects.  As a result, heap
objects are not interchangable.

The number of GenHeap and/or FastHeap objects is something I can't
determine until runtime, so my code contains things like this:

  GenHeap *pgh1 = new GenHeap;
  ...
  GenHeap *pgh2 = new GenHeap;
  ...
  FastHeap *pfh = new FastHeap;

I often want to have two or more of my home-grown containers reside in the
same heap.  This allows me to improve locality when operating on several
containers simultaneously.  My current design lets me do this:

  GenHeap *pgh1 = new GenHeap;         // same as above
  GenHeap *pgh2 = new GenHeap;

  Cont1<T> *pc1 = new Cont1<T>(pgh1);  // create new container and have
                                       // it use *pgh1 as its heap

  Cont2<T> *pc2 = new Cont2<T>(pgh1);  // create another new container and
                                       // have it also use *pgh1 as its heap

  Cont1<T> *pc3 = new Cont1<T>(pgh2);  // create a third container, but
                                       // have it use *pgh2 as its heap

Is there a way to get this same kind of behavior using allocators?  The
straightforward answer seems to be no, because standard-conforming
containers are allowed to assume that all instances of an allocator type
are equivalent.  Still, it doesn't seem to me that my design is
unreasonable.  Am I overlooking a way to use allocators to do it?  At one
point I thought this might be a good place to take advantage of
allocator<T>::allocate's "hint" paremeter, but the standard says that the
hint must be a prior return value from calling allocate on the same
allocator<T> object.

Thanks,

Scott

--
Scott Meyers, Ph.D.                  smeyers@aristeia.com
Software Development Consultant      http://www.aristeia.com/
Visit http://meyerscd.awl.com/ to demo the Effective C++ CD
---
[ 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              ]

smeyers@aristeia.com (Scott Meyers) writes:

>
> Is there a way to get this same kind of behavior using allocators?  The
> straightforward answer seems to be no, because standard-conforming
> containers are allowed to assume that all instances of an allocator type
> are equivalent.

You should expect that restriction to be lifted in a future revision
of the standard.  It was a compromise, and the committee put it in
because we were unable to agree on what the semantics of non-
equivalent allocators ought to be.

The real significance of that restriction is that those semantics are
implementation defined.  I expect that essentially all library
implementors will support non-equivalent allocators, but that there
will be slightly different restrictions.  (For example: should
a.swap(b) be well defined even if a.get_allocator() != b.get_allocator()?)

Once there's some more implementation experience, I expect the
standard to specify these things more precisely.
---
[ 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 way to get this same kind of behavior using
   >allocators? The straightforward answer seems to be no,
   >because standard-conforming containers are allowed to assume
   >that all instances of an allocator type are equivalent. Still,
   >it doesn't seem to me that my design is unreasonable. Am I
   >overlooking a way to use allocators to do it?

In short, yes, you can use (coerce?) STL-conforming allocators to
do this. My solution requires, however, that you define your own
allocator or subclass a default implementation provided by the
vendor. This kind of solution is implied by your question to
be OK, since you define your own allocators in your example.

The design of STL containers is such that each container creates
its own instance of the allocator as a class member object. But
you want it to use a specific instance of your choice. This is
the crux of the problem. The solution is to use indirection
within the allocator class itself.

   struct GenHeapAlloc{
      GenHeapAlloc() : pGHAI(pGHAIToUse) { }
      int* allocate(size_t n){ return pGHAI->allocate(n); }
      ...
      GenHeapAllocImplementation<T>* pGHAI;
      static GenHeapAllocImplementation<T>* pGHAIToUse;
   };

The above class can of course be templated if needed or desired.
Also note that the GenHeapAllocImplementation class can simply be the
default allocator provided by the vendor; you don't need to write any
new class here.

Now let's say you want to use your own specific heaps to store
integers. They could, of course, contain any sufficent type.
So you declare the three containers like this:

   GenHeapAllocImplementation* pgh1 = new GenHeapAllocImplementation;
   GenHeapAllocImplementation* pgh2 = new GenHeapAllocImplementation;

   list<int, GenHeapAlloc>* pc1;
   GenHeapAlloc::pGHAIStatic = pgh1;  //Tell it to use pgh1
   pc1 = new list<int, GenHeapAlloc>; //Create list that uses pgh1.

   vector<int, GenHeapAlloc>* pc2;
   GenHeapAlloc::pGHAIStatic = pgh1;    //Tell it to use pgh1
   pc2 = new vector<int, GenHeapAlloc>; //Create vec that uses pgh1.

   list<int, GenHeapAlloc>* pc3;
   GenHeapAlloc::pGHAIStatic = pgh2;  //Tell it to use pgh2
   pc2 = new list<int, GenHeapAlloc>; //Create list that uses pgh2.

Most issues can be addressed with the solution above or some
variation of the above. The only annoying thing is that you
are somewhat stuck in passing info to the allocator before it
gets used (i.e. at construction). Well, the get_allocator
container function could be used to change the used allocator
after construction, but the fact that get_allocator returns a
copy and not a reference forces you to use double-deferencing
in the allocator class, but that is not a big deal.

Some issues may come up if one container instance tries to
deallocate memory allocated in another container instance.
I am not certain off the top of my head if this is normal
behaviour, and don't have the time to research it.

Paul Pedriana
---
[ 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              ]