James Kuyper wrote:
>
> While having a non-static Allocator member is perhaps the simplest way
> to achieve all of these requirements, the standard doesn't mandate it,
> and I think the technique you describe below could meet the above
> requirement equally well.
>
> Also, keep in mind section 20.1.5 p4, which says that
>
> "Implementations of containters described in this International Standard
> are permitted to assume that their Allocator template parameter meets
> the following two additional requirements beyond those in Table 32.
>
> -- All instances of a given allocator type are required to be
> interchangeable and always compare equal to each other."
>
> Thus, by the as-if rule, a static Allocator member of each container
> class would be perfectly legal.
>

Still, that would be a restriction, since, according to same,
implementors are encouraged to provide implementation which do not rely
on those additional requirements. And, if given allocator satisfy those
requirements,
most likely it has no non-static data members, so EBO will handle this
transparently
while not restricting from using other types of allocators (persistent
storage, for example).
I agree that most implementations do take care about size optimization
now,
and SGI STL uses less general technique, as it does not cover custom
allocators automatically.
STLport 3.2 will migrate from SGI scheme to generic EBO implementation.

Best regards,

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

In article <7inv1a$237b@enews3.newsguy.com>, "Darin Adler"
<darin@bentspoon.com> wrote:

> For example, the implementation I use most often, part of Metrowerks
> Standard Library, uses a template called _EmptyMemberOpt to do this, and it
> credits Nathan C. Myers with the implementation.

Just to follow up, see http://www.cantrip.org/emptyopt.html

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

Hi,

So the commitee decided to make the allocator a non-static member of
each container. This takes up some extra space, increasing the sizeof
the container. This is usually unnecessary, because the default
allocators as well as most custom allocators do not have any data
members.

This could be avoided by inheriting privately from the allocator class
and making the appropriate using declaration. By doing this, you allow
the compiler to perform the empty-base optimization, rendering the size
of the vector optimal.

However, I haven't seen this done in any STL implementation I saw,
although it seems natural to me. I implemented a toy vector with all
the operations and it seemed to work fine. (Yes, I admit I started by
pasting from the STL implementation.) I didn't have any compile-time or
run-time problems (I couldn't pretend I did a thorough test. But I see
no reason for which switching from containment to private inheritance
would incur any problems).

My question is: why didn't anyone do that? Would this be a conforming
implementation?

Andrei


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


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

> This could be avoided by inheriting privately from the allocator class
> and making the appropriate using declaration. By doing this, you allow
> the compiler to perform the empty-base optimization, rendering the size
> of the vector optimal.

Many STL implementations do this kind of optimization. I don't think you can
have the collection itself inherit privately from the allocator class --
most implementations have one of the private members of the collection class
inherit from the allocator class.

For example, the implementation I use most often, part of Metrowerks
Standard Library, uses a template called _EmptyMemberOpt to do this, and it
credits Nathan C. Myers with the implementation.

Apparently the SGI implementation takes another approach to this problem and
provides their own way to define what they call SGI-style allocators. They
use an _Alloc_traits template to detect allocators that don't require any
storage.

    -- Darin
---
[ 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 29 May 1999 01:00:16 GMT, Andrei Alexandrescu <andrewalex@hotmail.com> wrote:

>My question is: why didn't anyone do that? Would this be a conforming
>implementation?

Perhaps implementors of the STL haven't gotten around to taking advantage
of the empty base optimization because most compilers don't do the
optimization.  I figure that if compilers don't do the useful return value
optimization, then they don't do the more esoteric empty base optimization.
OK, so maybe this is a goofy reason.

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

Andrei Alexandrescu wrote:
>
> Hi,
>
> So the commitee decided to make the allocator a non-static member of
> each container. This takes up some extra space, increasing the sizeof

That's not quite what the standard says. Section 23.1 p8 requires that:

"Copy constructors for all container types defined in this clause copy
an allocator argument from their respective first parameters. All other
constructors for these container type take an Allocator& argument
(20.1.5), an allocator whose value type is the same as the container's
value type. A copy of this argument is used for any memory allocation
performed, by these constructors and by all member functions, during the
lifetime of each container object. In all container types defined in
this clause, the member get_allocator() returns a copy of the Allocator
object used to construct the container."

While having a non-static Allocator member is perhaps the simplest way
to achieve all of these requirements, the standard doesn't mandate it,
and I think the technique you describe below could meet the above
requirement equally well.

Also, keep in mind section 20.1.5 p4, which says that

"Implementations of containters described in this International Standard
are permitted to assume that their Allocator template parameter meets
the following two additional requirements beyond those in Table 32.

-- All instances of a given allocator type are required to be
interchangeable and always compare equal to each other."

Thus, by the as-if rule, a static Allocator member of each container
class would be perfectly legal.

> the container. This is usually unnecessary, because the default
> allocators as well as most custom allocators do not have any data
> members.
>
> This could be avoided by inheriting privately from the allocator class
> and making the appropriate using declaration. By doing this, you allow
> the compiler to perform the empty-base optimization, rendering the size
> of the vector optimal.
---
[ 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 <slrn7kuslh.o1b.sbnaran@fermi.ceg.uiuc.edu>,
  sbnaran@KILL.uiuc.edu wrote:
> On 29 May 1999 01:00:16 GMT, Andrei Alexandrescu
<andrewalex@hotmail.com> wrote:
> Perhaps implementors of the STL haven't gotten around to taking
advantage
> of the empty base optimization because most compilers don't do the
> optimization.  I figure that if compilers don't do the useful return
value
> optimization, then they don't do the more esoteric empty base
optimization.

I'm affraid you're wrong. The empty base optimization (EBO) is very
easy to implement, easier than RVO. In the case of RVO, compilers have
to figure out which is the temporary that'll get returned, cope with
multiple retuns, etc. So I think RVO is more esoteric than EBO.

MSVC does EBO for years. It fails to perform RVO in some cases.

Andrei


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


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