Topic: Allocators to be removed from STL?


Author: fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)
Date: 1996/10/22
Raw View
Nathan Myers <ncm@cantrip.org> writes:

>This issue arose in committee, and is interesting in general.
>The question is best stated as, what-the-hell good are template template
>parameters?
>
>In this case, suppose you had an allocator that required two parameters:
>
>  template <class T, int Pagesize>
>    class SharedPageAllocator;
>
>You can use this allocator with a Standard container, but not with the one
>Daveed (and John Skaller before him) suggests.

You can?

Supposing you have

 typedef SharedPageAllocator<int,4096> MyIntAllocator;

Can you then do

 vector<int, MyIntAllocator> v;

?
If so, what are the semantics of MyIntAllocator::rebind?

The draft standard says (20.1.4, lib.allocator.requirements) that for
any allocator X, the semantics of the type X::rebind<U>::other are
defined as "for X an instantiation of XT<T>, the type XT<U>".  But in
this case, there is no type T and template XT such that the type
MyIntAllocator is an instantiation of XT<T>.  So what does this part of
the standard mean in this case?  Does this mean that MyIntAllocator is
not a valid allocator?  Or does it mean that it is a valid allocator,
but that the standard does not place any requirements on the semantics
of MyIntAllocator::rebind?

If the former, then your claim that

>In fact, for any possible
>use of a template template parameter, you can offer the user more flexibility
>if you replace it with the form found in the Allocator interface.

is false.  But if the latter, then rebind seems unusable,
and I think that would make collection classes unimplementable.

Actually, on further thought, I think collection classes are unimplementable
anyway.  The draft says (23.1, lib.container.requirements) that container
classes must allocate all their memory using a copy of the allocator argument
passed to the container's constructor.  But from the description of the
requirements on allocators, the allocator interface doesn't seem to provide
any way to allocate objects of a different type.

Did I miss something?

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]





Author: Nathan Myers <ncm@cantrip.org>
Date: 1996/10/23
Raw View
Fergus Henderson wrote:

> Nathan Myers <ncm@cantrip.org> writes:
>
> >This issue arose in committee, and is interesting in general:
> >The question is best stated as, what-the-hell good are template template
> >parameters?
> >
> >In this case, suppose you had an allocator that required two parameters:
> >
> >  template <class T, int Pagesize>
> >    class SharedPageAllocator;
> >
> >You can use this allocator with a Standard container, but not with the one
> >Daveed (and John Skaller before him) suggests.

> You can?  Supposing you have
>         typedef SharedPageAllocator<int,4096> MyIntAllocator;
> Can you then do
>         vector<int, MyIntAllocator> v;
> ?

Of course.

> If so, what are the semantics of MyIntAllocator::rebind?

Here's how you would define that member:

template <class T, size_t PageSize>
  struct SharedPageAllocator  {

     template <class U>
       struct rebind { typedef SharedPageAllocator<U,PageSize> other; };
     ...
  };

so that the two following two types are the same:

  SharedPageAllocator<int,4096>::rebind<char>::other
  SharedPageAllocator<char,4096>

Simple, isn't it?

> The draft standard says ...

The language describing rebind<> is the subject of an open issue in
the issues list for Clause 20.  It could certainly be clarified, and
any help Fergus were willing to offer in that direction would of
course be much appreciated.  Perhaps he could review the proposed
changes for this issue?

> [... hence, ]
>
> >In fact, for any possible
> >use of a template template parameter, you can offer the user more flexibility
> >if you replace it with the form found in the Allocator interface.
>
> is false.

Sorry, that doesn't follow.  Understand the technique, and you will
understand how it provides more flexibility.

> [...] rebind seems unusable,
> and I think that would make collection classes unimplementable.
>
> Actually, on further thought, I think collection classes are unimplementable
> anyway.  [...]
> Did I miss something?

In a word, yes.

Take a look at the definition of the default allocator, and the example
use of it to implement a container, later in the chapter.  The Allocator
requirements table is an attempt at capturing that usage.  If the table
is incomplete or unclear, then it must be fixed.  There is work in
progress on that (and many other fronts), and we would all like the
work to have gone faster, but the Standard is a volunteer effort.

If Fergus feels he has identified problems in the description of
any part of the Draft, I encourage him to add them to the appropriate
issues lists.

Nathan Myers
ncm@cantrip.org
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]





Author: fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)
Date: 1996/10/24
Raw View
Nathan Myers <ncm@cantrip.org> writes:

>Fergus Henderson wrote:
>
>> The draft standard says ...
>
>The language describing rebind<> is the subject of an open issue in
>the issues list for Clause 20.

Ah, that's what I was missing.

>Sorry, that doesn't follow.  Understand the technique, and you will
>understand how it provides more flexibility.

Actually, I did understand the technique, I just didn't understand
how it could be justified based on the words in the draft standard.

>It could certainly be clarified, and
>any help Fergus were willing to offer in that direction would of
>course be much appreciated.  Perhaps he could review the proposed
>changes for this issue?

Having now looked at the proposed changes, they look fine, and they
seem to address all the problems with the existing wording that I
mentioned in my previous post.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]





Author: Nathan Myers <ncm@cantrip.org>
Date: 1996/10/17
Raw View
(I am responsible for the (re)design of the Allocator interface as it
appears
in the Draft.)

David Vandevoorde wrote:
> >>>>> "AK" == Ajay Kamdar <ajay@lehman.com> writes:
> AK> If allocators are removed from STL, it will be a significant
> AK> obstacle to persistifying standard strings and STL containers in
> AK> object databases.

> [...] most of us will not have to write
> container templates that take standard allocators as generic parameters...

This is true: if your users will never need to place your container in (e.g.)
a shared memory region, or in persistent store, then you don't have to use the
Allocator interface when implementing the container.

> (if you did, you might have to understand why a simple binary node needs
> declarations such as:
>
>         template<typename T, typename StdAllocator>
>         struct binary_node {
>            T data_
>            StdAllocator::rebind<void>::other::pointer left_;
>            StdAllocator::rebind<void>::other::pointer right_;
>         };
>
> brrr... :-P.)

I share Daveed's distaste for the idiom above, so I don't use it.

The "rebind<>" mechanism was necessary because (for no good reason
I know of) C++ has no "template typedef" feature.  The only problem,
once you are familiar with it, is that it's long.  That can be contained
with a typedef:

         template<typename T, typename StdAllocator>
         struct binary_node {
            typedef StdAllocator::rebind<binary_node>::other::pointer pointer;
            T data_
            pointer left_;
            pointer right_;
         };

This is just like the non-allocator version, except for one extra line that
looks the same (and will soon look familiar) for almost any container.

> BTW, although I didn't find a statement to the effect that allocators
> must be templates, a brief browsing of a DWP seems to indicate that
> this is in fact a requirement. If so, wouldn't it mean that e.g.
>
>         template<typename T,
>                  template<typename U> class Allocator = allocator>
>         struct list;
>
> would be a better standard declaration than the current ([lib.sequences])
>
>         template<class T, class Allocator = allocator<T> >
>         class list;

This issue arose in committee, and is interesting in general.
The question is best stated as, what-the-hell good are template template
parameters?

In this case, suppose you had an allocator that required two parameters:

  template <class T, int Pagesize>
    class SharedPageAllocator;

You can use this allocator with a Standard container, but not with the one
Daveed (and John Skaller before him) suggests.  In fact, for any possible
use of a template template parameter, you can offer the user more flexibility
if you replace it with the form found in the Allocator interface.

        *   *   *   *   *

Incidentally... If we had template typedefs, then the typedef in binary_node<>
above would look like

   typedef StdAllocator::rebind<binary_node>::pointer pointer;

While this is still longish, its intended meaning is dead clear.
Perhaps in the next round of standardization, in five years,
we will get template typedefs.

Nathan Myers
ncm@cantrip.org  http://www.cantrip.org/


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]





Author: vandevod@cs.rpi.edu (David Vandevoorde)
Date: 1996/10/18
Raw View
>>>>> "NM" == Nathan Myers <ncm@cantrip.org> writes:
[...]
NM>          template<typename T, typename StdAllocator>
NM>          struct binary_node {
NM>             typedef StdAllocator::rebind<binary_node>::other::pointer
NM>     pointer;
NM>             T data_
NM>             pointer left_;
NM>             pointer right_;
NM>          };

Can you do that? Couldn't there be a requirement that binary_node be a
complete type? (I don't think it is a necessity from a technical point
of view, but I seem to recall someone suggesting that it is a DWP
requirement).

[...]
>> BTW, although I didn't find a statement to the effect that allocators
>> must be templates, a brief browsing of a DWP seems to indicate that
>> this is in fact a requirement. If so, wouldn't it mean that e.g.
>>
>> template<typename T,
>> template<typename U> class Allocator = allocator>
>> struct list;
>>
>> would be a better standard declaration than the current ([lib.sequences])
>>
>> template<class T, class Allocator = allocator<T> >
>> class list;

NM> This issue arose in committee, and is interesting in general.
NM> The question is best stated as, what-the-hell good are template template
NM> parameters?
[...]

Thanks for your excellent and illuminating explanation.

I have not heard of any serious discussion to drop template template
arguments, but since very few people have implemented them, and since
the standard library does not rely on them, wouldn't it have a
``stabilizing effect'' to do so?

 Daveed


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]





Author: ajay@lehman.com (Ajay Kamdar)
Date: 1996/10/14
Raw View
The news (rumor?) is that as of 10/11/96, the C++ standardization
committee is seriously considering throwing allocators out of
the STL standard, and that this push is backed by people with
significant clout on the committee. Is this accurate?

If allocators are removed from STL, it will be a significant obstacle
to persistifying standard strings and STL containers in object databases.
This is of great concern because the alternatives to having allocators
which help persistify objects seem to be:
  (a) Use proprietary persistent string classes and collections for
      use with an object database, use STL collections elsewhere,
      and pay for the cost of conversion each time. Or stay with
      the proprietary string and collection classes completely.

  (b) Use proprietary vendor extensions to STL which support allocators.

None of these alternatives are attractive because they continue to lock us
into proprietary approaches, and significantly negate the benefits of
having STL in the first place. Special allocators are needed for real life
applications, and are not of limited value as some would like to believe.

I do hope that the news of the demise of allocators is greatly
exaggerated.
--
Ajay Kamdar        |    Email: ajay@lehman.com    |    Standard Disclaimer
Lehman Brothers    |    Phone: (201) 524-5048     |
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]





Author: clamage@taumet.eng.sun.com (Steve Clamage)
Date: 1996/10/14
Raw View
In article 1mk@jabba.lehman.com, ajay@lehman.com (Ajay Kamdar) writes:
>The news (rumor?) is that as of 10/11/96, the C++ standardization
>committee is seriously considering throwing allocators out of
>the STL standard, and that this push is backed by people with
>significant clout on the committee. Is this accurate?

No. Allocators are under discussion, particularly about whether the
definition in the latest draft is adequate or needs revising. Someone
probably suggested that allocators are more trouble than they are
worth, but I do not believe allocators will be discarded.

I often wonder how rumors like this originate. If you ever hear a
rumor about some alleged action by the Committee, or by "people with
significant clout," or by "compiler vendors," that seems radical or
strange, it is probably not true. This forum is certainly a good
place to post questions such as the above.
---
Steve Clamage, stephen.clamage@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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]





Author: vandevod@cs.rpi.edu (David Vandevoorde)
Date: 1996/10/15
Raw View
>>>>> "AK" == Ajay Kamdar <ajay@lehman.com> writes:
[...]
AK> If allocators are removed from STL, it will be a significant
AK> obstacle to persistifying standard strings and STL containers in
AK> object databases.
[...]
AK> None of these alternatives are attractive because they continue to
AK> lock us into proprietary approaches, and significantly negate the
AK> benefits of having STL in the first place. Special allocators are
AK> needed for real life applications, and are not of limited value as
AK> some would like to believe.

I have seen both 1) ``allocator opponents'' say that persistence for
standard STL containers is impossible/futile (they advocate making an
STL-compatioble persistence-specific container instead), and
2) ``allocator proponents'' say that the current nature of STL and
allocators make persistence hard to achieve but perhaps not
impossible.

Although I do not believe rumors that say there is a serious intent
to remove allocators from the proposed standard library, I certainly
wouldn't mind it being the case. OTOH, from a user's perspective it
really doesn't matter too much: most of us will not have to write
container templates that take standard allocators as generic parameters
(if you did, you might have to understand why a simple binary node needs
declarations such as:

 template<typename T, typename StdAllocator>
 struct binary_node {
    T data_
    StdAllocator::rebind<void>::other::pointer left_;
    StdAllocator::rebind<void>::other::pointer right_;
 };

brrr... :-P.)

BTW, although I didn't find a statement to the effect that allocators
must be templates, a brief browsing of a DWP seems to indicate that
this is in fact a requirement. If so, wouldn't it mean that e.g.

 template<typename T,
                 template<typename U> class Allocator = allocator>
 struct list;

would be a better standard declaration than the current ([lib.sequences])

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

(I realize the latter is sufficient; I'm only wondering if it could
lead to strange error messages if Allocator were bound to a non-template).

 Daveed
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]





Author: ark@research.att.com (Andrew Koenig)
Date: 1996/10/16
Raw View
In article <53tom2$1mk@jabba.lehman.com> ajay@lehman.com (Ajay Kamdar) writes:

> The news (rumor?) is that as of 10/11/96, the C++ standardization
> committee is seriously considering throwing allocators out of
> the STL standard, and that this push is backed by people with
> significant clout on the committee. Is this accurate?

No, the rumor is not accurate.

It is more accurate to say that not everyone on the committee is
satisfied with the current specification for allocators, but different
people are dissatisfied for different reasons and there is no clear
agreement at this point as to what, if anything, to do.

Unless a consensus develops for a major change, which I think is
unlikely, I expect that allocators will appear in the next official draft
in their current form or close to it.
--
    --Andrew Koenig
      ark@research.att.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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]





Author: Max TenEyck Woodbury <mtew@cds.duke.edu>
Date: 1996/10/16
Raw View
Ajay Kamdar wrote:
>
> The news (rumor?) is that as of 10/11/96, the C++ standardization
> committee is seriously considering throwing allocators out of
> the STL standard, and that this push is backed by people with
> significant clout on the committee. Is this accurate?
>
> If allocators are removed from STL, it will be a significant obstacle
> to persistifying standard strings and STL containers in object databases.
> This is of great concern because the alternatives to having allocators
> which help persistify objects seem to be:
>   (a) Use proprietary persistent string classes and collections for
>       use with an object database, use STL collections elsewhere,
>       and pay for the cost of conversion each time. Or stay with
>       the proprietary string and collection classes completely.
>
>   (b) Use proprietary vendor extensions to STL which support allocators.
>
> None of these alternatives are attractive because they continue to lock us
> into proprietary approaches, and significantly negate the benefits of
> having STL in the first place. Special allocators are needed for real life
> applications, and are not of limited value as some would like to believe.
>
> I do hope that the news of the demise of allocators is greatly
> exaggerated.

While I have argued strongly against run time differentiation of
'allocators', I believe 'allocators' per se DO represent a useful
abstraction in the same way 'traits' is a useful abstraction for
characterizing string attributes.  The original design of
'allocators' was very sound and necessary to solve a number of
significant problems with manipulation of pointers and memory
management.  However, the implementations that had to deal with
unimplemented language features were, to put it bluntly, hacks with
more than a few problems.  A return to the original design is what
is needed, not more hacking.

mtew@cds.duke.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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]