Do not pay for... xxx.push_back()
Attila Feher
As far as I understood from the Design and Evolution of C++ and every
other publication I read a major goal in C++ is to not to introduce
unneeded burder (time/asm instructions) while "doing something".
Actually the ideal state is that C++ is as effective as C... leaving
room to no other language than pure assembler "below" C++. I love
that. However I do not get how does the vector::push_back() fit into
this picture... Can you help me out why is this as it is?
What is my problem:
std::container<T>::push_back( const T&x);
I have no shorter way to describe it. :-)) Well, that const T&, that
bothers me.
Let's say I have a class, which creates a big key from a string. So for
the type T (which is my "big key class") I have a const char * (and/or
const std::string &) constructor. My original string is 80 bits, the
resulting key is much longer. I just picked up this example, the old
pkZIP was doing sth like this. But basically I have a small data
(structure) from which I create a large with a constructor.
So far so good. I pass a small structure to push_back. But, to be able
to push a T back, C++ will create a temporary T, bind the const-ref to
it, and then copy construct the real T inside the vector (the _only_
thing I wanted to create!) from this temporary.
I have tested this using SUN's implementation (6.1) and unfortunately it
is like this. I see a constructor call and then a copy constructor
call. :-(( I looked at the standard, and I see the push_back being
defined what I wrote above. And whatever optimizations I asked for it
was not enough to get rid of the in-excess copying.
And I don't really get it. The standard contains the requirement for
member function templates. I have actually started to tweak the
RogueWave STL header(s) (vector, memory) coming with the SUN compiler
and I was able to create a push_back, which actually used only one
constructor: the one, which "replacement new'd" the final object to the
right place.
So I started to wonder (since all it took was to make some members to be
templated on the const Z& arg) why do we all over the world pay for this
copying? Or is it just me? (My compiler?) Should this be optimized
away?
I know, that this little thing leads faaar away, since one may ask: how
about multiply argument constructors. Why don't we support overloaded
push_backs, where actually I can give more than one argument to the
constructor... Well, that part starts to be tricky, since where do we
stop? At 60 arguments? etc.
My problem is that I have to work with a sort of "conversion", where a
bigClassRepresentedAsFormatA is converted to
bigClassRepresentedAsFormatB. And not only one, but several. Coming in
as a vector of FormatA classes and going out as a vector of FormatB
classes. Now you can see where I am going. I pay for copying FormatB
classes and they are _large_. And I do _not_ need to copy them, since I
do have a constructor taking FormatA object const-ref. I hear Herbs
voice "Use PIMPL!"... but then I would choke on the MT pessimization
caused by excessive memory allocation. And I do not need my FormatB
classes on the heap... since they _are_ on the heap already inside the
vector...
So I am stuck here. Is there a hidden gotcha here I do not see, why
push_back is not a member template? And not only push_back, but all the
like. I would also argue that map::insert could also construct the pair
_only_ at the final place...
And just to push_to_excess(): is there a missing C++ feature here, why
it isn't simple enough to make push_back to take _any_ number of _any_
types (as template)? Well, I know: I _could_ make a class (like the
optional arguments class suggested by Stroustrup) but that would be
again paying for something I do not use. All I want, is the C++
template mechanism to support this kind of delegation from an arbitraty
push_back(...) to the final replacement new. And well, if I do not have
the appropriate constructor, I get a 12.5KB error message... and will do
better next time.
Where do I miss the point? It all seems so simple - I mean that it
should have been possible. Is there some very good - but hidden for me
reason why this must not be done?
Attila
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
James Kanze
|> As far as I understood from the Design and Evolution of C++ and
|> every other publication I read a major goal in C++ is to not to
|> introduce unneeded burder (time/asm instructions) while "doing
|> something". Actually the ideal state is that C++ is as effective
|> as C... leaving room to no other language than pure assembler
|> "below" C++. I love that. However I do not get how does the
|> vector::push_back() fit into this picture... Can you help me out
|> why is this as it is?
Well, you can't compare vector::push_back to anything in C, because
there is nothing equivalent:-).
The rule you are probably thinking of is that you don't pay for what
you don't use. If you don't use std::vector::push_back, its presence
imposes no additional costs.
There is no rule saying that additional features which you use will be
free:-).
|> What is my problem:
|> std::container<T>::push_back( const T&x);
[Description of expensive to copy class deleted....]
|> Where do I miss the point? It all seems so simple - I mean that
|> it should have been possible. Is there some very good - but
|> hidden for me reason why this must not be done?
The solution is, of course, to make your class cheap to copy. There
are several ways to do this: use copy-on-write for the data in the
implementation; use deferred initialization, in which the constructor
only saves the initialization data, and the actually initialization
only takes place on first use.
I used the latter in my last application; the actual data was a class
with an std::vector<> with a size of around 100,000, which was
inserted in another std::vector using push_back. I obviously didn't
want to do a deep copy of 100,000 elements (even if the elements were
pointers, initially null), so I simply deferred the initialization of
the vector until it was in its final place, and called an initialize
function in the class which did a resize on the vector. (Note that
this means that I also did a reserve of the necessary size in the
outer vector before starting, since any reallocation would involve a
deep copy as well.)
It is important to understand the philosophy behind the STL. It is
value oriented. This means that it considers the elements in the
containers to be values, to be copied at will. In some cases, you do
get additional guarantees -- after reserve on a vector, for example,
you are (more or less) guaranteed that none of the elements will be
copied as long as the actual size doesn't exceed the argument to
reserve. But these are all special cases, and are not fundamental to
the STL. Generally speaking, copy should be cheap, or you should not
be using the STL.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique oriente objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)179 2607481
Attila Feher
>
> Attila Feher <Attila...@lmf.ericsson.se> writes:
[SNIP]
> Well, you can't compare vector::push_back to anything in C, because
> there is nothing equivalent:-).
Well, I guess I did not really compare it to C.
> The rule you are probably thinking of is that you don't pay for what
> you don't use. If you don't use std::vector::push_back, its presence
> imposes no additional costs.
Nope. What I thought is that if I use vector _and_ push back, I do not
need to pay for something I do not use or ask for: namely th creation of
a temporary object.
> There is no rule saying that additional features which you use will be
> free:-).
Yep. But I guess there is a rule saying that additional features should
be implemented as optimum as possible (but not more :-), since otherwise
how will it be possible ot leave room only for assembly?
> |> What is my problem:
>
> |> std::container<T>::push_back( const T&x);
>
> [Description of expensive to copy class deleted....]
>
> |> Where do I miss the point? It all seems so simple - I mean that
> |> it should have been possible. Is there some very good - but
> |> hidden for me reason why this must not be done?
>
> The solution is, of course, to make your class cheap to copy.
[SNIPped description of how to make my app slower using COW and how to
make deferred init, which does not help me]
OK. Let's make the situation more clear. _Both_ my class A and B are
_huge_. They represent the same data, different ways. I have no way to
defer init of B (when created from A) since the A objects' lifetime is
out of my hand and I have no idea _when_ the B object will be used - and
99% of the cases when B is first used A is already dead.
> It is important to understand the philosophy behind the STL. It is
> value oriented. This means that it considers the elements in the
> containers to be values, to be copied at will.
Great. This still does not answer the original question: why should I
pay for a temporary value, when I do not need it and there is a way to
avoid it?
> In some cases, you do
> get additional guarantees -- after reserve on a vector, for example,
> you are (more or less) guaranteed that none of the elements will be
> copied as long as the actual size doesn't exceed the argument to
> reserve.
Great. I have no problem with that. That is something I have "asked
for" by choosing a dynamic sized type.
> But these are all special cases, and are not fundamental to
> the STL. Generally speaking, copy should be cheap, or you should not
> be using the STL.
Wow. So basically you say: if your system involves multithreading and
decently large enough objects, please revert to writing your own
containers, because we have only planned STL to be used with
integers??? Sorry, I cannot believe this can be true in such a powerful
language as C++. I mean I can understand that noone has thought of it,
that push_back may be too expensive with big classes etc. I can believe
that in my templated push_back-dream there is some serious drawback.
But I cannot believe that a deliberate decision has been taken to limit
the use of the standard library containers to small types.
We all know that mad-COW disease strikes in MT, so COW is not a
solution. In dynamic enough environments deferred init is not a
solution either, if your objects are both large enough, since the source
object may have been deleted when you first try to use the target one.
So I am really sorry to say, but I still wait for an answer or an
argument, which clarifies why push_back isn't templated to avoid
creating unneeded temporaries. Either there is some hidden pitfall I
don't know about (would not be the first case) or...?
Attila
Andrei Alexandrescu
news:86n0ur6...@alex.gabi-soft.de...
> Attila Feher <Attila...@lmf.ericsson.se> writes:
[snip]
> |> What is my problem:
>
> |> std::container<T>::push_back( const T&x);
> The solution is, of course, to make your class cheap to copy.
> It is important to understand the philosophy behind the STL. It is
> value oriented.
I believe this answer is misleading. The solution is *not* to uglify
his own code for the sake of a missing concept in the language. OP's
problem is best solved by introducing the notion of moving
constructors in the language, which is dearly needed. This solution
does not contradict the philosphy of STL in any way.
Andrei
Adin Hunter Baber
Attila Feher <Attila...@lmf.ericsson.se> wrote:
> So I am really sorry to say, but I still wait for an answer or an
> argument, which clarifies why push_back isn't templated to avoid
> creating unneeded temporaries. Either there is some hidden pitfall I
> don't know about (would not be the first case) or...?
>
Is your code going to be used multi-platform or multi-compiler?
If not, you could make the templated push_back() and put it into the
vector class yourself. I realize that this brings maintenance
nightmares, but I have found that to be a general problem with hardcore
optimizations.
James Kanze
|> James Kanze wrote:
|> > Attila Feher <Attila...@lmf.ericsson.se> writes:
|> [SNIP]
|> > The rule you are probably thinking of is that you don't pay for
|> > what you don't use. If you don't use std::vector::push_back,
|> > its presence imposes no additional costs.
|> Nope. What I thought is that if I use vector _and_ push back, I
|> do not need to pay for something I do not use or ask for: namely
|> th creation of a temporary object.
In order to push back something, you need something to push back. If
it is a temporary object, this is NOT a cost of push_back.
|> > There is no rule saying that additional features which you use
|> > will be free:-).
|> Yep. But I guess there is a rule saying that additional features
|> should be implemented as optimum as possible (but not more :-),
|> since otherwise how will it be possible ot leave room only for
|> assembly?
There is no rule concerning how optimal anything must be. On the
whole, the STL is designed with far too much attention to runtime; it
can be implemented in a very efficient manner. But the STL is
designed to handle values, and by definition, a value is copiable.
This fits in with C++ in general, where the basic types are values,
and if you want reference semantics, you have to use pointers (which
are, themselves, values).
If you need something special, you have to write it yourself. I find
this perfectly normal -- what you need will not be what I need, and if
we try and put everything that anyone might possibly need into the
language, the standard won't fit on my disk anymore.
|> > |> What is my problem:
|> > |> std::container<T>::push_back( const T&x);
|> > [Description of expensive to copy class deleted....]
|> > |> Where do I miss the point? It all seems so simple - I mean
|> > |> that it should have been possible. Is there some very good
|> > |> - but hidden for me reason why this must not be done?
|> > The solution is, of course, to make your class cheap to copy.
|> [SNIPped description of how to make my app slower using COW and how to
|> make deferred init, which does not help me]
|> OK. Let's make the situation more clear. _Both_ my class A and B
|> are _huge_. They represent the same data, different ways. I have
|> no way to defer init of B (when created from A) since the A
|> objects' lifetime is out of my hand and I have no idea _when_ the
|> B object will be used - and 99% of the cases when B is first used
|> A is already dead.
So you have some special requirements. I was only throwing out
suggestions.
The STL (and most of C++) is based on value semantics. Value
semantics suppose a relatively cheap copy, at least in general.
|> > It is important to understand the philosophy behind the STL. It
|> > is value oriented. This means that it considers the elements in
|> > the containers to be values, to be copied at will.
|> Great. This still does not answer the original question: why
|> should I pay for a temporary value, when I do not need it and
|> there is a way to avoid it?
There is no way to avoid it. You must pass something to push_back.
I can imagine ways of avoiding the temporary in specific cases, but
nothing generally useful. And if it isn't generally useful, it
doesn't belong in the standard.
|> > In some cases, you do get additional guarantees -- after reserve
|> > on a vector, for example, you are (more or less) guaranteed that
|> > none of the elements will be copied as long as the actual size
|> > doesn't exceed the argument to reserve.
|> Great. I have no problem with that. That is something I have
|> "asked for" by choosing a dynamic sized type.
|> > But these are all special cases, and are not fundamental to the
|> > STL. Generally speaking, copy should be cheap, or you should
|> > not be using the STL.
|> Wow. So basically you say: if your system involves multithreading
|> and decently large enough objects, please revert to writing your
|> own containers, because we have only planned STL to be used with
|> integers???
Well, that is at least partially true. C++ definitly uses value
semantics by default -- with the built-in types, for example. And the
STL was designed to be efficient with the built-in types. It is also
efficient with user defined types, in so far as they more or less
conform to the basic value semantics of the built-in types.
This is a fundamental design decision of C++. If you really cannot
live with it, try another language. The problem you are describing
cannot exist in lisp, for example, which is based on reference
semantics and object sharing. It wouldn't exist in Java, either. On
the other hand, C++ is very flexible, and you can easily implement a
container of pointers (smart or not), and pass pointers to the object
around, rather than the complete object. The only restriction is that
unlike Lisp or Java, you must take care of the memory management.
In all cases, the basic problem remains: the information necessary to
construct the object is not present (and cannot be present) in the
implementation of vector. In the case of a value oriented language,
the normal solution is to construct at the call site and then copy; in
reference oriented languages, it is to construct at the call site and
then pass a pointer. The first involves a copy which you don't want.
The second imposes dynamic allocation, which you don't want. (In Lisp
or Java, *all* objects are dynamically allocated.)
This is the abstraction penalty which was recently mentionned in
another thread. If you forgo abstraction, it is trivial to create a
container which knows how to construct your object from its
parameters, in place, or to delve into the container at the call site,
to construct the new object in place. Since one of the main purposes
of std::vector *is* abstraction, direct support for either would seem
out of place. If performance IS a real problem, and there is no other
solution, then you must forgo the abstraction. At a real cost to
maintainability.
I really think it is too much to ask for the standard to support this.
In the case of vector, practical considerations have already lead to
some compromizes in the abstraction (implementation must be
contiguous, etc.). I'm not eager to go further in this direction.
|> Sorry, I cannot believe this can be true in such a powerful
|> language as C++. I mean I can understand that noone has thought
|> of it, that push_back may be too expensive with big classes etc.
They've thought of it. I imagine that the general consensus is that
normally, things like COW and delayed initialization are sufficient,
and that it isn't worth breaking the abstraction for the rare cases
where they are not.
Even in your case, I find it difficult to believe that separating
initialization from default construction couldn't provide a solution.
From what you have said, I suspect that a default constructor probably
doesn't even exist in the target class. So a simple solution would be
to provide one, which does absolutely nothing -- it leaves the class
data as raw memory. And provide an initialization function which does
the same job as the normal constructor. By doing this, this
particular problem is solved by writing:
vectorOfBs.push_back( B() ) ;
vectorOfBs.last().initialize( someA ) ;
You may need to add some sort of flag, so that copy construction can
do the right thing, according to whether the object is initialized or
not. If the object contains pointers to dynamic data, just
initializing the pointers to NULL should suffice.
If you're worried that some nave client might create B's using the
default constructor, and try to use them, you might consider making
the default constructor private, and add a static member function,
constructInVector, which does the above.
|> I can believe that in my templated push_back-dream there is some
|> serious drawback. But I cannot believe that a deliberate decision
|> has been taken to limit the use of the standard library containers
|> to small types.
There is an implicit decision to limit the use of the standard library
containers to types appropriate to be copied. What that means depends
on the application, but the standard library is very definitly
designed with value semantics in mind.
|> We all know that mad-COW disease strikes in MT, so COW is not a
|> solution.
We all know that COW can be made to work well in MT environments in
specific cases. It may not be appropriate for a general purpose
class, like std::string, where the implementor cannot know how the
class will be used. But that doesn't mean that it doesn't work in
more specific cases.
In your case, if the vector is being accessed from other threads, you
need a lock for every access -- any manipulation of the counter is
guarded by that lock.
|> In dynamic enough environments deferred init is not a solution
|> either, if your objects are both large enough, since the source
|> object may have been deleted when you first try to use the target
|> one.
Deferred initialization doesn't mean that you have to defer it
forever. In my case, I only deferred it until the object was in its
final location; in my case as well, the actual initialization data
wouldn't have been available later.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique oriente objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)179 2607481
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Adin Hunter Baber
post. Please snip 9further0 and resubmit. -mod}
In article <3CEBA9F3...@lmf.ericsson.se>,
Attila Feher <Attila...@lmf.ericsson.se> wrote:
> James Kanze wrote:
[vorpal sword applied]
Would it be possible to simply use a vector of smart pointers? That way
you could save all of that copying.
James Kanze
|> "James Kanze" <ka...@alex.gabi-soft.de> wrote in message
|> news:86n0ur6...@alex.gabi-soft.de...
|> > Attila Feher <Attila...@lmf.ericsson.se> writes:
|> [snip]
|> > |> What is my problem:
|> >
|> > |> std::container<T>::push_back( const T&x);
|> [snip]
|> > The solution is, of course, to make your class cheap to copy.
|> [snip]
|> > It is important to understand the philosophy behind the STL. It is
|> > value oriented.
|> I believe this answer is misleading. The solution is *not* to
|> uglify his own code for the sake of a missing concept in the
|> language. OP's problem is best solved by introducing the notion of
|> moving constructors in the language, which is dearly needed. This
|> solution does not contradict the philosphy of STL in any way.
I disagree. Not only the STL, but much of C++, is value oriented.
Value orientation implies copying.
I don't know of any language which would solve his problem -- he
doesn't want a copy, and he doesn't want to dynamically allocate the
object. Languages which don't use a copy require everything to be
dynamically allocated. C++ generally prefers copying (value
semantics) when applicable, but really offers a choice -- he can
locally construct and copy, or he can construct dynamically, and pass
a pointer. I'm not sure what else you can offer without uglifying
something by breaking abstraction.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique oriente objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)179 2607481
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Francis Glassborow
<andre...@hotmail.com> writes
>I believe this answer is misleading. The solution is *not* to uglify
>his own code for the sake of a missing concept in the language. OP's
>problem is best solved by introducing the notion of moving
>constructors in the language, which is dearly needed. This solution
>does not contradict the philosphy of STL in any way.
I agree, but we need someone with real understanding of the issues to
write a proposal for such ctors including an impact statement with
regards to the rest of the language and the benefits from suppling them.
i.e.
What is the problem or problems
How does a move ctor address the problem
Tentative syntax
What are the potential costs (i.e. show that you have considered abuses
as well as uses)
How does in interact with the rest of the language.
How difficult is it to implement (though you might need to consult a
couple of implemetors for that)
The above schema is a rough guide for any proposed extension to the core
language.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
Andrei Alexandrescu
> "Andrei Alexandrescu" <andre...@hotmail.com> writes:
> |> I believe this answer is misleading. The solution is *not* to
> |> uglify his own code for the sake of a missing concept in the
> |> language. OP's problem is best solved by introducing the notion
of
> |> moving constructors in the language, which is dearly needed.
This
> |> solution does not contradict the philosphy of STL in any way.
>
> I disagree. Not only the STL, but much of C++, is value oriented.
> Value orientation implies copying.
This is a misunderstanding. Move semantics do not eliminate copy
semantics.
> I don't know of any language which would solve his problem -- he
> doesn't want a copy, and he doesn't want to dynamically allocate the
> object.
He wants to smoothly move the object from a place to another, and
leave the source as an empty shell. In other words, he'd like a short,
efficient, and less problematic variant of:
v.resize(v.size() + 1);
B obj = ...;
swap(v.back(), obj);
(By the way, Attila, this is as close as you get within the current
language.)
> Languages which don't use a copy require everything to be
> dynamically allocated. C++ generally prefers copying (value
> semantics) when applicable, but really offers a choice -- he can
> locally construct and copy, or he can construct dynamically, and
pass
> a pointer. I'm not sure what else you can offer without uglifying
> something by breaking abstraction.
I'm talking about a third operation, move, which turns out to be as
fundamental as copying. There are past articles here and on boost by
Hinnant, Abrahams and others on the subject.
Andrei
Howard Hinnant
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <86vg9e7...@alex.gabi-soft.de>, James Kanze
<ka...@alex.gabi-soft.de> wrote:
| |> I believe this answer is misleading. The solution is *not* to
| |> uglify his own code for the sake of a missing concept in the
| |> language. OP's problem is best solved by introducing the notion of
| |> moving constructors in the language, which is dearly needed. This
| |> solution does not contradict the philosphy of STL in any way.
|
| I disagree. Not only the STL, but much of C++, is value oriented.
| Value orientation implies copying.
|
| I don't know of any language which would solve his problem -- he
| doesn't want a copy, and he doesn't want to dynamically allocate the
| object. Languages which don't use a copy require everything to be
| dynamically allocated. C++ generally prefers copying (value
| semantics) when applicable, but really offers a choice -- he can
| locally construct and copy, or he can construct dynamically, and pass
| a pointer. I'm not sure what else you can offer without uglifying
| something by breaking abstraction.
If the vector element is movable, and if vector's push_back is move
aware, and if the right small tweaks to the language can be made, move
semantics is an /extremely/ elegant solution to this problem. Move
semantics and value oriented (copy semantics) can coexist quite nicely.
Move's can be made from rvalues without anybody noticing (except for
the increased performance). Imho, move semantics are one of the most
important concepts that should be considered for C++0X. So much so,
that I'm personally willing to put significant time and energy into
helping make it happen.
Unfortunately James, only you will see this post (via email). I am
unable to post to comp.lang.c++.moderated.
{ Surprise, it's here. :) -mod/jep }
--
Howard Hinnant
Metrowerks
Howard Hinnant
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <QmrFAuGI...@robinton.demon.co.uk>, Francis Glassborow
<francis.g...@ntlworld.com> wrote:
| In article <acgitl$pe5kf$1...@ID-14036.news.dfncis.de>, Andrei Alexandrescu
| <andre...@hotmail.com> writes
| >I believe this answer is misleading. The solution is *not* to uglify
| >his own code for the sake of a missing concept in the language. OP's
| >problem is best solved by introducing the notion of moving
| >constructors in the language, which is dearly needed. This solution
| >does not contradict the philosphy of STL in any way.
|
| I agree, but we need someone with real understanding of the issues to
| write a proposal for such ctors including an impact statement with
| regards to the rest of the language and the benefits from suppling them.
|
| i.e.
| What is the problem or problems
| How does a move ctor address the problem
| Tentative syntax
| What are the potential costs (i.e. show that you have considered abuses
| as well as uses)
| How does in interact with the rest of the language.
| How difficult is it to implement (though you might need to consult a
| couple of implemetors for that)
|
| The above schema is a rough guide for any proposed extension to the core
| language.
<raising my hand> I hope to have such a proposal in time for Santa
Cruz (with help from several others). Thank you for the outline.
--
Howard Hinnant
Metrowerks
Garry Lancaster
> |> > |> What is my problem:
> |> >
> |> > |> std::container<T>::push_back( const T&x);
James Kanze:
> |> > The solution is, of course, to make your class cheap to copy.
> |> [snip]
> |> > It is important to understand the philosophy behind the STL. It is
> |> > value oriented.
Andrei Alexandrescu:
> |> I believe this answer is misleading. The solution is *not* to
> |> uglify his own code for the sake of a missing concept in the
> |> language. OP's problem is best solved by introducing the notion of
> |> moving constructors in the language, which is dearly needed. This
> |> solution does not contradict the philosphy of STL in any way.
James Kanze:
> I disagree. Not only the STL, but much of C++, is value oriented.
> Value orientation implies copying.
If I understand him correctly, the original poster isn't
objecting to copying per se, just to unnecessary
copying in one particular place. In other words he's
asking for
template <typename T, typename A>
template <typename CtorParam1,...>
void std::vector<T, A>::push_back<CtorParam1, ...>(
CtorParam1 ctorParam1,...)
{
// Allocate memory for new element in vector.
// Construct vector in place using supplied ctor parameters
}
This is difficult in C++, because there is no varargs
template argument system and because of the
interactions of references, const and temporaries
when supplied to template functions. This last point
is a little obscure and at least partly to do with
non-standard compiler behaviour, but for an example
of what I'm getting at, try to write a single template
function that just forwards to a function that could
take a T, T& or const T& as a parameter.
Kind regards
Garry Lancaster
Codemill Ltd
Visit our web site at http://www.codemill.net
Francis Glassborow
Hinnant <hin...@antispam.metrowerks.com> writes
><raising my hand> I hope to have such a proposal in time for Santa
>Cruz (with help from several others). Thank you for the outline.
Great. I guess we will easily be able to add the missing element
(classifying the nature of the problem, I guess this one best comes
under 'improve support for generic programming' )
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
James Kanze
|> "James Kanze" <ka...@alex.gabi-soft.de> wrote in message
|> news:86vg9e7...@alex.gabi-soft.de...
|> > "Andrei Alexandrescu" <andre...@hotmail.com> writes:
|> > |> I believe this answer is misleading. The solution is *not*
|> > |> to uglify his own code for the sake of a missing concept in
|> > |> the language. OP's problem is best solved by introducing the
|> > |> notion of moving constructors in the language, which is
|> > |> dearly needed. This solution does not contradict the
|> > |> philosphy of STL in any way.
|> > I disagree. Not only the STL, but much of C++, is value
|> > oriented. Value orientation implies copying.
|> This is a misunderstanding. Move semantics do not eliminate copy
|> semantics.
Agreed. I was not considering move semantics. I don't know if it
would help him or not; depending on how the class is organized, moving
it could be just as expensive as copying it. (My impression is that
he has minimized use of dynamic memory, on performance grounds. And
move semantics are mainly a big win when the class has one or two
pointers to really large blocks of dynamic memory. On the other hand,
if his class has a lot of std::string, and this is modified to support
move, it might help.)
|> > I don't know of any language which would solve his problem -- he
|> > doesn't want a copy, and he doesn't want to dynamically allocate
|> > the object.
|> He wants to smoothly move the object from a place to another, and
|> leave the source as an empty shell.
That's not what he said. He said he didn't want to copy. If the
class uses pointers to uniquely owned separate memory, move semantics
can avoid copying what is pointed to. But if the class contains the
data directly, move semantics don't really change anything.
(Of course, neither of us really know the details of the class, so we
are both just speculating. All I'm saying is that we -- you and I --
are talking about different things, and we may not disagree at all.)
|> In other words, he'd like a short, efficient, and less problematic
|> variant of:
|> v.resize(v.size() + 1);
|> B obj = ...;
|> swap(v.back(), obj);
What you think he'd like... My interpretation was taht the class
itself was big, and that copying or moving would result in about the
same amount of work. But I'll admit that he didn't really say one way
or the other.
|> (By the way, Attila, this is as close as you get within the
|> current language.)
I presented an alternative solution, which worked when I had the same
problem. (In my case, move semantics probably would have helped too,
since the data I was copying was in an std::vector.)
|> > Languages which don't use a copy require everything to be
|> > dynamically allocated. C++ generally prefers copying (value
|> > semantics) when applicable, but really offers a choice -- he can
|> > locally construct and copy, or he can construct dynamically, and
|> > pass a pointer. I'm not sure what else you can offer without
|> > uglifying something by breaking abstraction.
|> I'm talking about a third operation, move, which turns out to be
|> as fundamental as copying. There are past articles here and on
|> boost by Hinnant, Abrahams and others on the subject.
Move is really just a minor variation on copy; the default semantics
of move are copy-destroy. In this sense, it fits perfectly into a
value semantics mould. Abstractly, it doesn't even introduce a new
concept. From a design point of view, it is an optimization. Whether
this optimization would help in this particular case, I have no idea;
it depends on the internal structure of his data. But move is
certainly not something fundamental, and in no way changes the
expressive potential of the language.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique oriente objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)179 2607481
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Anthony Williams
> "Andrei Alexandrescu" <andre...@hotmail.com> writes:
>
> |> "James Kanze" <ka...@alex.gabi-soft.de> wrote in message
> |> > dynamically allocated. C++ generally prefers copying (value
> |> > semantics) when applicable, but really offers a choice -- he can
> |> > locally construct and copy, or he can construct dynamically, and
> |> > pass a pointer. I'm not sure what else you can offer without
> |> > uglifying something by breaking abstraction.
>
> |> I'm talking about a third operation, move, which turns out to be
> |> as fundamental as copying. There are past articles here and on
> |> boost by Hinnant, Abrahams and others on the subject.
>
> Move is really just a minor variation on copy; the default semantics
> of move are copy-destroy. In this sense, it fits perfectly into a
> value semantics mould. Abstractly, it doesn't even introduce a new
> concept. From a design point of view, it is an optimization. Whether
> this optimization would help in this particular case, I have no idea;
> it depends on the internal structure of his data. But move is
> certainly not something fundamental, and in no way changes the
> expressive potential of the language.
Conceptually, sometimes things can be moved, but not copied, so moving is
definitely a new concept, even if the default semantics are the same as
copy-destroy. Where only a single instance of a resource can exist, it is
possible to desire transfer of ownership (i.e. move semantics), without
wanting to permit copying. Of course, this could be achieved by using
std::auto_ptr, but that requires an extra level of redirection. Another
possibility is shared ownership, but there might be valid reasons for
needing a single point of access. In any case, such
moveable-but-not-copyable objects can't currently be stored in standard
containers without shared ownership; if the standard was modified to have
the concept of move semantics, you could store them in the standard
containers --- move them in; the container can then move them around
internally without copying, when necessary (e.g. when reallocating a
std::vector<>), and we could provide an interface for moving the elements
out of the container (which would erase the contained elements).
Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optical Components Ltd
The opinions expressed in this message are not necessarily those of my
employer
Attila Feher
[SNIP]
> I disagree.
That we all see! :-))) I disagree, too! Does this mean we agree?
:-)))
> Not only the STL, but much of C++, is value oriented.
You love this value orientation/semantics. I am value oriented. :-)
> Value orientation implies copying.
Well, that is what I want. Copying. ONE copying and not TWO copying.
> I don't know of any language which would solve his problem -- he
> doesn't want a copy, and he doesn't want to dynamically allocate the
> object.
Stop the train! I _do_ want a copy! I want a copy of my class A object
as class B object! ONE copy. And how could you say that I do not want
to dynamically allocate? It is in a vector! It is _already_
dynamically allocated!
> Languages which don't use a copy require everything to be
> dynamically allocated.
I want a copy. ONE copy and ONE copy only, so help me God.
> C++ generally prefers copying
Did you ask him?
> (value semantics)
Steve Dewhurst will change his company name after seeing this thread...
> when applicable,
And it is applicable here. Do one and only one copy. From a class A
object I copy the data to a class B object. And _only_ that. After
that I do not want to copy my class B object again. I want to make the
copying to the "final destination": inside the vector. And it can be
done, I have done it by changing the push_back (and some other little
allocator related functions to member templates).
> but really offers a choice -- he can
> locally construct and copy, or he can construct dynamically, and pass
> a pointer.
It's a choice like: do you want bullet or the chair?
> I'm not sure what else you can offer without uglifying
> something by breaking abstraction.
What I have just told: templated push_back. I believe I have already
mentioned this in my opening post.
Attila
Attila Feher
[SNIP]
> Would it be possible to simply use a vector of smart pointers? That way
> you could save all of that copying.
And re-introduce the nightmare of threads colliding on memory
allocation. I already have my classes on the heap inside the vector.
Allocating them (again) one-by-one from the heap would only make the
code slower (creation, access, destruction), create more stress on the
already screaming OS memory-manager and even make it possible that I
loose locality of reference while walking the vector and end up with way
too many cache updates. Instead of cash updates :-)
Attila
Attila Feher
[SNIP]
> In order to push back something, you need something to push back. If
> it is a temporary object, this is NOT a cost of push_back.
Well, you miss the point. I do not want to push_back something! It
isn't my fault the function is named like this. There are enough other
things which are, so I do not take the blame for this one. :-)))
What I want to do is to _construct_ a new element inside the vector,
using the other object (having other type) as input.
> |> > There is no rule saying that additional features which you use
> |> > will be free:-).
>
> |> Yep. But I guess there is a rule saying that additional features
> |> should be implemented as optimum as possible (but not more :-),
> |> since otherwise how will it be possible ot leave room only for
> |> assembly?
>
> There is no rule concerning how optimal anything must be.
It is only me, or does anyone else get the feeling that you have to be
right? No offense meant. But _if_ the STL is designed with _no_
performance in mind... well, then the STL should not be part of C++.
Since one of the major goals of C++ was performance.
> On the
> whole, the STL is designed with far too much attention to runtime; it
> can be implemented in a very efficient manner. But the STL is
> designed to handle values, and by definition, a value is copiable.
Yes. Value is copyable. _With_costs_. And _why_ would I _create_ an
_unneeded_ temporary and then _copy_ it to another place? What does
make this logical? IMHO nothing.
> This fits in with C++ in general, where the basic types are values,
> and if you want reference semantics, you have to use pointers (which
> are, themselves, values).
I do not want reference semantics. I want a push_back, which is able to
"behave" and not force me to create a temporary object, which I do not
need and which - in fact - is not needed.
> If you need something special, you have to write it yourself.
Are you serious that not wasting CPU and memory by creating an
absolutely unneeded temporary is "special"? So this is normal (in your
opinion):
char a[10];
a[0]=1;
The latter line creates a temporary char on the stack from the number
one, and then copies it into the array. This is the normal?
> I find
> this perfectly normal -- what you need will not be what I need, and if
> we try and put everything that anyone might possibly need into the
> language, the standard won't fit on my disk anymore.
UhOh. So wasting time is normal. Please look at my "translated"
example, and ask yourself: is it normal to create a temporary when none
is needed?
> So you have some special requirements. I was only throwing out
> suggestions.
What is special on not wanting to have an absolutely unnecessary
temporary be created and destroyed?
> The STL (and most of C++) is based on value semantics. Value
> semantics suppose a relatively cheap copy, at least in general.
What? Sorry I guess I do not get this. You mean that STL has been
created for integers and not larger?
> |> > It is important to understand the philosophy behind the STL. It
> |> > is value oriented. This means that it considers the elements in
> |> > the containers to be values, to be copied at will.
>
> |> Great. This still does not answer the original question: why
> |> should I pay for a temporary value, when I do not need it and
> |> there is a way to avoid it?
>
> There is no way to avoid it. You must pass something to push_back.
Yes. Since I have just tweaked/hacked my copy of the STL to avoid the
unneeded temporary completely by making push_back (and some more
internals) a member template I hereby announce that there is a way. I
just do not get it yet why isn't it applied in the STL.
> I can imagine ways of avoiding the temporary in specific cases, but
> nothing generally useful.
Well, I doubt that any of us can declare him/herself as the "general
user". I myself have found this templatized push_back generally useful
and costless. Of course YMMV.
> And if it isn't generally useful, it
> doesn't belong in the standard.
Wow. I hope it won't be you deciding what gets into the standard. No
offense meant again. But I have just represented few cases (I guess
pretty usual one) when it would be nice to have a template-push_back.
In my little brain it is generally useful.
> |> Great. I have no problem with that. That is something I have
> |> "asked for" by choosing a dynamic sized type.
>
> |> > But these are all special cases, and are not fundamental to the
> |> > STL. Generally speaking, copy should be cheap, or you should
> |> > not be using the STL.
>
> |> Wow. So basically you say: if your system involves multithreading
> |> and decently large enough objects, please revert to writing your
> |> own containers, because we have only planned STL to be used with
> |> integers???
>
> Well, that is at least partially true.
Here I give up. Sorry, but I cannot seriously believe that you meant
this. I am now sure you are just kidding.
> C++ definitly uses value
> semantics by default -- with the built-in types, for example. And the
> STL was designed to be efficient with the built-in types. It is also
> efficient with user defined types, in so far as they more or less
> conform to the basic value semantics of the built-in types.
Sorry, could not resist: Aha, so basically user defined types, which
are not larger than an integer. And - according to your above
statements - this is supposed to be the "normal case". Any user defined
type larger than an integer or double is "special case". I am getting
sarcastic. :-(( Is it 1st of Arpil on Tatuin and just I do not know
it? Please, others, help me out here. I must have misunderstood
something very basic here. I always believed that any useful suer
defined data type will be significantly larger than an integer and that
the STL was there to server 99% of the C++ programmers and not 1% only,
who uses only built-ins.
> This is a fundamental design decision of C++.
Well, I have read Design and Evolution of C++ and I am sure I would
remember if this would have been mentioned. First of all I believe that
you are mixing here C++ (the language, which _really_ deals with values
mostly) and the STL. And I believe you have missed the whole point as
well. I do not care, if vector uses value/weight/volume or Value Addedd
Tax semantics. What I would like to see is that it does not create an
unneeded temporary, when I do push_back with a type, from which the
element type can be created.
> If you really cannot
> live with it, try another language.
No need to get deffensive. If I coul dnot live with C++ I would not
write here. But I believe that showing up attitude won't help with the
issue. If you love how the vector::push_back works, I am happy for
you. Really. But then I guess you could live some room for those here,
who actually has some answers to my questions, for which I have opened
this thread (no offense meant again):
- why isn't/wasn't push_back templated, is there any gotcha there I am
not aware of
- is there any way to avoid creating a who-needs-that temporary
> The problem you are describing
> cannot exist in lisp, for example, which is based on reference
> semantics and object sharing.
Great! How does this help me?
> It wouldn't exist in Java, either.
Perfect! How does this help me with my C++ problem?
> On
> the other hand, C++ is very flexible, and you can easily implement a
> container of pointers (smart or not), and pass pointers to the object
> around, rather than the complete object.
Yes. And seek for help how to tell to the users of the product that:
well, I have made some optimizations for speed in my product. Due to
the fact that my product is multithreaded I have actually can offer you
now 33% of its original capacity. It all sux, but it was told to me in
clc++mod that I have to do it this way.
In MT there is no way I will start allocating stuff on the heap just for
fun.
> The only restriction is that
> unlike Lisp or Java, you must take care of the memory management.
You know, working in C++ from around 1991 I am well aware of that.
> In all cases, the basic problem remains: the information necessary to
> construct the object is not present (and cannot be present) in the
> implementation of vector.
Hm. Pretty intersting thought. I still need to find out what does it
have to do with all of my questions.
[SNIP]
> contiguous, etc.). I'm not eager to go further in this direction.
Let's hope, it won't depend on you, whether vector will be made more
optimum or not.
> |> Sorry, I cannot believe this can be true in such a powerful
> |> language as C++. I mean I can understand that noone has thought
> |> of it, that push_back may be too expensive with big classes etc.
>
> They've thought of it. I imagine that the general consensus is that
> normally, things like COW and delayed initialization are sufficient,
> and that it isn't worth breaking the abstraction for the rare cases
> where they are not.
COW? I may be well not aware of how things evolved in the last 3 months
but before that there was a high consensus about COW being The Worst
Choice In Most Cases To Solve NonExisting Problems, especially if used
in MT environemt.
> Even in your case, I find it difficult to believe that separating
> initialization from default construction couldn't provide a solution.
Well, I think you need to work on your imagination. :-)))
> From what you have said, I suspect that a default constructor probably
> doesn't even exist in the target class. So a simple solution would be
> to provide one, which does absolutely nothing -- it leaves the class
> data as raw memory. And provide an initialization function which does
> the same job as the normal constructor. By doing this, this
> particular problem is solved by writing:
>
> vectorOfBs.push_back( B() ) ;
> vectorOfBs.last().initialize( someA ) ;
Well, if I hadn't had to read through all those lines repeating "value
sematics", I would be happy to see this. I have done this (BTW ther
_was_ a default constructor). but. But. _But_. _BUT_, this is a
_hack_. I create a crippled class, just because something, which could
be solved by having a templated push_back isn't there. Not to mention,
that for everyones laugh the class, I have inside the vector has
_vectors_ in it, so I just _cannot_ make its creation absolutely free.
[SNIP]
> There is an implicit decision to limit the use of the standard library
> containers to types appropriate to be copied. What that means depends
> on the application, but the standard library is very definitly
> designed with value semantics in mind.
Well. Value semantics again. I still say: it has nothing to do with
what I was talking about. Tests has proven that the unneeded temporary
can be eliminated by using a templated push_back. All I wanted to
> |> We all know that mad-COW disease strikes in MT, so COW is not a
> |> solution.
>
> We all know that COW can be made to work well in MT environments in
> specific cases.
Perfect! But my case is a normal case, I use already Hoard to be able
to serve the memory allocation needs without having it virtually render
my 4 CPU server to a 0.8 CPU one, I have to make highly portable code,
so works-on-this-CPU-hacks are out of the scope etc.
> It may not be appropriate for a general purpose
> class, like std::string, where the implementor cannot know how the
> class will be used. But that doesn't mean that it doesn't work in
> more specific cases.
Well, I believe that I know my case and it cannot work here. And in my
case memory allocation for all vector elements (and remember, I have
this about 4 levels deep!) separately is not the answer.
> In your case, if the vector is being accessed from other threads, you
> need a lock for every access -- any manipulation of the counter is
> guarded by that lock.
Which lock is created and destroyed on a way, that it may very easily
stop all other threads and render a 4 CPU machine to a 0.7CPU one, as it
already has happened when way too many (COW) std::strings has been
created and destroyed. This isn't the way to go. Why would I
overcomplicate and slow down my code?
[SNIP]
> Deferred initialization doesn't mean that you have to defer it
> forever. In my case, I only deferred it until the object was in its
> final location; in my case as well, the actual initialization data
> wouldn't have been available later.
Well, I see your point. I guess I do. You think that vector.push_back
is perfect and I have to do triple-flips in my code if I do not like
it. Point taken. Let's see now someone who actually can tell me why
isn't push_back a template, what problems would it cause if it would be.
Thanx for the long mail, but I believe that it has missed my point
completely. But I have learnt from it.
BR, Attila
Attila Feher
[SNIP]
Both. Just to make life easier. Probably multi-platform (OS _and_
CPU), multi-compiler _and_ may very well be multi-standard library at
some point. So hacking the push_back does not work. Esp. since you
need to hack deeply into the allocators as well. :-(((
What I came up with is: make default construction cheap, then fill the
elements of the vector directly. Hack it is, but the best one I could
come up with.
A
Dave Harris
> What I want to do is to _construct_ a new element inside the vector,
> using the other object (having other type) as input.
Sounds reasonable to me. Like:
template <typename T>
class vector {
public:
template <typename U>
iterator push_back( const U &u ) {
void *p = grab_memory_for_a_new_T();
new(p) T(u);
return end()-1;
}
// ...
};
(although real code would need allocators, exception safety etc). I think
this would be a reasonable proposal for the next std library. I don't
think we need support more than one argument, as other arguments can be
packed into a U type.
> Let's see now someone who actually can tell me why isn't push_back
> a template, what problems would it cause if it would be.
My guess is that nobody thought of it, at least not enough to propose it.
Weren't template member functions a relatively late addition? Perhaps
nobody reviewed std::vector looking for places where they might be handy.
I do have some concerns. If we have this templated pushed_back(), do we
still need the normal one? There are some subtle issues to do with
T::T(const U&) not being a copy constructor even when T and U are the same
type. Ditto with assignment. I am also worried about the quality of error
messages that are possible with doubled-up templates.
If we need to keep the non-templated versions, than that is quite a lot of
extra functions if we're to cover the various forms of insert() etc.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
James Dennett
> James Kanze wrote:
> [SNIP]
>
>>Value orientation implies copying.
>
>
> Well, that is what I want. Copying. ONE copying and not TWO copying.
I think not. You want a conversion, not a copy. You can
only copy from type X to type X.
>
>>I don't know of any language which would solve his problem -- he
>>doesn't want a copy, and he doesn't want to dynamically allocate the
>>object.
>
>
>
> Stop the train! I _do_ want a copy! I want a copy of my class A object
> as class B object!
That's not a copy then. It produces an object which is *not*
equivalent to the original, i.e., not a copy.
> ONE copy. And how could you say that I do not want
> to dynamically allocate? It is in a vector! It is _already_
> dynamically allocated!
Not as an individual object.
> And it is applicable here. Do one and only one copy. From a class A
> object I copy the data to a class B object.
And, as I say almost as many times as you claim that this is
making a copy, it is not.
> What I have just told: templated push_back. I believe I have already
> mentioned this in my opening post.
It seems like a reasonable thing to have put into the container
requirements, but I don't know if it's so easy to retro-fit. Would
it have any effect other than omitting a (real) copying operation?
--
James Dennett <jden...@acm.org>
Andrei Alexandrescu
> Move is really just a minor variation on copy; the default semantics
> of move are copy-destroy.
> In this sense, it fits perfectly into a
> value semantics mould. Abstractly, it doesn't even introduce a new
> concept.
> From a design point of view, it is an optimization. Whether
> this optimization would help in this particular case, I have no idea;
> it depends on the internal structure of his data. But move is
> certainly not something fundamental, and in no way changes the
> expressive potential of the language.
Sorry, I'd say that each and every sentence quoted above is wrong. This is a
different semantics, and not an optimization.
Andrei
Niklas Matthies
> "Andrei Alexandrescu" <andre...@hotmail.com> writes:
[毽愍
> |> I'm talking about a third operation, move, which turns out to be
> |> as fundamental as copying. There are past articles here and on
> |> boost by Hinnant, Abrahams and others on the subject.
>
> Move is really just a minor variation on copy; the default semantics
> of move are copy-destroy. In this sense, it fits perfectly into a
> value semantics mould. Abstractly, it doesn't even introduce a new
> concept. From a design point of view, it is an optimization.
It's not just optimization. It's a "new concept" in the sense that
Copy-Destroy often cannot be guaranteed not to fail (because of the
copy), while Move generally can be. Furthermore, there are types for
which Copy doesn't make sense (e.g. auto_ptr) while Move does.
[毽愍
> But move is certainly not something fundamental, and in no way
> changes the expressive potential of the language.
I don't quite agree with this.
-- Niklas Matthies
--
Great minds discuss ideas.
Average minds discuss events.
Small minds discuss people.
John Potter
<Attila...@lmf.ericsson.se> wrote:
> What I want to do is to _construct_ a new element inside the vector,
> using the other object (having other type) as input.
Ok, you want a general insertion, not push_back.
raw_storage_iterator uninitialized_insert (iterator);
Usage:
*v.uninitialized_insert(v.end()) = other_object;
That does not generalize well; so, maybe you want.
iterator uninitialized_insert (iterator, Other);
void uninitialized_insert (iterator, n, Other);
void uninitialized_insert (iterator, OtherIter, OtherIter)
There should, of course, also be placement_insert_iterators.
I wonder why the whole world is not screaming for this. Maybe there
really is no need? Try this.
struct B {
B () { cout << "B()/n"; }
B (B const&) { cout << "B(B)\n"; }
B& operator= (B const&) { cout << "B=\n"; }
};
struct A {
A () { cout << "A()/n"; }
A (A const&) { cout << "A(A)\n"; }
A (B const&) { cout << "A(B)\n"; }
A& operator= (A const&) { cout << "A=\n"; }
};
int main () {
vector<A> v;
v.reserve(2);
B b;
cout << "Push\n";
v.push_back(b);
cout << "Insert\n";
v.insert(v.end(), &b, &b + 1);
}
Output:
B()
Push
A(B)
A(A)
Insert
A(B)
I don't think that we need to add more to the language before we learn
how to use what is already there.
John
John
Maciej Sobczak
"Dave Harris" <bran...@cix.co.uk> wrote in message
news:memo.20020524...@brangdon.madasafish.com...
> Attila...@lmf.ericsson.se (Attila Feher) wrote (abridged):
> > What I want to do is to _construct_ a new element inside the vector,
> > using the other object (having other type) as input.
>
> Sounds reasonable to me. Like:
>
> template <typename T>
> class vector {
> public:
> template <typename U>
> iterator push_back( const U &u ) {
> void *p = grab_memory_for_a_new_T();
> new(p) T(u);
> return end()-1;
> }
> // ...
> };
I was thinking about something similar.
My first though was to have a method in the vector's interface that would
allocate memory for the next element and return the pointer (I deliberately
not use the term iterator here) to it. Something like:
pointer push_room()
{
void *p = grab_memory_for_a_new_T();
return p;
}
The idiomatic use would be something like:
vector<MyClass> v;
MyClass *p = v.push_room();
new (p) MyClass(/*put whatever you want here*/);
YES, I KNOW IT IS A PILE OF BULL,
becaue the exception safety is pulled outside the interface and the user is
likely to come up with a broken (with holes) vector if the constructor
fails.
But... We can push it back into the vector (pun intended) with this:
// draft only!
template<class Function>
void push_back_f(Function f)
{
void *p = grab_memory_for_a_new_T();
f(p);
}
with appropriate EH here and there so that the vector keeps its logical size
intact when the function f fails to construct the actual object in the chunk
of memory pointed to by p.
Here, the callback function (functor) is used to hide all the construction
magic. It is supposed to overload the
void operator()(pointer *);
method which either constructs the object using whatever technique it likes
(including placement new) or throws an exception, which will be propagated
outside the vector::push_back_f.
Attila - in your case the usage can look like this:
class MakeBigFromSmall
{
public:
MakeBigFromSmall(const SmallClass &s) : s_(s) {}
void operator()(BigClass *p)
{
new (p) BigClass(s_); // or whatever you wish
}
private:
SmallClass s_;
};
and later:
vector<BigClass> v;
SmallClass s = ...;
v.push_back_f(MakeBigFromSmall(s));
Attila - I hope you will not shout at me just because the functor is passed
by value? ;-)))))
Cheers,
--
Maciej Sobczak
http://www.maciejsobczak.com/
Francis Glassborow
Harris <bran...@cix.co.uk> writes
>I do have some concerns. If we have this templated pushed_back(), do we
>still need the normal one? There are some subtle issues to do with
>T::T(const U&) not being a copy constructor even when T and U are the same
>type. Ditto with assignment. I am also worried about the quality of error
>messages that are possible with doubled-up templates.
No there are not. Compiler generated copy ctor and copy assignment
ALWAYS beat an insatiation of a template and so a member template can
NEVER provide one of those.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Howard Hinnant
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <3ceea06c...@news.earthlink.net>, John Potter
<jpo...@falcon.lhup.edu> wrote:
I don't think you can depend on this behavior. Apparently your
implementation of vector::insert uses a raw placement new to construct
the new element. My implementation uses the allocator's construct
function to create the new element with the result being:
B()
Push
A(B)
A(A)
Insert
A(B)
A(A)
Is the vector required to use its allocator's construct function? Is
it required not to?
--
Howard Hinnant
Metrowerks
Dave Harris
> > I do have some concerns. If we have this templated pushed_back(),
> > do we still need the normal one? There are some subtle issues to
> > do with T::T(const U&) not being a copy constructor even when T
> > and U are the same type. Ditto with assignment. I am also
> > worried about the quality of error messages that are possible
> > with doubled-up templates.
>
> No there are not. Compiler generated copy ctor and copy assignment
> ALWAYS beat an insatiation of a template and so a member template can
> NEVER provide one of those.
Is that actually a problem here, though? I didn't think so but wasn't
sure. The "new(p) T(u)" is using a copy constructor rather than providing
one.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Raoul Gough
> > What I want to do is to _construct_ a new element inside the vector,
> > using the other object (having other type) as input.
>
> Sounds reasonable to me. Like:
>
> template <typename T>
> class vector {
> public:
> template <typename U>
> iterator push_back( const U &u ) {
> void *p = grab_memory_for_a_new_T();
> new(p) T(u);
> return end()-1;
> }
> // ...
> };
>
> (although real code would need allocators, exception safety etc). I think
> this would be a reasonable proposal for the next std library. I don't
> think we need support more than one argument, as other arguments can be
> packed into a U type.
This could be much improved by a generic function and constructor forwarding
syntax. For instance, overloading the ellipses parameter syntax could
produce this:
// in template class vector
void construct_push_back (...)
{
// allocate space for a new T* at p
new (p) T (...);
}
The idea is that construct_push_back generates a set of member functions
that matches exactly the overload set for T's constructors. OK, maybe best
not to reuse the same syntax for this purpose, but the idea would be the
same.
This would almost be very useful for the pImpl idiom, but you would
obviously need to know the set of functions that you are forwarding to, so
it would introduce a dependency on at least part of the implementation
again. OTOH, it might help with intrusive smart pointers, allowing a
wrapper's constructor to match automatically those of the contained object.
Actually, for something like std::pair, it would be necessary to introduce
named parameter list substitutions:
pair (__param_list a, __param_list b) : first (a), second (b) { }
Now that would be kind of neat, IMHO
Regards,
Raoul Gough.
Mary K. Kuhner
>In any case, such
>moveable-but-not-copyable objects can't currently be stored in standard
>containers without shared ownership; if the standard was modified to have
>the concept of move semantics, you could store them in the standard
>containers --- move them in; the container can then move them around
>internally without copying, when necessary (e.g. when reallocating a
>std::vector<>), and we could provide an interface for moving the elements
>out of the container (which would erase the contained elements).
One of the reasons auto_ptrs can't go into STL containers is that
the containers and algorithms are allowed to make copies as well
as just move elements around. The algorithm most famous for taking
advantage of this permission is sort: some implementations copy
a pivot value, or several of them. I think the algorithm family
including remove* and unique may also be problematic.
So unless you are also willing to revise the requirements on STL
containers, your move-semantic objects will be unsafe to put into
them, just like auto_ptrs.
Mary Kuhner mkku...@gs.washington.edu
Douglas Gilbert
Just to continue the swap theme, I have made a variant of
std::vector, called swap_vector that swaps elements when
resizing and adds methods to swap elements in and out of
the vector. This is worthwhile when:
- the contained type supports swap() and it is fast
compared to a copy ctor
- the default ctor of the contained type is cheap
Standard containers themselves meet these requirements.
This is further discussed at:
http://www.torque.net/sg/p/swap_vector.html
together with an implementation that extends STLport.
I'm working on a freestanding version.
Doug Gilbert
James Kanze
|> James Kanze wrote:
|> [SNIP]
|> > In order to push back something, you need something to push
|> > back. If it is a temporary object, this is NOT a cost of
|> > push_back.
|> Well, you miss the point. I do not want to push_back something!
|> It isn't my fault the function is named like this. There are
|> enough other things which are, so I do not take the blame for this
|> one. :-)))
It's true that the name is bad -- it should be named append, or
something like that.
Never the less, the defined semantics of the function are to append a
*copy* of the object to the end of the vector. Not the object itself,
but a copy.
The entire STL is designed around this idea -- we insert *copies* of
the object, and not actual objects, the containers contain *copies* of
the object, etc.
This does mean that using STL with objects that are expensive to copy
may be a little slow.
|> What I want to do is to _construct_ a new element inside the
|> vector, using the other object (having other type) as input.
What you want is to break the abstraction of std::vector. I
understand that you have a particular performance problem, and that it
can only be solved by breaking this abstraction.
Should all users of the STL have to pay for the fact that you have a
special problem?
|> > |> > There is no rule saying that additional features which you
|> > |> > use will be free:-).
|> > |> Yep. But I guess there is a rule saying that additional
|> > |> features should be implemented as optimum as possible (but
|> > |> not more :-), since otherwise how will it be possible ot
|> > |> leave room only for assembly?
|> > There is no rule concerning how optimal anything must be.
|> It is only me, or does anyone else get the feeling that you have
|> to be right? No offense meant. But _if_ the STL is designed with
|> _no_ performance in mind... well, then the STL should not be part
|> of C++. Since one of the major goals of C++ was performance.
We're talking at cross purposes. The STL (like every other piece of
software) was designed to solve a specific set of problems. The STL
was designed so that the solution of these problems can be implemented
efficiently (although the standard certainly doesn't require it --
efficiency is always a QoI).
An efficient implementation does not mean that any particular
functionality cannot be done more rapidly, perhaps by ignoring the
global aspects (such as the abstraction). Most programs I've written
contain functions that are only called once, but no one complains
about an unnecessary function call if the compiler doesn't inline
them.
An efficient implementation does not mean that special cases will be
handled particularly efficiently either. The efficiency of the STL
quite obviously depends on the efficiency of copying, for example.
|> > On the whole, the STL is designed with far too much attention to
|> > runtime; it can be implemented in a very efficient manner. But
|> > the STL is designed to handle values, and by definition, a value
|> > is copiable.
|> Yes. Value is copyable. _With_costs_. And _why_ would I
|> _create_ an _unneeded_ temporary and then _copy_ it to another
|> place? What does make this logical? IMHO nothing.
Then you don't understand the importance of abstraction.
|> > This fits in with C++ in general, where the basic types are
|> > values, and if you want reference semantics, you have to use
|> > pointers (which are, themselves, values).
|> I do not want reference semantics. I want a push_back, which is
|> able to "behave" and not force me to create a temporary object,
|> which I do not need and which - in fact - is not needed.
What you want is to break a layer of abstraction. Either std::vector
knows more than it should about your objects, or the client code knows
more than it should about the implementation of std::vector.
Sometimes, performance does require breaking abstraction. But such
optimizations should be seen as an evil necessity, and should
certainly not be made part of the standard.
|> > If you need something special, you have to write it yourself.
|> Are you serious that not wasting CPU and memory by creating an
|> absolutely unneeded temporary is "special"? So this is normal (in
|> your opinion):
|> char a[10];
|> a[0]=1;
|> The latter line creates a temporary char on the stack from the
|> number one, and then copies it into the array. This is the
|> normal?
That's the way every value oriented language I've seen has worked.
That's the way C works, for example.
Obviously, in the case of built-in types, the compiler knows a lot
more about the actual semantics, and may be able to optimize. IMHO, I
think it also reasonable for the compiler to "assume" that the copy
constructor copies. The standard explicitly allows this in certain
cases as well. I don't know if push_back is one of those cases, but I
would certainly accept the idea that it should be. In this case, the
compiler *could* optimize away the additional copy, the same as it
generally does with built-in types.
I'm not sure how good current compilers really are with this. (I'm
not even sure whether the special rules in the standard can be applied
here, although I think they can.)
[...]
|> > The STL (and most of C++) is based on value semantics. Value
|> > semantics suppose a relatively cheap copy, at least in general.
|> What? Sorry I guess I do not get this. You mean that STL has
|> been created for integers and not larger?
One part of the STL design is that it behave "efficiently" with
built-in types -- that certain operations on built-in types be, for
all practical purposes, as fast as possible. Thus, the difference
between operator[] on std::vector<int> and int[] should be minimum.
(I'm not saying I agree with this, and IMHO, std::vector<>::operator[]
should do bounds checking. But I believe that this is the argument.)
One of the characteristics of built-in types is that they are cheap to
copy. The STL exploits this characteristing in certain cases.
|> > |> > It is important to understand the philosophy behind the
|> > |> > STL. It is value oriented. This means that it considers
|> > |> > the elements in the containers to be values, to be copied
|> > |> > at will.
|> > |> Great. This still does not answer the original question:
|> > |> why should I pay for a temporary value, when I do not need
|> > |> it and there is a way to avoid it?
|> > There is no way to avoid it. You must pass something to
|> > push_back.
|> Yes. Since I have just tweaked/hacked my copy of the STL to avoid
|> the unneeded temporary completely by making push_back (and some
|> more internals) a member template I hereby announce that there is
|> a way. I just do not get it yet why isn't it applied in the STL.
Doubtlessly because it was not felt to be necessary to solve the
problems the STL was designed to solve.
[...]
|> > |> Wow. So basically you say: if your system involves
|> > |> multithreading and decently large enough objects, please
|> > |> revert to writing your own containers, because we have only
|> > |> planned STL to be used with integers???
|> > Well, that is at least partially true.
|> Here I give up. Sorry, but I cannot seriously believe that you
|> meant this. I am now sure you are just kidding.
As I said, at least *partially* true. The STL was designed with value
semantics in mind. Value semantics imply cheap copy. The built-in
types have value semantics. (Note that in C/C++, pointers themselves
have value semantics.)
|> > C++ definitly uses value semantics by default -- with the
|> > built-in types, for example. And the STL was designed to be
|> > efficient with the built-in types. It is also efficient with
|> > user defined types, in so far as they more or less conform to
|> > the basic value semantics of the built-in types.
|> Sorry, could not resist: Aha, so basically user defined types,
|> which are not larger than an integer.
User defined types which have an efficient copy. How efficient
depends on what your requirements are.
|> And - according to your above statements - this is supposed to be
|> the "normal case". Any user defined type larger than an integer
|> or double is "special case". I am getting sarcastic. :-(( Is it
|> 1st of Arpil on Tatuin and just I do not know it? Please, others,
|> help me out here. I must have misunderstood something very basic
|> here. I always believed that any useful suer defined data type
|> will be significantly larger than an integer and that the STL was
|> there to server 99% of the C++ programmers and not 1% only, who
|> uses only built-ins.
I think you've missed the point that requirements vary. Something
like "struct Point { double x, y, z ; }" will have sufficiently
efficient value semantics for most uses as well, and it is certainly
larger than a double.
If I look at my own work, I find that most classes can be divided into
two large categories: values and entity objects. The values are
usually relatively small, and have cheap copy; the entity objects,
while often very big, have identity, and cannot be copied.
There are, of course, other categories. The most obvious is
containers, which (following the STL example) I generally make
copiable, but which can, potentially, be very big. And whatever you
(or I, for that matter) think of it, the STL does not make any effort
to optimize containers of containers -- even something simple like:
typedef std::vector< double > Vector1D ;
typedef std::vector< Vector1D> > Vector2D ;
Vector2D a( 1000, Vector1D( 1000 ) ) ;
is going to involve a lot of copying -- in this case, of uninitialized
objects.
What do you want me to say? Making this as optimal as possible was
obviously not one of the STL design goals. You talk about one
particular case -- you need a special form for push_back. But what
about all of the "unnecessary" copies in the above.
Copying pervades the STL. If you are serious about your proposal,
then you have to address everybody's issues, not just your own. And
find ways of suppressing *all* of the unnecessary copying. Why should
the standard add a special feature to solve your case, and not do
something to solve the above? (Note that both cases can also be
solved by good optimization on the part of the compiler. No
additional special language is needed.)
|> > This is a fundamental design decision of C++.
|> Well, I have read Design and Evolution of C++ and I am sure I
|> would remember if this would have been mentioned.
Perhaps some things are so obvious that it wasn't felt necessary to
mention them. C (and C++) use value semantics for all of the built-in
types. I don't think that this design decision was mentionned in the
DEC++ either, but it is evident to anyone who knows the language.
|> First of all I believe that you are mixing here C++ (the language,
|> which _really_ deals with values mostly) and the STL.
Well, my impression was that the STL more or less tries to align
itself on the language. It certainly does use value semantics.
|> And I believe you have missed the whole point as well. I do not
|> care, if vector uses value/weight/volume or Value Addedd Tax
|> semantics. What I would like to see is that it does not create an
|> unneeded temporary, when I do push_back with a type, from which
|> the element type can be created.
I understand the point very well. You have a particular problem,
where the compiler you use is unable to optimize as efficiently as you
want, and as the language allows. You thus want to change the basic
ground rules of the standard library to solve your special problem.
|> > If you really cannot live with it, try another language.
|> No need to get deffensive. If I coul dnot live with C++ I would
|> not write here. But I believe that showing up attitude won't help
|> with the issue. If you love how the vector::push_back works, I am
|> happy for you.
Actually, I'm not that thrilled about the STL in general. There are a
lot of design decisions I would change (one iterator instead of two,
etc.). But I do believe that it is a coherent library -- everything
in the library is pretty much consistent with the ground rules that
were adopted.
One of those ground rules (and one I do agree with) is that the
containers have value semantics, and store *copies* of the object
which they own and manage.
|> Really. But then I guess you could live some room for those here,
|> who actually has some answers to my questions, for which I have
|> opened this thread (no offense meant again):
|> - why isn't/wasn't push_back templated, is there any gotcha there I am
|> not aware of
Because this is a very special solution to one person's particular
problem, and doesn't fit in with the library in general.
|> - is there any way to avoid creating a who-needs-that temporary
I offered several suggestions, including one which I actually used in
a similar case. But if you really need something very special, the
only way to get it is to write it yourself.
[...]
|> > |> Sorry, I cannot believe this can be true in such a powerful
|> > |> language as C++. I mean I can understand that noone has
|> > |> thought of it, that push_back may be too expensive with big
|> > |> classes etc.
|> > They've thought of it. I imagine that the general consensus is
|> > that normally, things like COW and delayed initialization are
|> > sufficient, and that it isn't worth breaking the abstraction for
|> > the rare cases where they are not.
|> COW? I may be well not aware of how things evolved in the last 3
|> months but before that there was a high consensus about COW being
|> The Worst Choice In Most Cases To Solve NonExisting Problems,
|> especially if used in MT environemt.
I have never seen anything even suggesting such a consensus. There is
a consensus that getting the particular semantics of std::string right
with CoW is difficult in an MT environment, but that is all. And part
of the consensus here is that the problem with the semantics of
std::string, and not CoW in itself.
|> > Even in your case, I find it difficult to believe that
|> > separating initialization from default construction couldn't
|> > provide a solution.
|> Well, I think you need to work on your imagination. :-)))
|> > From what you have said, I suspect that a default constructor
|> > probably doesn't even exist in the target class. So a simple
|> > solution would be to provide one, which does absolutely nothing
|> > -- it leaves the class data as raw memory. And provide an
|> > initialization function which does the same job as the normal
|> > constructor. By doing this, this particular problem is solved
|> > by writing:
|> > vectorOfBs.push_back( B() ) ;
|> > vectorOfBs.last().initialize( someA ) ;
|> Well, if I hadn't had to read through all those lines repeating
|> "value sematics", I would be happy to see this. I have done this
|> (BTW ther _was_ a default constructor). but. But. _But_.
|> _BUT_, this is a _hack_.
At least we agree about one thing. It *is* a hack. It shouldn't be
resorted to unless performance absolutely requires it. Most
optimizations are hacks. We avoid them. Unless we can't --
requirements are requirements, after all.
|> I create a crippled class, just because something, which could be
|> solved by having a templated push_back isn't there. Not to
|> mention, that for everyones laugh the class, I have inside the
|> vector has _vectors_ in it, so I just _cannot_ make its creation
|> absolutely free.
Creating a vector with the default constructor should be very cheap.
Copying an empty vector should be very cheap.
This is exactly what I did. My class contained one, very large
vector. So I was careful not to initialize it until it had come to
rest in its final place.
Obviously, I would have preferred to do everything nice and cleanly.
But performance constraints didn't allow it. So I did what I had to.
(And I commented very carefully what I did, and why.)
Note that even the contained vectors had an "unnecessary copy"
problem. The information necessary to contain the elements wasn't
available in order, so I had to create the entire vector (around
100,000 elements), and then use assignment to give the elements the
correct value. Why should the standard solve your problem, with
push_back, and not do anything about mine?
[...]
|> > In your case, if the vector is being accessed from other
|> > threads, you need a lock for every access -- any manipulation of
|> > the counter is guarded by that lock.
|> Which lock is created and destroyed on a way, that it may very
|> easily stop all other threads and render a 4 CPU machine to a
|> 0.7CPU one, as it already has happened when way too many (COW)
|> std::strings has been created and destroyed. This isn't the way
|> to go. Why would I overcomplicate and slow down my code?
I'm not sure I understand here. There are only three possibilities:
you use the lock, no matter what it costs; you only access the vector
from one thread; or your code is broken. No matter what you actually
put in the vector, or how you manage it.
--
James Kanze mailto:ka...@gabi-soft.de
Need real expertise in C++, Java, OO design
I am available, see my CV at www.gabi-soft.de
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)69 63198627
James Kanze
|> On 24 May 2002 09:35:30 -0400, James Kanze <ka...@alex.gabi-soft.de> wrote:
|> > "Andrei Alexandrescu" <andre...@hotmail.com> writes:
|> [···]
|> > |> I'm talking about a third operation, move, which turns out
|> > |> to be as fundamental as copying. There are past articles
|> > |> here and on boost by Hinnant, Abrahams and others on the
|> > |> subject.
|> > Move is really just a minor variation on copy; the default
|> > semantics of move are copy-destroy. In this sense, it fits
|> > perfectly into a value semantics mould. Abstractly, it doesn't
|> > even introduce a new concept. From a design point of view, it
|> > is an optimization.
|> It's not just optimization. It's a "new concept" in the sense that
|> Copy-Destroy often cannot be guaranteed not to fail (because of
|> the copy), while Move generally can be. Furthermore, there are
|> types for which Copy doesn't make sense (e.g. auto_ptr) while Move
|> does.
I'm not sure I'd say it's really a new concept, but I understand.
Move can offer guarantees (like throw()) which might not be present in
copy-destroy. (Is a specialized swap a new concept because it can
offer these guarantees, when the standard swap can't?)
I still can't see it as a radically different way of thinking of
objects.
--
James Kanze mailto:ka...@gabi-soft.de
Need real expertise in C++, Java, OO design
I am available, see my CV at www.gabi-soft.de
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)69 63198627
Francis Glassborow
<mkku...@kingman.genetics.washington.edu> writes
>So unless you are also willing to revise the requirements on STL
>containers, your move-semantic objects will be unsafe to put into
>them, just like auto_ptrs.
No, I think you are mistaken. The problem with auto_ptr is that it
hijacks the copy ctor to provide move semantics. If we have a genuine
move ctor then algorithms can select move or copy as appropriate. There
would still need to be quite a lot of copying, but less than we have
now.
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Anthony Williams
news:acrtj9$1ou4$1...@nntp6.u.washington.edu...
> Anthony Williams <ant...@nortelnetworks.com> wrote:
> >In any case, such
> >moveable-but-not-copyable objects can't currently be stored in standard
> >containers without shared ownership; if the standard was modified to have
> >the concept of move semantics, you could store them in the standard
> >containers --- move them in; the container can then move them around
> >internally without copying, when necessary (e.g. when reallocating a
> >std::vector<>), and we could provide an interface for moving the elements
> >out of the container (which would erase the contained elements).
>
> One of the reasons auto_ptrs can't go into STL containers is that
> the containers and algorithms are allowed to make copies as well
> as just move elements around. The algorithm most famous for taking
> advantage of this permission is sort: some implementations copy
> a pivot value, or several of them. I think the algorithm family
> including remove* and unique may also be problematic.
>
> So unless you are also willing to revise the requirements on STL
> containers, your move-semantic objects will be unsafe to put into
> them, just like auto_ptrs.
Since move-semantic objects in general would be a change, it would be
necessary to define how they relate to the existing standard library. If we
allowed containers of such objects, then we would have to ensure that the
algorithms worked with iterators into such containers, or were documented as
not working.
Yes, the implementation of e.g. std::sort might have to be rewritten if the
elements to be sorted had move semantics, but I don't think that should pose
a problem for the specification, as the elements need to be moved anyway
(how else can you sort them?) --- quicksort is "in place", and for mergesort
each element needs to be moved into the temporary storage, and then moved
into the correct location in the array during merging. The only issue is the
pivot and the comparison function; we must be sure to use references not
"copies". Obviously, other sorting algorithms might need care.
The xxx_copy algorithms obviously won't work, but remove shouldn't be a
problem. Basically the _implementation_ of every algorithm might need to be
rethought, but there shouldn't be much change on the requirements --- if an
algorithm currently (including DRs) requires an accessible copy-constructor
or assignment operator, then it won't work with move-semantic objects,
otherwise it should work if correctly written.
Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optical Components Ltd
The opinions expressed in this message are not necessarily those of my
employer
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Attila Feher
[SNIP]
> |> This is a misunderstanding. Move semantics do not eliminate copy
> |> semantics.
>
> Agreed. I was not considering move semantics. I don't know if it
> would help him or not; depending on how the class is organized, moving
> it could be just as expensive as copying it.
Well, mostly how you could imagine is one big junk of data inside one
kinda class, with virtually no types the same, and another, the target
"format" where the same data is there - just called another name. And I
cannot perfectly quote, but my goal is to put the "Roses" from one
vector to another, just with another name - but without the need for a
"temporary Rose with another name" in between.
To Andrei: Thanx for the vector "swap-to-move trick", I have actually
just proposed this as a solution for places where it can be used a day
before. And the "same game" can be played with any std stuff, like
string for example.
So what I came up with is introducing "move" (not yet using std::swap
specializations) for data stored as strictly owned pointers - where the
types are our own and the swap trick where they are in vector. Where we
need to "convert" I came up with the not-so-nice hack (also proposed
here the next day) of creating a (nearly, since I cannot skip
initialization of members with do-nothing default constructor, resize
the target vector to the required size and fill those elements one by
one. This is - of course - an ugly hack and renders those classes
"special", since their default constructor does not really do it's job.
This is especially ugly since there are enums involved... That was the
reason why I was asking my original question: does making push_back (and
the similar) a member template involve some (to me) unknown gotchas
(pitfalls, whatever) so that it wasn't (they weren't) made to be one
(member template(s))?
Attila
Grzegorz Jakacki
Could somebody explain, what is meant by "move semantics" for C++? It
seems to me that two concepts are mixed in the messages posted so far,
e.g.:
(1) "Andrei Alexandrescu" <andre...@hotmail.com> writes:
> moving constructors
(2) "Anthony Williams"<ant...@nortelnetworks.com> writes:
> move-semantic objects
As I understand (1) means introducing new kind of unary constructor
(and/or operator=), which is allowed to trash the source object, while
(2) means introducing a type modifier, which makes the copy
constructor of the type behave like moving constructor in the sense of
(1) (linear type?).
Clarification appreciated.
Regards
Grzegorz
###################################################################
# Grzegorz Jakacki China IC Design Center #
# Senior Engineer, CAD Dept. 1 Gaojiayuan, Chaoyang #
# tel. +86-10-64365577 x2009 Beijing 100015, China #
###################################################################
Attila Feher
>
> Attila Feher wrote:
> > James Kanze wrote:
> > [SNIP]
> >
> >>Value orientation implies copying.
> >
> >
> > Well, that is what I want. Copying. ONE copying and not TWO copying.
>
> I think not. You want a conversion, not a copy. You can
> only copy from type X to type X.
Call it conversion. I call it copy. The fact that the copier machine
prints my stuff on green paper (which was originally on white) is still
a copy for me. No conversion takes place in the original sense of the
word, like from Fahreheit to Celsius etc.
> >>I don't know of any language which would solve his problem -- he
> >>doesn't want a copy, and he doesn't want to dynamically allocate the
> >>object.
> >
> > Stop the train! I _do_ want a copy! I want a copy of my class A object
> > as class B object!
>
> That's not a copy then. It produces an object which is *not*
> equivalent to the original, i.e., not a copy.
UhOh. So if you copy a file from one directory to the other, and the
other directory is actually on a HDD with different block size, so your
file now takes up a bit more space than on the original disk... then it
isn't a copy anymore, because it isn't equivalent? What is equivalent?
My _copy_ does not leave out, change, add or convert _any_ of the data
elements from object type A to type B. It copies. Member names
differ. Maybe some containers used inside to store the data differ.
Big deal! That is _implementation_detail_. The data inside is the
same! So I believe that since (thinking about real data structures,
with dynamic allocations etc.) copies will never be bitwise the same -
what I feel as your definition of equivalent - according to you, no
copy exists of certain data structures. Since _even_ if they _are_
bit-by-bit the same, their _identity_ (ie: address) will not be the
same, so they will not be copies?
How about calling std::copy to insert elements of a vector into a list?
I call a function called copy. Will the list be a copy of the vector?
Nope? But its elements _are_! Consider my situation as such. I
believe that in my case _copy_ is a better word to describe what I need
to do, since I do not _change_ anything in the data. The two copies (in
different format) of the data set are _identical_ or _equivalent_, since
they do contain the same data. My conversion from A->B->A will give
back A unchanged.
> > ONE copy. And how could you say that I do not want
> > to dynamically allocate? It is in a vector! It is _already_
> > dynamically allocated!
>
> Not as an individual object.
Since I do _not_ need them as individual objects! It gives me already
enough headache that as vector, they are dynamically allocated (thx to
no portable align).
> > And it is applicable here. Do one and only one copy. From a class A
> > object I copy the data to a class B object.
>
> And, as I say almost as many times as you claim that this is
> making a copy, it is not.
And as many times as you try to call something a conversion, which does
not _change_ the data it is not. Take a glass of vine. Pour it into a
jug. Is the vine the same? Or it isn't, because it is contained in
something else???
> > What I have just told: templated push_back. I believe I have already
> > mentioned this in my opening post.
>
> It seems like a reasonable thing to have put into the container
> requirements, but I don't know if it's so easy to retro-fit. Would
> it have any effect other than omitting a (real) copying operation?
Well, it is really nice you to ask that. However this is one of the
questions I have asked as the OP, so I would be very surprised if
suddenly I could answer it. :-))) I suspect there _may_ be some
drawbacks of it I do not know.
Attila
James Kanze
|> James Dennett wrote:
|> > Attila Feher wrote:
|> > > James Kanze wrote:
|> > > [SNIP]
|> > >>Value orientation implies copying.
|> > > Well, that is what I want. Copying. ONE copying and not TWO
|> > > copying.
|> > I think not. You want a conversion, not a copy. You can only
|> > copy from type X to type X.
|> Call it conversion. I call it copy. The fact that the copier
|> machine prints my stuff on green paper (which was originally on
|> white) is still a copy for me. No conversion takes place in the
|> original sense of the word, like from Fahreheit to Celsius etc.
The C++ standard calls it conversion. Within the C++ language, the
verb "to copy" has a very precise meaning.
|> > >>I don't know of any language which would solve his problem --
|> > >>he doesn't want a copy, and he doesn't want to dynamically
|> > >>allocate the object.
|> > > Stop the train! I _do_ want a copy! I want a copy of my
|> > > class A object as class B object!
|> > That's not a copy then. It produces an object which is *not*
|> > equivalent to the original, i.e., not a copy.
|> UhOh. So if you copy a file from one directory to the other, and
|> the other directory is actually on a HDD with different block
|> size, so your file now takes up a bit more space than on the
|> original disk... then it isn't a copy anymore, because it isn't
|> equivalent? What is equivalent?
Generally, two things are equivalent if they have the same type and
compare equal. If the result of your copy, above, is a file, and the
resulting file "compares equal" with the original, it is a copy.
Within the context of C++, the definition is more precise, and
formally, the results don't even have to compare equal -- consider
what happens when "copying" std::auto_ptr.
--
James Kanze mailto:ka...@gabi-soft.de
Need real expertise in C++, Java, OO design
I am available, see my CV at www.gabi-soft.de
Ziegelhttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)69 63198627
Attila Feher
[SNIP]
> But... We can push it back into the vector (pun intended) with this:
>
> // draft only!
> template<class Function>
> void push_back_f(Function f)
> {
>
> void *p = grab_memory_for_a_new_T();
> f(p);
> }
This, does (to my understanding) exactly the same thing what an
overloaded member template push_back could provide, except that here we
need to create a functor or function to create the job of the
constructor and somehow, with deep wizardry pass/store the arguments
need by the constructor into this function/functor. Which will be
eventually copied, so we end up with the very similar problem as with
current push back, except that we have to work more.
[SNIP]
> Attila - I hope you will not shout at me just because the functor is passed
> by value? ;-)))))
Not shout but frown. As I have mentioned, in my case both classes are
_huge_ and this functor (since it takes only the void* argument) should
store inside the argument needed for the replacement new (constructor).
So we end up the same way, only here we might copy the source class.
Attila
John Potter
wrote:
> The C++ standard calls it conversion. Within the C++ language, the
> verb "to copy" has a very precise meaning.
And, the C++ standard says that a copy constructor is a conversion
constructor. This is all word game nonsense.
struct B { };
struct A { A(); A(B const&); }
void f () {
B b;
A a(b); // Uses A(B), a single conversion
vector<A> v;
v.reserve(2);
v.push_back(a); // Uses A(A), a single conversion
v.push_back(b); // Uses A(A(B)), two conversions
The original question is why can't push_back just do A(B)? Generalize
it to all insertions in all containers.
John
Attila Feher
[SNIP]
> verb "to copy" has a very precise meaning.
I believe it does. Like in phrases: copy constructor. In my humble
dictionary, since std::copy from a vector to a list does _not_ copy the
vector and it is still called copy... Anyways I was not speaking C++, I
was speaking English. But I believe we can continue arguing about if we
call it copy or convert, but I personally think this is not the issue
here. The issue is what I have posted in my OP. Do you have a
solution/suggestion for the problem or an answer to the question
(concrete answer) if there are any pitfalls or known gotchas why the
push_back (and the related) functions are not templated and are not
overloaded? I kindly ask you to please concentrate on these issues,
since I have asked for help on these. Arguing about usage of a term or
whether I am sane or not if I want a push_back without having an extra
temporary created and destroyed isn't much of a help.
> Generally, two things are equivalent if they have the same type and
> compare equal.
Well, what about _not_ having the same type but having the same _data_
inside and comparing equal? (Without ignoring anything in the
comparison). Is the vine in a glass equal to the same part of the vine
when it was in the bottle?
> If the result of your copy, above, is a file, and the resulting file
> "compares equal" with the original, it is a copy.
Well, I can create a perfectly legal comparison betwen my 2 types, since
they _do_ have _all_ the same data but inside different structure and
with different names.
> Within the context of C++, the definition is more precise, and
> formally, the results don't even have to compare equal -- consider
> what happens when "copying" std::auto_ptr.
Yep. That is _definitely_ not a copy. That is _move_.
Attila
Howard Hinnant
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <c8c98175.02052...@posting.google.com>, Grzegorz
Jakacki <jak...@cidc.com.cn> wrote:
| Hi,
|
| Could somebody explain, what is meant by "move semantics" for C++? It
| seems to me that two concepts are mixed in the messages posted so far,
| e.g.:
|
| (1) "Andrei Alexandrescu" <andre...@hotmail.com> writes:
| > moving constructors
|
| (2) "Anthony Williams"<ant...@nortelnetworks.com> writes:
| > move-semantic objects
|
| As I understand (1) means introducing new kind of unary constructor
| (and/or operator=), which is allowed to trash the source object, while
| (2) means introducing a type modifier, which makes the copy
| constructor of the type behave like moving constructor in the sense of
| (1) (linear type?).
|
| Clarification appreciated.
"Move semantics" does not really have a precise meaning in C++. Today
it probably means slightly different things to different people. And it
does not exist in C++ today except in relatively primitive ways. We
hope that a future C++ might nail down move semantics more precisely and
make it generally useful to a wider range of objects.
In a nutshell, move semantics refers to transferring value / resorces
from one object to another, with little regard for what happens to the
source object. Syntax for how to do this does not yet exist, except for
a few special cases:
1. auto_ptr copy: Looks like a copy syntatically, but it is a move.
2. swap for std::containers. This may be overkill for move since both
objects are both source and destination.
3. list::splice: Transfers node ownership from one list to another.
Very move-like. The syntax is obviously not generally applicable to
other objects though.
If we had a standardized syntax for move (like we do for copy), then
generic code could choose to move objects instead of copy them. This
might produce signicant performance optimizations as it is often cheaper
to move than to copy.
--
Howard Hinnant
Metrowerks
Mary K. Kuhner
>In article <acrtj9$1ou4$1...@nntp6.u.washington.edu>, Mary K. Kuhner
><mkku...@kingman.genetics.washington.edu> writes
>>So unless you are also willing to revise the requirements on STL
>>containers, your move-semantic objects will be unsafe to put into
>>them, just like auto_ptrs.
>No, I think you are mistaken. The problem with auto_ptr is that it
>hijacks the copy ctor to provide move semantics. If we have a genuine
>move ctor then algorithms can select move or copy as appropriate.
You're right. If you had defined move construction *and* copy
construction, and the algorithms were written to use the right one, no
problem. I was somehow imagining an object with only move
semantics--like an auto_ptr--but this would be of limited usefulness
anyway.
What syntax would one use to invoke move construction as opposed to copy
construction?
Mary Kuhner mkku...@gs.washington.edu
Maciej Sobczak
"Attila Feher" <Attila...@lmf.ericsson.se> wrote in message
news:3CF35406...@lmf.ericsson.se...
> > // draft only!
> > template<class Function>
> > void push_back_f(Function f)
> > {
> >
> > void *p = grab_memory_for_a_new_T();
> > f(p);
> > }
>
> This, does (to my understanding) exactly the same thing what an
> overloaded member template push_back could provide,
If fact, it does more. You can write your functor to do something
different than just call the placement new. Depending on your needs, it
can be even some sequence of constructor followed by init(...) or
something. Also, the number of arguments that the constructor can take
is not an issue here. I mean - vector does not care, you have full
freedom inside the functor. You cannot achieve this genericity with
simple overload.
> except that here we
> need to create a functor or function to create the job of the
> constructor and somehow, with deep wizardry pass/store the arguments
> need by the constructor into this function/functor. Which will be
> eventually copied, so we end up with the very similar problem as with
> current push back
Yawn.
References are cheap enough?
>, except that we have to work more.
Assuming that most of the time you need to call B's constructor with one
parameter of type A, here you have:
template <class A, class B>
class MakeBFromA
{
public:
MakeBFromA(const A &a) : a_(a) {}
void operator()(void *p)
{
new (p) B(a_);
}
private:
const A &a_;
};
and later you do not have to work more than:
vector<B> v;
A a;
v.push_back_f(MakeBFromA<A,B>(a));
The temporary is really avoided here. And the functor is as cheap as one
reference.
> So we end up the same way, only here we might copy the source class.
References, if you wish.
Cheers,
--
Maciej Sobczak
http://www.maciejsobczak.com/
Attila Feher
>
> On 24 May 2002 12:40:20 -0400, Attila Feher
> <Attila...@lmf.ericsson.se> wrote:
> I don't think that we need to add more to the language before we learn
> how to use what is already there.
OK. Point taken. Now please let me see your rain-dance with a 2
arguments constructor and insert! How will that work?
Attila
Attila Feher
[SNIP]
> I don't think you can depend on this behavior. Apparently your
> implementation of vector::insert uses a raw placement new to construct
> the new element. My implementation uses the allocator's construct
> function to create the new element with the result being:
>
> B()
> Push
> A(B)
> A(A)
> Insert
> A(B)
> A(A)
Thanx! That would have been my second post, saying that I believe that
the observed behavio[u]r is system dependent and I have the feeling it
is non-standard. I mean I have this feeling after looking into the
implementation I have, which heavily uses the allocator everywhere. I
actually had no time to browse the standard (there are zillion other
things to worry about). Although I wanted to check this, esp. since I
have been - sort of - offended by saying that I do not know the language
(which is true, but I don't like to hear it :-), so if any language
guru/lawyer could drop into this (I still get lost in the standard text
way too easily) and confirm, that would be very much appreciated.
> Is the vector required to use its allocator's construct function?
> Is it required not to?
I guess it is required, otherwise why would you have the allocator in
the first place. If it is not explicitly mentioned in the standard I
believe that it is time for a defect-report...
Attila
Peter Dimov
> In article <acrtj9$1ou4$1...@nntp6.u.washington.edu>, Mary K. Kuhner
> <mkku...@kingman.genetics.washington.edu> writes
> >So unless you are also willing to revise the requirements on STL
> >containers, your move-semantic objects will be unsafe to put into
> >them, just like auto_ptrs.
>
> No, I think you are mistaken. The problem with auto_ptr is that it
> hijacks the copy ctor to provide move semantics. If we have a genuine
> move ctor then algorithms can select move or copy as appropriate. There
> would still need to be quite a lot of copying, but less than we have
> now.
It's a bit more complicated. Classes that can be copied are fine, move
is merely an optimization there. The other category contains classes
that can be moved but cannot be copied - like auto_ptr. As auto_ptr
has demonstrated, 'pure' move is pretty limited if you don't hijack
some form of copy constructor - you can't return such classes from
functions otherwise.
Howard Hinnant
Dimov <pdi...@mmltd.net> wrote:
| As auto_ptr
| has demonstrated, 'pure' move is pretty limited if you don't hijack
| some form of copy constructor - you can't return such classes from
| functions otherwise.
You could if 12.8/15 was modified to prefer (but not require) move
construction over copy construction when copying an auto-storage local
to the stack. But of course eliding the accessible move/copy should
still be allowed (and preferred!).
--
Howard Hinnant
Metrowerks
John Potter
<Attila...@lmf.ericsson.se> wrote:
> Howard Hinnant wrote:
> > Is the vector required to use its allocator's construct function?
> > Is it required not to?
> I guess it is required, otherwise why would you have the allocator in
> the first place. If it is not explicitly mentioned in the standard I
> believe that it is time for a defect-report...
Allocator::construct(p, v)
is required to be equivalent to
new ((void*)p) T(v)
and its second parameter is required to be T const&.
If the standard requires use of this function, all attempts to solve
your problem will fail. The simple case for vector.
template <class U>
void push_back (U const& u);
Required implementation would include
alloc.construct(p, u);
The conversion which was saved on the call of push_back must be
introduced in the implementation. Exactly what happened in Howard's
implementation.
To even approach getting what you seem to want, the implementation must
be forbidden to use the construct member. Think about list and the fact
that the allocator constructs nodes not Ts. How will you expose the raw
part of the node for the T and use the construct member?
John
John Potter
<Attila...@lmf.ericsson.se> wrote:
> John Potter wrote:
> > On 24 May 2002 12:40:20 -0400, Attila Feher
> > <Attila...@lmf.ericsson.se> wrote:
> > I don't think that we need to add more to the language before we learn
> > how to use what is already there.
> OK. Point taken. Now please let me see your rain-dance with a 2
> arguments constructor and insert! How will that work?
It will not. I only considered the stated problem which contained a
conversion (one parameter).
To be honest, I find the standard much easier to read than your posts.
Could you post the desired increases to the vector interface in the
form of code (member declarations) with prose for the semantics?
John
Attila Feher
>
> On 29 May 2002 06:21:22 -0400, Attila Feher
> <Attila...@lmf.ericsson.se> wrote:
>
> > John Potter wrote:
>
> > > On 24 May 2002 12:40:20 -0400, Attila Feher
> > > <Attila...@lmf.ericsson.se> wrote:
>
> > > I don't think that we need to add more to the language before we learn
> > > how to use what is already there.
>
> > OK. Point taken. Now please let me see your rain-dance with a 2
> > arguments constructor and insert! How will that work?
>
> It will not. I only considered the stated problem which contained a
> conversion (one parameter).
And suggested a solution which is not portable, yes. But if you
carefully read my first post, you will see:
8<---
I know, that this little thing leads faaar away, since one may ask: how
about multiply argument constructors. Why don't we support overloaded
push_backs, where actually I can give more than one argument to the
constructor... Well, that part starts to be tricky, since where do we
stop? At 60 arguments? etc.
--->8
So the question is there.
> To be honest, I find the standard much easier to read than your posts.
I am very happy to hear that. Then I look professional.
> Could you post the desired increases to the vector interface in the
> form of code (member declarations) with prose for the semantics?
I have made a post, which has asked questions. I did not propose
anything. I have asked: what drawbacks are there, why isn't templated
puch_back already there, are there any hidden gotchas, pitfalls,
whatever one can call them - which the comitee was aware of when not
adding this kind of things (and forbiding their addition by making
push_back a non-member) _or_ it was just never-ever considered.
But to simply tell it: I want the vector (and all other containers) to
be able to do construction of an element _directy_ using one argument
constructors, without a temporary copy.
And I was thinking that the same could be done for multiply arguments
(wherever applicable), but that (to be able to make a nice solution,
supporting _all_ possible number of arguments) would need some sort of
"delegating template syntax", which leads faar again. Delegating
template syntax would enable a template to receive any number of
arguments and pass it on to another template _or_ even a simple function
for that matter, if that hits in.
But that variable argument template thing leads faaar, because if we
want to do it right, we would need to introduce some sort of typelist
support into langauge and compile-time-programming support..., same for
classes... so if I wanted to dump my class I could just create a member
called dump, and iterate through my members (compile time)... But as I
have said: that leads too far away.
Attila
Attila Feher
>
> On 29 May 2002 06:37:25 -0400, Attila Feher
> <Attila...@lmf.ericsson.se> wrote:
>
> > Howard Hinnant wrote:
>
> > > Is the vector required to use its allocator's construct function?
> > > Is it required not to?
>
> > I guess it is required, otherwise why would you have the allocator in
> > the first place. If it is not explicitly mentioned in the standard I
> > believe that it is time for a defect-report...
>
> Allocator::construct(p, v)
>
> is required to be equivalent to
>
> new ((void*)p) T(v)
>
> and its second parameter is required to be T const&.
>
> If the standard requires use of this function, all attempts to solve
> your problem will fail. The simple case for vector.
>
> template <class U>
> void push_back (U const& u);
>
> Required implementation would include
>
> alloc.construct(p, u);
>
> The conversion which was saved on the call of push_back must be
> introduced in the implementation. Exactly what happened in Howard's
> implementation.
That was the reason why I have made the construct to be a template as
well:
template <class U>
void construct(T* p, U v) {
new ((void *)p) T(v);
}
The signature may no tbee good, but I believe that is the idea.
> To even approach getting what you seem to want, the implementation must
> be forbidden to use the construct member. Think about list and the fact
> that the allocator constructs nodes not Ts. How will you expose the raw
> part of the node for the T and use the construct member?
Next time please ask for something complex. :-))) This is too easy:
Solution: templated constructor for the node
Takes all needed arguments for the node itself _plus_ the one for the
type T construction, but it isn't a T type, but any type. Code bloat
may occur from repeated addition of the same code filling all the other
members, which may be tolerated _or_ factored out into a private __init
function. Either way has pros and cons. The first way may bloat code,
but will not do it _if_ only the type T is used and if the rest of the
construction is not so simple, that the compiler can sctually figure out
some jumping-around-optimization. The second way will always pay for an
additional function call... except if it will be auto-inlined... in
which case we are back to square one. Not to mention that with
node-members with non-do-nothing constructors the second approach will
cost an unneeded default construction. So I would stay with the first
one and pray and push compiler vendor (if needed) to optimize the bloat
away.
Attila
John E. Potter
On Sat, 25 May 2002, Howard Hinnant wrote:
> In article <3ceea06c...@news.earthlink.net>, John Potter
> <jpo...@falcon.lhup.edu> wrote:
>
> | struct B {
> | B () { cout << "B()/n"; }
> | B (B const&) { cout << "B(B)\n"; }
> | B& operator= (B const&) { cout << "B=B\n"; }
> | };
> | struct A {
> | A () { cout << "A()/n"; }
> | A (A const&) { cout << "A(A)\n"; }
> | A (B const&) { cout << "A(B)\n"; }
> | A& operator= (A const&) { cout << "A=A\n"; }
A& operator= (B const&) { cout << "A=B\n"; }
> | };
> | int main () {
> | vector<A> v;
> | v.reserve(2);
> | B b;
> | cout << "Push\n";
> | v.push_back(b);
> | cout << "Insert\n";
> | v.insert(v.end(), &b, &b + 1);
> | }
> | Output:
> | B()
> | Push
> | A(B)
> | A(A)
> | Insert
> | A(B)
> | I don't think that we need to add more to the language before we
> | learn how to use what is already there.
> I don't think you can depend on this behavior.
I guess not.
> Apparently your
> implementation of vector::insert uses a raw placement new to construct
> the new element.
Indirectly via uninitialized_copy which seems like the logical thing to
do.
> My implementation uses the allocator's construct
> function to create the new element with the result being:
> B()
> Push
> A(B)
> A(A)
> Insert
> A(B)
> A(A)
> Is the vector required to use its allocator's construct function?
Not that I can find.
> Is it required not to?
Not that I can find.
Alloc.construct(p, val) is new ((void*)p) T(val). Of course the
standard claims that this void function returns that. :) Using the
construct member serves no purpose other than forcing a T const&.
I guess it is QoI. Of course, your Q is low since it broke my hack. :)
Just for amusement, what happens here?
int main () {
vector<A> v;
v.reserve(3);
B b;
cout << "Push\n";
v.push_back(b);
cout << "Insert end\n";
v.insert(v.end(), &b, &b + 1);
cout << "Insert begin\n";
v.insert(v.begin(), &b, &b + 1);
}
I am guessing the the last one will use A=B and not create a temporary.
I find that a bit inconsistent. Of course, consistency is not required.
John
James Kanze
|> Francis Glassborow <fran...@robinton.demon.co.uk> wrote: >In
|> article <acrtj9$1ou4$1...@nntp6.u.washington.edu>, Mary K. Kuhner
|> ><mkku...@kingman.genetics.washington.edu> writes >>So unless you
|> are also willing to revise the requirements on STL >>containers,
|> your move-semantic objects will be unsafe to put >>into them, just
|> like auto_ptrs.
|> >No, I think you are mistaken. The problem with auto_ptr is that
|> >it hijacks the copy ctor to provide move semantics. If we have a
|> >genuine move ctor then algorithms can select move or copy as
|> >appropriate.
That's the easy part. The thing I'm wondering about is what happens
with regards to the source object. After a move, it logically isn't an
object any more, and calling a destructor on it would be undefined
behavior.
Or would it. Should the move constructor modify the source object so
that calling the destructor would be safe?
Or is it all the responsibility of the programmer -- it's his
responsibility to avoid calling the destructor. In which case, I can
imagine some pretty difficult to find bugs when someone accidentally
introduces a temporary into an expression using the move constructor.
|> You're right. If you had defined move construction *and* copy
|> construction, and the algorithms were written to use the right one,
|> no problem. I was somehow imagining an object with only move
|> semantics--like an auto_ptr--but this would be of limited usefulness
|> anyway.
Not necessarily.
|> What syntax would one use to invoke move construction as opposed to
|> copy construction?
What syntax would one use to define the move constructor? What syntax,
if any, should one use to inhibit destruction of the moved object?
Who knows?
--
James Kanze mailto:ka...@gabi-soft.de
Need real expertise in C++, Java, OO design?
I am available, see my CV at www.gabi-soft.de
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)69 63198627
Francis Glassborow
<mkku...@kingman.genetics.washington.edu> writes
>You're right. If you had defined move construction *and* copy
>construction, and the algorithms were written to use the right one, no
>problem. I was somehow imagining an object with only move
>semantics--like an auto_ptr--but this would be of limited usefulness
>anyway.
>
>What syntax would one use to invoke move construction as opposed to
>copy construction?
That is, of course, the crunch. We have two problems
1) how shall we identify a move ctor definition?
2) how shall we identify using one?
--
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Andrea Griffini
wrote:
>The C++ standard calls it conversion. Within the C++ language, the
>verb "to copy" has a very precise meaning.
Not really. Copy-constructible and Assignable refer
to the fuzzy concept of "equivalent object".
I think it's hard to give it any reasonable meaning
and I think it would be better to drop the need of
such a confuse and questionable concept.
In my opinion it would be better to state what
containers can do freely (i.e. using copy constructor, assignment and
may be std::swap between elements and between and element and a
temporary) without trying to describe what those operations *mean* for a
user defined class. Container treat those operations like for native
types and if this isn't right for a user defined class then this is just
a user problem.
This would for example rule out placing auto_ptr
in containers without getting stuck in cheap
philosophy and without the need of undefined
behaviour daemon summoning rite.
>Generally, two things are equivalent if they have the same type and
>compare equal.
What about classes that don't define equality or
any comparision operator ? Should be forbidden to
place them in containers only because is nonsense
to compare them ?
>If the result of your copy, above, is a file, and the resulting file
>"compares equal" with the original, it is a copy.
What is the meaning of those quotes ?
>Within the context of C++, the definition is more precise, and
>formally, the results don't even have to compare equal -- consider what
>happens when "copying" std::auto_ptr.
I wasn't able to understand what is the formal meaning
of "equivalent objects". The standard gives some reasonable meaning to
equivalent code, but for objects things are in my opinion way trickier.
Where is the definition stated ? Is something that was
added to the standard after the last public draft ?
Andrea
Howard Hinnant
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <Pine.A32.3.96.102052...@falcon.lhup.edu>,
John E. Potter <jpo...@falcon.lhup.edu> wrote:
| Just for amusement, what happens here?
|
| int main () {
| vector<A> v;
| v.reserve(3);
| B b;
| cout << "Push\n";
| v.push_back(b);
| cout << "Insert end\n";
| v.insert(v.end(), &b, &b + 1);
| cout << "Insert begin\n";
| v.insert(v.begin(), &b, &b + 1);
| }
|
| I am guessing the the last one will use A=B and not create a temporary.
| I find that a bit inconsistent. Of course, consistency is not required.
I get:
B()/nPush
A(B)
A(A)
Insert end
A(B)
A(A)
Insert begin
A(A)
A=A
A=B
--
Howard Hinnant
Metrowerks
Garry Lancaster
> That's the easy part. The thing I'm wondering about is what happens
> with regards to the source object. After a move, it logically isn't an
> object any more, and calling a destructor on it would be undefined
> behavior.
>
> Or would it. Should the move constructor modify the source object so
> that calling the destructor would be safe?
>
> Or is it all the responsibility of the programmer -- it's his
> responsibility to avoid calling the destructor. In which case, I can
> imagine some pretty difficult to find bugs when someone accidentally
> introduces a temporary into an expression using the move constructor.
General move semantics can only be given to classes
that can have a legal null-like or empty state, such as
most smart pointers or containers. Objects of such
classes are still proper valid objects after they have
been a move source.
swap is of course more generally applicable.
Kind regards
Garry Lancaster
Codemill Ltd
Visit our web site at http://www.codemill.net
John Potter
<Attila...@lmf.ericsson.se> wrote:
> John Potter wrote:
> > Allocator::construct(p, v)
> > is required to be equivalent to
> > new ((void*)p) T(v)
> > and its second parameter is required to be T const&.
> > If the standard requires use of this function, all attempts to
> solve > your problem will fail. The simple case for vector.
> > template <class U>
> > void push_back (U const& u);
> > Required implementation would include
> > alloc.construct(p, u);
> > The conversion which was saved on the call of push_back must be >
> introduced in the implementation. Exactly what happened in Howard's
> > implementation.
> That was the reason why I have made the construct to be a template as
> well:
> template <class U>
> void construct(T* p, U v) {
> new ((void *)p) T(v);
> }
> The signature may no tbee good, but I believe that is the idea.
Good enough. Now we need to change allocators also.
> > To even approach getting what you seem to want, the implementation
> must > be forbidden to use the construct member. Think about list
> and the fact > that the allocator constructs nodes not Ts. How will
> you expose the raw > part of the node for the T and use the construct
> member?
>
> Next time please ask for something complex. :-))) This is too easy:
>
> Solution: templated constructor for the node
What node? We all think that there is a node in std::list; however, the
standard does not specify one. How do you intend to specify a templated
constructor for something which does not exist?
Maybe you can see that your ideas are being taken as "wishful thinking".
The answer to your question of "why doesn't it exist" is likely that
nobody is interested enough to do the hard work of drafting a formal
specification.
The hard question to answer is likely how valuable is this optimization.
The standard usually does not specify optimizations, but only enables
them. The NRVO is an example where a copy may be removed but is left as
a QoI issue. For the simple case, my use of the insert range member
removes the copy if the QoI allows it and does not otherwise. It is as
portable as NRVO. If Howard's clients demanded it, I'm sure that he
would provide it.
Does anyone really care? Or, is this just an amusing exercise?
John
John Potter
<hin...@antispam.metrowerks.com> wrote:
> In article <Pine.A32.3.96.102052...@falcon.lhup.edu>,
> John E. Potter <jpo...@falcon.lhup.edu> wrote:
> | I am guessing the the last one will use A=B and not create a temporary.
> | I find that a bit inconsistent. Of course, consistency is not required.
> I get:
> Insert begin
> A(A)
> A=A
> A=B
As expected. Anyway, I replaced vector with list and everything makes
an extra copy, A(B),A(A), so the hack does not generalize. The
implementation that I used had a construct template which initialized
the data member of the node; however, insert range is a loop using
insert value and the copy is made before ever getting there.
As things stand, an implementer could provide an optimized version and
might if there were a perceived demand. Changing the standard to
require it would be a lot of work and maybe violate the usual rule that
the standard does not require optimizations.
John
Garry Lancaster
Garry Lancaster <glanc...@ntlworld.com> wrote in message
news:j0uJ8.2233$cA.1...@news8-gui.server.ntli.net...
> James Kanze:
> > That's the easy part. The thing I'm wondering about is what happens
> > with regards to the source object. After a move, it logically isn't an
> > object any more, and calling a destructor on it would be undefined
> > behavior.
> >
> > Or would it. Should the move constructor modify the source object so
> > that calling the destructor would be safe?
> >
> > Or is it all the responsibility of the programmer -- it's his
> > responsibility to avoid calling the destructor. In which case, I can
> > imagine some pretty difficult to find bugs when someone accidentally
> > introduces a temporary into an expression using the move constructor.
>
> General move semantics can only be given to classes
> that can have a legal null-like or empty state, such as
> most smart pointers or containers. Objects of such
> classes are still proper valid objects after they have
> been a move source.
>
> swap is of course more generally applicable.
I should mention one more special case: return values.
Since a returned object goes out of scope immediately,
you might be able to combine move and destruction in
a single operation in some safe way there. And that too
would be more broadly applicable.
John Potter
<Attila...@lmf.ericsson.se> wrote:
> John Potter wrote:
> > It will not. I only considered the stated problem which contained
> a > conversion (one parameter).
> And suggested a solution which is not portable, yes.
Yes. That is one of the joys of trying something in this newsgroup.
You can depend on learning something when there are problems with the
idea.
> But to simply tell it: I want the vector (and all other containers) to
> be able to do construction of an element _directy_ using one argument
> constructors, without a temporary copy.
That's what I thought you wanted.
> And I was thinking that the same could be done for multiply arguments
Maciej Sobczak has taken up that cause in csc++. See the "A library
extension proposal" thread.
John
Dave Harris
> General move semantics can only be given to classes
> that can have a legal null-like or empty state, such as
> most smart pointers or containers. Objects of such
> classes are still proper valid objects after they have
> been a move source.
I would say there are really 2 kinds of move. The move which leaves its
source in a destructable state, and the move which leaves its source as
raw bytes. The first can be used in situations where a subsequent
destruction is (currently) unavoidable, such as with temporary objects on
the stack. The second can be used for classes which have no legal "empty"
state.
Both kinds make sense. Neither is truly more general than the other. This
is one of the reasons why move is not such a simple idea.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
Garry Lancaster
> > General move semantics can only be given to classes
> > that can have a legal null-like or empty state, such as
> > most smart pointers or containers. Objects of such
> > classes are still proper valid objects after they have
> > been a move source.
Dave Harris:
> I would say there are really 2 kinds of move. The move which leaves its
> source in a destructable state, and the move which leaves its source as
> raw bytes. The first can be used in situations where a subsequent
> destruction is (currently) unavoidable, such as with temporary objects on
> the stack. The second can be used for classes which have no legal "empty"
> state.
I agree and I already mentioned the other kind of move
when I mentioned move return. It occurs to me that this
could also be generalised to parameter passing when
the object passed as the parameter is not used before
destruction e.g.
void foo()
{
big obj;
bar( obj ); // obj not used subsequently. Pass using move?
}
We might call this "tail move" in homage to tail recursion.
> Both kinds make sense. Neither is truly more general
> than the other. This is one of the reasons why move is
> not such a simple idea.
OK, I should have written "simple" rather than "general"
in the paragraph you quoted. Once you have swap, move
without destruction and move combined with destruction,
you have a really complicated set of options. One challenge
for the move proposal is to find a palatable compromise
between simplicity and power.
Kind regards
Garry Lancaster
Codemill Ltd
Visit our web site at http://www.codemill.net
Attila Feher
> > That was the reason why I have made the construct to be a template
> > as
> > well:
>
> > template <class U>
> > void construct(T* p, U v) {
> > new ((void *)p) T(v);
> > }
>
> > The signature may no tbee good, but I believe that is the idea.
>
> Good enough. Now we need to change allocators also.
Well. I could do it in 10 minutes, and I am _not_ a library designer, I
did not even know before the internals of Rogue Wave... But of course,
if your position is "oppose, because I did not need it so far" I cannot
help with that.
> > Solution: templated constructor for the node
>
> What node? We all think that there is a node in std::list; however,
> the standard does not specify one. How do you intend to specify a
> templated constructor for something which does not exist?
Hm. So than what is this "rebind" and "other" thing in the allocator
Scott Meyers talks about in Effective STL Item 11? A joke?
> Maybe you can see that your ideas are being taken as "wishful
> thinking".
No, actually I think that since you do not need this (or you think you
don't) you find it easier to oppose it than actually (for the same
amount of time) think about it.
> The answer to your question of "why doesn't it exist" is likely that
> nobody is interested enough to do the hard work of drafting a formal
> specification.
"Interested" and "has enough time" is two very different things. So
there may very well be _many_ interested people, but they have no time
(or opportunity) to make a formal spec.
> The hard question to answer is likely how valuable is this
> optimization.
This is _not_ optimization. This is removing a pessimization.
> The standard usually does not specify optimizations, but only enables
> them.
Good. Not doing something which is not needed is not an optimization.
It is just "writing decent code".
> The NRVO is an example where a copy may be removed but is left as a
> QoI issue.
Yep. Because thay may very well be architecture dependent if it can be
solved and how etc. _Much_ lower level things, so I guess it is not
really fair to compare it to library design!
> For the simple case, my use of the insert range member removes the
> copy if the QoI allows it and does not otherwise.
If it removes the copy, it means it does not use the allocator (to my
understanding). Or it default constructs and then assigns... which is
again a waste.
> It is as portable as NRVO.
Yes. That is the problem. I guess your implementation is not good or
bad - it is just paying the price elsewhere.
> If Howard's clients demanded it, I'm sure that he
> would provide it.
Aha. I have seen many many C++ programmers in my life. Very few of
them actually would easily understand even the problem. Not that they
find out and... Anyways AFAIS you did not get it either, since you talk
about optimization...
> Does anyone really care? Or, is this just an amusing exercise?
Did you intend this as a joke, or you seriously are accusing me with
wasting other people's time?
Attila
Shannon Barber
> std::container<T>::push_back( const T&x);
>
<snip>
> So far so good. I pass a small structure to push_back. But, to be able
> to push a T back, C++ will create a temporary T,
Something is wrong, the whole point of passing the object by constant
reference is to eliminate the temporary copy of which you speak.
You also mentioned "Sun" so it wouldn't surprise me if your compiler
made a copy any way :)
At some point in a time a copy must be made, but only once per
push_back, not twice.
Also, the behavior may be different in a release build. Have you
checked the disasm for that?
Attila Feher
>
> Attila Feher <Attila...@lmf.ericsson.se> wrote
>
> > std::container<T>::push_back( const T&x);
> >
> <snip>
> > So far so good. I pass a small structure to push_back. But, to be
> > able to push a T back, C++ will create a temporary T,
>
> Something is wrong, the whole point of passing the object by constant
> reference is to eliminate the temporary copy of which you speak.
Yep. But what I pass is another (explicitly convertable) type, not T.
> You also mentioned "Sun" so it wouldn't surprise me if your compiler
> made a copy any way :)
Nope, it is the std definition of the vector (and other containers) I am
afraid. :-(((
> At some point in a time a copy must be made, but only once per
> push_back, not twice.
Yeah, that is what I was hoping for...
> Also, the behavior may be different in a release build. Have you
> checked the disasm for that?
Sure.
Attila
John Potter
<Attila...@lmf.ericsson.se> wrote:
> "John Potter wrote:
> > Good enough. Now we need to change allocators also.
> Well. I could do it in 10 minutes, and I am _not_ a library designer
Yes, changing code is trivial. Changing the standard is not.
> > What node? We all think that there is a node in std::list; however,
> > the standard does not specify one. How do you intend to specify a
> > templated constructor for something which does not exist?
> Hm. So than what is this "rebind" and "other" thing in the allocator
> Scott Meyers talks about in Effective STL Item 11? A joke?
It's real and used. The problem is how to say in the standard that the
unmentioned node will have a templated ctor. It is easy to change
push_back to templated, it exists. The hard part is giving a spec which
says that container<A>::push_back(B const&) where B is convertable to A
does not make more than one copy. Should it hold if B has an A
conversion operator, or only if A has a B const& ctor?
> > Maybe you can see that your ideas are being taken as "wishful
> > thinking".
> No, actually I think that since you do not need this (or you think you
> don't) you find it easier to oppose it than actually (for the same
> amount of time) think about it.
Actually, I like it. Talking about it in a newsgroup is wishful
thinking. Drafting a proposal is not.
> > The answer to your question of "why doesn't it exist" is likely that
> > nobody is interested enough to do the hard work of drafting a formal
> > specification.
> "Interested" and "has enough time" is two very different things. So
> there may very well be _many_ interested people, but they have no time
> (or opportunity) to make a formal spec.
Interested "enough" requires making the time.
> > The hard question to answer is likely how valuable is this
> > optimization.
> This is _not_ optimization. This is removing a pessimization.
I will not play that word game. It is a change in efficiency not in
functionality.
> If it removes the copy, it means it does not use the allocator (to my
> understanding).
Correct, it does not use the allocator construct function which is not
required. It uses the allocator to allocate and uses placement new via
some other function to construct. AFAICT, the allocator construct and
destruct functions are a convience only. Allocators *shall* provide
them and containers *may* use them.
> > Does anyone really care? Or, is this just an amusing exercise?
> Did you intend this as a joke, or you seriously are accusing me with
> wasting other people's time?
Neither. If someone really cares, they will do the formal work
required. If not, it has still been amusing and educational. If
amusement were a waste of time, there would be no newsgroups. The
thread in csc++ does not seem to be going in the direction that I think
you would like. Maybe some input there would be more fruitful.
John
Bence Kodaj
far as I understand it, he wants to supply push_back() with the
_argument_ to T's constructor, and he wants a T object to be created
only at its final place, i.e., within the container's storage area.
But as things stand now, if you say push_back( argument_to_T's_ctor ),
then the compiler creates a temporary T from your argument, then it
binds the const T& to this temp object, then it copies the temp
object, and it's this copy that ends up in the container.
Bence Kodaj
Andrea Griffini
wrote:
>This is further discussed at:
>http://www.torque.net/sg/p/swap_vector.html
>together with an implementation that extends STLport.
>I'm working on a freestanding version.
Not long ago I was discussing about how inefficient is even
std::vector<std::string>::erase because all elements are
assigned (i.e. copied, with even unneeded allocations in
case of a non-COW std::string implementation) instead
of swapped in place. The use of copying in this case also
makes the erase operation more vulnerable to exceptions.
It would be nice to have the standard library being able
to detect the presence of a "standard" swap method and
considering in this case the objects being somewhat "heavy"
and preferring a swap call to move objects around instead
of copy-construction or assignment.
Imagining to that being part of the standard I think it
would be nice not having to use a special container for
requiring that... but only for pragmatic reasons: I think
probably most programmers would just forget to use the
different more efficient version and also having a new
standard container would lead to temporary unportable code
(the one using the new containers when used on "old"
compilers). Probably stating that a class having a method
with a signature of "void swap(X& other)" will allow the
library to use also that method to move elements around
isn't going to break a lot of existing code.
I'm not sure I would like to work with a collegue that
used that signature for a method with a different meaning...
that code in other words is going to get broken by next
maintainer anyway... ;)
That is easy (or even possible) to have that detection
in a library with current C++ template trickery it's
something I don't know. But, as for the final result, I
would like more this automatism instead of an explicit
container or algorithm approach that would require to
roughly double the size of the standard library.
An less intrusive alternative could be using
"void std::swap(T&,T&)" and swap algorithms only if a
specialization is available. No idea if this is harder
or simpler to achieve, tho.
Also the copy-destructor availability could be specified
by a specific member or a specific specialization...
This would lead to even more efficient operations on
"heavy" objects like std::string.
Andrea
John Potter
> On 27 May 2002 06:10:04 -0400, Douglas Gilbert <dgil...@interlog.com>
> wrote:
> >This is further discussed at:
> >http://www.torque.net/sg/p/swap_vector.html
> >together with an implementation that extends STLport.
> >I'm working on a freestanding version.
> Not long ago I was discussing about how inefficient is even
> std::vector<std::string>::erase because all elements are assigned
> (i.e. copied, with even unneeded allocations in case of a non-COW
> std::string implementation) instead of swapped in place. The use of
> copying in this case also makes the erase operation more vulnerable to
> exceptions.
Premature optimization? Does the profiler show a problem? Can you fix
it without changing the standard?
template <class Vec, class Iter>
Iter swap_erase (Vec& vec, Iter pos) {
std::reverse(pos + 1, vec.end());
std::reverse(pos, vec.end());
vec.pop_back();
return pos;
}
template <class Vec, class Iter>
Iter swap_insert (Vec& vec, Iter pos, typename Vec::reference val) {
typename Vec::size_type sub(pos - vec.begin());
vec.push_back(val);
pos = vec.begin() + sub;
std::reverse(pos, vec.end() - 1);
std::reverse(pos, vec.end());
return pos;
}
Likewise for insert/erase(range).
The question that comes to mind is why the application is using a vector
of strings with lots of inserts and erases in the middle. Is it really
an algorithm and data structure problem?
John
Andrea Griffini
wrote:
>Premature optimization? Does the profiler show a problem? Can you fix
>it without changing the standard?
....
>Likewise for insert/erase(range).
>
>The question that comes to mind is why the application is using a vector
>of strings with lots of inserts and erases in the middle. Is it really
>an algorithm and data structure problem?
While it's true that when you want to optimize it's important
to first understand where the time is spent my opinion is that
it's dangerous to get carried away too far with this concept
(if you care about efficiency).
You may get programs that are uniformly way slower/fatter than
necessary in 95% of the code, and quite thighly optimized in
the 5% part that adsorb most of the computation time. This is
not horrible, but far from optimal.
I've been working for a while in the realtime graphics world
where even a "mere" 20% speed increase can be quite visible...
and you can easily get that kind of slowness spread all over
your code if you're sloppy when first (pre-measuring) writing
your instructions.
Now I'm working in industrial automation where sometimes being
20% slower doesn't mean that your program is 20% worse, but
that is completely useless because you lose your train and
that the solution isn't viable (that if you're wasting 20%
is false... it would have been viable if coded properly, is
not viable just because you're a sloppy programmer).
I agree that premature optimization is not good but just
writing carelessy about what happens until you get to the
end isn't the path to perfection either, tho.
The C++ language also cares a *lot* about "premature
optimization" a few examples are "const ref" parms
when you're not interested in using aliasing instead
of by-value parms or the (ugly from an oo-perspective)
non-virtual dispatch or even inline functions or COW
strings.
In such a context (where is supposed that the programmer
knows and *cares* about what happens behind the curtain)
is strange that the C++ language hasn't a built-in
concept of "heavy" user-defined classes and uses only
assignment to move around things.
The library tries to take care of its own classes, but
the important concept of "moving" is absent. The point
in my posting was that instead of having to specify that
behaviour on a per-container or on a per-operation basis
(like, if I understand correctly, you are suggesting)
I think it would be useful to be able to specify the
behaviour on a per-class basis ("contained" class i mean).
Sure you can code without it or without changing the
standard. But I don't understand your point when
saying this... everything can be done without changing
the standard (or without C++, for that matter).
Andrea
Attila Feher
> wrote:
>
> >Premature optimization? Does the profiler show a problem? Can you fix
> >it without changing the standard?
Sorry, I have missed the first message and I feel addressed, so I answer to
this one: YES, the profiler DOES show that the code spends unacceptable
time on creation of temporaries while calling push_back. No, the problem
cannot be properly eliminated without adding templated push_back.
Attila
John Potter
> On 10 Jun 2002 12:40:08 -0400, jpo...@falcon.lhup.edu (John Potter)
> wrote:
> >Premature optimization? Does the profiler show a problem? Can you fix
> >it without changing the standard?
> >The question that comes to mind is why the application is using a vector
> >of strings with lots of inserts and erases in the middle. Is it really
> >an algorithm and data structure problem?
> While it's true that when you want to optimize it's important
> to first understand where the time is spent my opinion is that
> it's dangerous to get carried away too far with this concept
> (if you care about efficiency).
> You may get programs that are uniformly way slower/fatter than
> necessary in 95% of the code, and quite thighly optimized in
> the 5% part that adsorb most of the computation time. This is
> not horrible, but far from optimal.
[snip]
> In such a context (where is supposed that the programmer
> knows and *cares* about what happens behind the curtain)
> is strange that the C++ language hasn't a built-in
> concept of "heavy" user-defined classes and uses only
> assignment to move around things.
> The library tries to take care of its own classes, but
> the important concept of "moving" is absent. The point
> in my posting was that instead of having to specify that
> behaviour on a per-container or on a per-operation basis
> (like, if I understand correctly, you are suggesting)
> I think it would be useful to be able to specify the
> behaviour on a per-class basis ("contained" class i mean).
I question the value. Here is some quantitative data. The tests are
for inserting/erasing ranges of strings(COW) or vector<char>(nonCOW).
The base case which is the one you are complaining about.
8192 vec<vec>::ins
8028 vec<vec>::del
Using the posted algorithms nearly quarters the time.
2373 vec<vec> swapins
2364 vec<str> swapdel
Using a COW string, better than halves that time.
1019 vec<str>::ins
1003 vec<str>::del
Using the posted algorithms with COW is worse with g++3.0.4.
1264 vec<str> swapins
1264 vec<str> swapdel
And better with g++2.95.3.
467 vec<str> swapins
466 vec<str> swapdel
Using pointers, we get about as good as can be.
228 vec<vec*>::ins
227 vec<vec*>::del
If we assume that move semantics will be somewhere between the COW time
and the pointer time, we could get around 500.
What I am suggesting is that either this is not a major operation in
the application and will show no results, or the application is using
the wrong data structure.
91 set<vec>::ins
8 set<vec>::del
7 list<vec>::ins
5 list<vec>::del
The data is bad for the multiset because it contains many copies of a
few strings causing full length compares.
> Sure you can code without it or without changing the
> standard. But I don't understand your point when
> saying this... everything can be done without changing
> the standard (or without C++, for that matter).
I'm being pessimistic. If you can do much better today by using
better data structures and/or algorithms, how much effort should be
invested in changing the standard so that you can do slightly better
with poor designs in 2008? It sounds a little like writing a better
bubble sort.
Anyway, there is work in progress on move semantics. There may be
some results soon which show me to be wrong.
John
John Potter
<attila.feher.no...@lmf.ericsson.se> wrote:
> > On 10 Jun 2002 12:40:08 -0400, jpo...@falcon.lhup.edu (John Potter)
> > wrote:
> >
> > >Premature optimization? Does the profiler show a problem? Can you
> > fix >it without changing the standard?
> Sorry, I have missed the first message and I feel addressed, so I
> answer to this one: YES, the profiler DOES show that the code spends
> unacceptable time on creation of temporaries while calling push_back.
> No, the problem cannot be properly eliminated without adding templated
> push_back.
The message that you missed was about the inefficiency of
vector<string>::erase(pos). I don't think that a templated push_back
will help. :) Your comments above would be better in the csc++ thread
where you were asked about a work around for templated push_back.
With a flaky news server, groups.google.com may help you keep in
contact.
John
Attila Feher
> I'm being pessimistic. If you can do much better today by using
> better data structures and/or algorithms, how much effort should be
> invested in changing the standard so that you can do slightly better
> with poor designs in 2008? It sounds a little like writing a better
> bubble sort.
Yeah, in ideal situation you are right. But the programmers worts nightmare
happens every day: we must work with other (lame) people's code... and one
just cannot change that data structure used. :-(((
A
Christopher Eltschka
> James Kanze:
> > That's the easy part. The thing I'm wondering about is what happens
> > with regards to the source object. After a move, it logically isn't an
> > object any more, and calling a destructor on it would be undefined
> > behavior.
> >
> > Or would it. Should the move constructor modify the source object so
> > that calling the destructor would be safe?
> >
> > Or is it all the responsibility of the programmer -- it's his
> > responsibility to avoid calling the destructor. In which case, I can
> > imagine some pretty difficult to find bugs when someone accidentally
> > introduces a temporary into an expression using the move constructor.
>
> General move semantics can only be given to classes
> that can have a legal null-like or empty state, such as
> most smart pointers or containers. Objects of such
> classes are still proper valid objects after they have
> been a move source.
Maybe it would make sense to define a new state for it, let's call it
a "zombie" state. Objects in a zombie state have the following
properties:
- All operations other than assignment to the object and destruction
may cause undefined behaviour
- Calling the destructor on it doesn't cause observable behaviour
The second condition means that it must be save to destruct the
object, but it must also be save to omit destruction and simply end
the life time by reusing the memory, by deallocating the memory, or
by ending the program.
The things you can do to objects with singular state as defined above
are exactly those you can do with uninitialized PODs and with dangling
pointers.
Now a moving constructor (or a moving assignment) would have as
post-condition that the object is in a singular state.
Of course, the main problem with move is that C++ doesn't really
support the concept of a "variable with no object in it".
In a language designed up front for this concept, a variable could
f.ex. have a "valuedness status" where at each point of the source a
variable is either valued or not valued, or otherwise the code is in
error.
For example, the following code (in made-up C++-like syntax) would be
allowed:
void swap_ints(int inout a, int inout b)
// inout demands valued variables on entry, and guarantees such
// variables on exit, but in between the valuedness of the given
// variables is not defined
{
int tmp = move a; // move a to new variable tmp;
// now a is unvalued, tmp and b are valued
a = move b; // move b to a
// initially a is unvalued => move construction
// now a and tmp are valued, b is unvalued
b = move tmp; // Move tmp to b
// Now a and b are valued, tmp is unvalued
} // since tmp is unvalued, no destructor is called.
But the following would not be allowed:
void foo(int a, int inout b, int inout c)
// a has copy semantics just as in C++
{
if (a == 0)
{
b.~int(); // Ok: b is now unvalued
}
// Error: Valuedness of b is not defined here!
int d; // d is unvalued
if (a == 1)
{
d = 5; // d is (copy-)constructed with value 5, now valued
}
// Error: Valuedness of c is not defined here!
int e;
if (a == 2)
{
e = 3; // e gets valued
}
else
{
e = 4; // e gets valued
}
// Ok: e is valued in any case
c.~int(); // c gets unvalued
} // Error: c must be valued on exit
Attila Feher
> Maybe it would make sense to define a new state for it, let's call it
> a "zombie" state. Objects in a zombie state have the following
> properties:
>
> - All operations other than assignment to the object and destruction
> may cause undefined behaviour
> - Calling the destructor on it doesn't cause observable behaviour
I would be very very careful adding new undefined behavio[u]r to the
language. :-((( Cannot we just say that we can define (overload?) the copy
constructor for move semantics, by giving one with non-const argument (even
for conversion constructors!) and make a "move" operator? I mean x =< y, or
sth like that. And the rule is: move will happen only for user defined
types, giving a move constructor. Calling move on types not providing one
will copy (and issue a diagnostics)...? No diagnostics required for
builtins, there you just get a copy and the assignment of a zero-initialized
value to the source. BTW, to make this work I believe that one should come
up with a way (some template metaprogramming trick) to identify if the
objetc is moveable. Otherwise some templates will give zillions of
warnings. :-((( One "way out" of this is to drop the required diagnostics
and make an error for non-moveable user defined types and probably make no
move for builtins...
Well, I guess that is the "better" way to go: move semantics for builtins
will be the same as copy, _except_ that the value of the source is undefined
(like with default initialization). This leaves room for the implementor.
For user defined types no move constructor is generated implicitly by the
compiler (as it is nearly impossible to require that) so calling move on sth
not supporting move will result in an error. The big question is: how to
find out in a template whether the type supports move or not...
Attila
Alexander Terekhov
Christopher Eltschka wrote:
[...]
> > General move semantics can only be given to classes
> > that can have a legal null-like or empty state, such as most smart
> > pointers or containers. Objects of such classes are still proper
> > valid objects after they have been a move source.
>
> Maybe it would make sense to define a new state for it, let's call it
> a "zombie" state. Objects in a zombie state have the following
> properties:
>
> - All operations other than assignment to the object and destruction
> may cause undefined behaviour
> - Calling the destructor on it doesn't cause observable behaviour
AFAICT, that's already the part of the standard C++ -- std::auto_ptr
and all kinds of other smart pointers implementing auto_ptr-like move
semantics (on assignment and copy-construction) [shared-ownership for
standard containers&algorithms could be supported via some 'adapter'
class calling '.clone() const' or something like that] and even with
different 'release-ownership' semantics [e.g. unref or unlock]:
http://groups.google.com/groups?selm=0A2949.A3D16A54%40web.de
(Subject: Re: auto_ptr and data members)
> The second condition means that it must be save to destruct the
> object, but it must also be save to omit destruction and simply end
> the life time by reusing the memory, by deallocating the memory, or by
> ending the program.
That would be rather tricky; well, 'just' one single extra bit per
object... plus zombie 'declarator' and bool operator [unless typeid
could be adopted to return predefined 'zombie' type info], I guess. ;-)
Basically you want to 'split' the lifetime of the 'memory' object and
the 'real' object that it could contain with 'zombie' status
basically saying that it's {now} raw memory object with trivial
destructor. Or am I wrong?
> The things you can do to objects with singular state as defined above
> are exactly those you can do with uninitialized PODs and with dangling
> pointers.
These beasts all have trivial destructors and that makes things quite
simple, but somewhat less useful & powerful, in my school-of-thought.
;-)
> Now a moving constructor (or a moving assignment) would have as
> post-condition that the object is in a singular state.
That's basically the same as allowing the 'manual' destruction of
automatic objects [w/o subsequent manual placement reconstruction
prior to exit from the corresponding scope], oder? Basically, manual
destruction or 'move-out' should set that 'non-existent/zombie' bit;
manual reconstruction or 'move-in' should reset that 'non-existent/
zombie' bit. Or am I missing something?
> Of course, the main problem with move is that C++ doesn't really
> support the concept of a "variable with no object in it".
Again, that's simply some collection or some smart pointer in the
current C++, AFAICT.
regards,
alexander.
Bernd Strieder
> Where do I miss the point? It all seems so simple - I mean that it
> should have been possible. Is there some very good - but hidden for me
> reason why this must not be done?
It's like pandoras box. If it became possible to pass some data to
push_back, that may be converted or passed to a constructor, then there
would be demand to generalize further:
class A
{
public:
A(int);
A(int,int);
A(int,int,int);
}
std::vector<A> as;
as.push_back(2);
as.push_back(2,3);
as.push_back(2,3,4);
What about the other insert methods? Well, this would be a few more member
templates only for the case with one argument, but everything beyond is
just ugly. That might change with some kind of variable template argument
lists becoming available.
Another solution could be an extension to the containers like:
template <class T,...>
void* vector<T,...>::uninitialized_push_back();
template <class T,...>
void* vector<T,...>::uninitialized_insert(iterator);
new (as.uninitialized_push_back()) A(3,4,5);
But a method like that in a container's interface is breaking about half of
all philosophy behind STL and C++, not to mention value semantics.
Moving constructors could reduce the problem, but not remove. The moved item
has to be constructed and then it is moved, which might still need some
additional effort compared to constructing it once in the right place.
What you want is not there by design. I doubt that cases, where optimizing
this case matters, are frequent enough to justify introduction of any of
the hacks into the standard. Consequently, the solution is a container of
your own designed for your situation.
Bernd Strieder
Attila Feher
>
> Attila Feher wrote:
>
> > Where do I miss the point? It all seems so simple - I mean that it
> > should have been possible. Is there some very good - but hidden for me
> > reason why this must not be done?
>
> It's like pandoras box. If it became possible to pass some data to
> push_back, that may be converted or passed to a constructor, then there
> would be demand to generalize further:
And here you can stop. The issue whether or not a templated push_back
(construct, whatever) is useful in the wide world or not is not based on
what do you imagine what else people could ask! So please stick to what
the topic is and if you know any better solution (without rewriting the
STL as part of the project) please share it. I would highly appreciate
if you would do no FUD in this topic. Let's just keep to the technical
facts!
[ANIP]
> But a method like that in a container's interface is breaking about half of
> all philosophy behind STL and C++, not to mention value semantics.
Good! I did not ask for it.
> Moving constructors could reduce the problem, but not remove. The moved item
> has to be constructed and then it is moved, which might still need some
> additional effort compared to constructing it once in the right place.
It is no solution to my problem. Move semantics - to really save time -
require dynamicly allocated memory, which is not an option in most of
the performance-sensitive cases.
> What you want is not there by design.
Yes. And it is very simple to put it there, and it (AFAIK) does not
break _anything_.
> I doubt that cases, where optimizing
> this case matters, are frequent enough to justify introduction of any of
> the hacks into the standard.
Khm. Please keep out words like hack, when talking about my solution.
Well, sorry: you did not talk about my solution (templated push back)
even a word. I apologize: please feel free to call your own suggestions
hacks. But I would appreciate if - talking about my original proposal -
you would simply stick to technical facts and if you cannot bring up any
technical argument against templated push_back..., well then I really do
not think it is appopriate to label it as hack.
> Consequently, the solution is a container of
> your own designed for your situation.
For you probably, I live from what I produce and I do not have the
resources to redesign the wheel.
....
I am so happy, that there are so many people here, who knows _every_
place on Earth, where people work with C++, also what they do, and also
what problems they have. To point out the cause of my frustration:
there were _many_ people posting me direct emails and explaining that
they had the same problem, but they whish not to post about it to the
newsgroup(s), because all they get is flame or near-flame statements
that their problem is no problem! Many people, not few said that! So I
believe that it would be a good path to follow that if someone has
nothing to say would not say anything... I do not think it is a good
idea to alienate people by judging them harshly: esp. if without any
real technical arguments.
Now taking this into account and the fact that the posters against this
suggestion could not come up with _any_ decent technical reason why not
allow it (templated push back), I would ask again: is there any
particular reason (a gotcha etc.) why it should not be there? If not...
it does not break any code and can save a lot for performance... and
does not make it worse in any case. So I would really appreciate it if
I could get some technically found articles to see if this is possible
and I would really like to save my time from reading articles telling
that it is not a problem to be solved. The email I have received tell
otherwise.
Attila
Andrei Alexandrescu
news:3D184D8B...@lmf.ericsson.se...
[snip]
I have an idea. You can define push_back within the existing C++ with
the templated insert() function like so:
template <class V, class T>
inline void push_back(V& v, const T& t)
{
v.reserve(v.size() * 2);
v.insert(v.end(), &t, &t + 1);
}
The first line ensures amortized constant cost, and the second line
calls the templated insert() member function of vector, passing it as
iterator the address of the object to be inserted. The templated
insert will construct in-place an object the way you wanted.
Hope this helps,
Andrei
John Potter
<andre...@hotmail.com> wrote:
> I have an idea. You can define push_back within the existing C++ with
> the templated insert() function like so:
>
> template <class V, class T>
> inline void push_back(V& v, const T& t)
> {
> v.reserve(v.size() * 2);
> v.insert(v.end(), &t, &t + 1);
> }
Two problems. It was mentioned a month ago when this thread started.
It doesn't work if the implementation uses allocator.construct. The
copying is passed on to that non-template function.
John
John Mullins
news:af9sbi$clk7l$1...@ID-14036.news.dfncis.de...
> I have an idea. You can define push_back within the existing C++ with
> the templated insert() function like so:
>
> template <class V, class T>
> inline void push_back(V& v, const T& t)
> {
> v.reserve(v.size() * 2);
> v.insert(v.end(), &t, &t + 1);
> }
>
> The first line ensures amortized constant cost,
Are you sure about this?
JM
Joshua Lehrer
>
> inline void push_back(V& v, const T& t)
> {
> v.reserve(v.size() * 2);
> v.insert(v.end(), &t, &t + 1);
> }
>
> The first line ensures amortized constant cost, and the second line
I don't see how this gives you constant cost.
Start with a vector of 4 elements, capacity=4. Call push_back. It
reserves 4*2=8 elements, then inserts the element to make 5 total
elements.
Call push_back again. It reserves 5*2=10 elements, then inserts the
element to make 6, etc... Every single call to push_back, with this
code, requires a capacity change.
shouldn't it be:
template <class V, class T>
inline void push_back(V& v, const T& t)
{
if (v.capacity()==v.size())
v.reserve(v.size() * 2);
v.insert(v.end(), &t, &t + 1);
}
even better, shouldn't v.insert(...) do the amortized constant cost
for you? I believe it does. According to SGI's documentation, "When
it is necessary to increase capacity(), vector usually increases it by
a factor of two..." v.insert certainly may need to increase capacity,
so I believe the final answer is really:
template <class V, class T>
inline void push_back(V& v, const T& t)
{
v.insert(v.end(), &t, &t + 1);
}
joshua lehrer
factset research systems
Allan W
> I have an idea. You can define push_back within the existing C++ with
> the templated insert() function like so:
>
> template <class V, class T>
> inline void push_back(V& v, const T& t)
> {
> v.reserve(v.size() * 2);
> v.insert(v.end(), &t, &t + 1);
> }
>
> The first line ensures amortized constant cost,
I think you meant to wrap it in an if() statement?
Tim Sharrock
<andre...@hotmail.com> wrote:
>You can define push_back within the existing C++ with
>the templated insert() function like so:
>
>template <class V, class T>
>inline void push_back(V& v, const T& t)
>{
> v.reserve(v.size() * 2);
> v.insert(v.end(), &t, &t + 1);
>}
>
>The first line ensures amortized constant cost
I fear not... if you do a sequence of push_backs, then
each will cause a reserve of a size two bigger than the
previous reserve, probably causing a reallocation each time.
For amortized constant you need to reserve with a new size
less often than that, eg
if(v.size()==v.capacity()){v.reserve(v.size() * 2);}
Tim
--
Tim Sharrock (t...@sharrock.org.uk)
Bernd Strieder
> Bernd Strieder wrote:
> And here you can stop. The issue whether or not a templated push_back
> (construct, whatever) is useful in the wide world or not is not based on
> what do you imagine what else people could ask! So please stick to what
If you want a std:: in front of it, then it matters.
> the topic is and if you know any better solution (without rewriting the
> STL as part of the project) please share it. I would highly appreciate
> if you would do no FUD in this topic. Let's just keep to the technical
> facts!
There are enough places, where things were left out of something, because it
was not possible to generalize them. That templatized push_back opens more
gaps in the interface than it closes. The problem ranges over all
containers and all methods to insert elements. Making all of them templates
would be a big step.
Some insert methods are templated with iterator types, but there low impact
is obvious, the implementation is straightforward.
A disadvantage could well be code bloat, as always is possible with
templates. Depending on how deep in terms of levels of functions the actual
construction happens, some more (non-public) member functions might have to
be templated additionally, you have seen it as you tried to implement. It
might be necessary, to change other parts of the library used internally,
widening the impact. Admittedly, it is possible to reduce code-bloat
problems to a minimum, but zero is not always possible.
You have tried to implement templated push_back for vector, I guess it is
the by far easiest case, and probably the one, where the general advantage
is the smallest, since vector copies its elements most of all containers.
Bernd Strieder
Attila Feher
>
> Attila Feher wrote:
>
> > Bernd Strieder wrote:
> > And here you can stop. The issue whether or not a templated push_back
> > (construct, whatever) is useful in the wide world or not is not based on
> > what do you imagine what else people could ask! So please stick to what
>
> If you want a std:: in front of it, then it matters.
You mean that it matters what people _might_ ask in order to take an
unbiased look on something which is actually asked?
> There are enough places, where things were left out of something, because it
> was not possible to generalize them. That templatized push_back opens more
> gaps in the interface than it closes.
I am sorry to be a smartass, but I have to ask: for exmaple? I have
really meant technical _facts_ and this comment is way to broad to take
it as a fact. :-(
> The problem ranges over all
> containers and all methods to insert elements. Making all of them templates
> would be a big step.
Yes. But what I was talking about is not to make everything in the
whole wide word to be a template, but to look into making push_back
tenplated.
[SNIP]
> A disadvantage could well be code bloat, as always is possible with
> templates.
You mean that the disadvantage would be that instead of inlining a copy
constructor call via replacement new we would inline a call to another
constructor? I fail to see here the possibility of a serious code
bloat. Could you give an exact example?
> Depending on how deep in terms of levels of functions the actual
> construction happens, some more (non-public) member functions might have to
> be templated additionally, you have seen it as you tried to implement.
I did try to implement it, in fact I did implement it. During which I
have found some pretty obscure behavior of the Standard Library
implementation in the SUN version we use here...
> It
> might be necessary, to change other parts of the library used internally,
> widening the impact.
Please tell concrete things, because I still do not see the "wide
impact" as a bad impact. At least not as long as some concrete facts
are presented. So far you have warned against code bloat, which I
believe has a little chance with the functionality involved here: since
the functions are so small that they must be inlined in any decent
implementation.
> Admittedly, it is possible to reduce code-bloat
> problems to a minimum, but zero is not always possible.
While in general I certainly believe you to 100% I still do not see how
could any serious code bloat happen here, in this specific case. :-(
> You have tried to implement templated push_back for vector, I guess it is
> the by far easiest case, and probably the one, where the general advantage
> is the smallest, since vector copies its elements most of all containers.
This is again a pretty negative comment - based on no facts. If one has
a vector of things (which is _only_ a vector, because the number of
elements is not known until runtime) and tries to fill it from another
container, converting element, with reserving the right amount of space
in advance there will be no copying! So your argument about copying
here is mute. There is a class, with a member vector, but once this
vector is filled, it is not touched anymore! And when it is filled, the
required number of elements are reserved in it, so no copying occures -
of course, since it has to be _fast_. It is _only_ a vector, because
the maximum number of elements is not bound.
Attila
Bernd Strieder
> Bernd Strieder wrote:
>> If you want a std:: in front of it, then it matters.
>
> You mean that it matters what people _might_ ask in order to take an
> unbiased look on something which is actually asked?
There will be lots of people asking why somhing has std:: in front of it.
>
>> There are enough places, where things were left out of something, because
>> it was not possible to generalize them. That templatized push_back opens
>> more gaps in the interface than it closes.
>
> I am sorry to be a smartass, but I have to ask: for exmaple? I have
> really meant technical _facts_ and this comment is way to broad to take
> it as a fact. :-(
The problem we are about here is the most prominent. Member templates had
already been used, I can't imagine that using them for the insert methods
to allow inlining the constructors had not been discussed.
There are many cases, where something is done for a pair, or for 1 or 2
items, but not any more. At times I would have needed a triple, a 4-tuple
or 5-tuple, or a binder with more slots. But you have to do them yourself.
>
> Yes. But what I was talking about is not to make everything in the
> whole wide word to be a template, but to look into making push_back
> tenplated.
If only push_back allowed this kind of stuff the interface would be
inconsistent. It was a goal to make the containers as easily exchangeable
as possible. The insertion methods should be exchangeable without big
surprises, either.
>
> [SNIP]
>> A disadvantage could well be code bloat, as always is possible with
>> templates.
>
> You mean that the disadvantage would be that instead of inlining a copy
> constructor call via replacement new we would inline a call to another
> constructor? I fail to see here the possibility of a serious code
> bloat. Could you give an exact example?
Currently, when doing a push_back inserting a type that has to be converted,
the conversion will take place before. If you have code inserting several
different types, only one variant of push_back is needed. With those member
templates an instance of its own will be generated for every type. This is
code bloat, not for you, but for others. There are containers, where
inlining all of the insertion code is not feasible, and with large objects
of the kind you have, it can be expected, that it is not feasible to inline
its constructors, as well. Then you will see code bloat in existing code,
where it didn't exist before. You won't see code bloat in your code, to
make it clear. And maybe it is possible to reduce the code bloat for
existing code.
So to keep the meaning of the old push_back, a templatized push_back must
get another name.
Perhaps the compiler could even try to be clever to select the instantiation
of the member template producing the best code. Since optimizing copies
away is allowed already, why not, but a hard requirement.
>
> Please tell concrete things, because I still do not see the "wide
> impact" as a bad impact. At least not as long as some concrete facts
> are presented. So far you have warned against code bloat, which I
> believe has a little chance with the functionality involved here: since
> the functions are so small that they must be inlined in any decent
> implementation.
There are interfaces to handle raw memory, construction, destruction and
copying in the library. I would expect the containers to use them. Are they
ready for your requirements? Could making them ready lead to code bloat in
existing code? Often enough container elements are embedded in other types,
their constructors will have to be templatized.
>> You have tried to implement templated push_back for vector, I guess it is
>> the by far easiest case, and probably the one, where the general
>> advantage is the smallest, since vector copies its elements most of all
>> containers.
>
> This is again a pretty negative comment - based on no facts. If one has
> a vector of things (which is _only_ a vector, because the number of
> elements is not known until runtime) and tries to fill it from another
> container, converting element, with reserving the right amount of space
> in advance there will be no copying! So your argument about copying
> here is mute. There is a class, with a member vector, but once this
> vector is filled, it is not touched anymore! And when it is filled, the
> required number of elements are reserved in it, so no copying occures -
> of course, since it has to be _fast_. It is _only_ a vector, because
> the maximum number of elements is not bound.
You use vector in a very special way. You could get what you want by simply
using std::allocator<T>::allocate followed by a loop with placement new. No
more lines of code than you already have, well you have store two pointers
instead of one vector. So there is no reason to make only
vector<T>::push_back a member template, since only in combination with
reserve() you get something, that could easily be done with about the same
amount of using existing facilities.
My problem with templatizing push_back() and other element insert() methods
is, that it is possible, it can not be generalized easily, as I would
expect, but it adds complexity and code bloat, and it changes the behaviour
of existing code. It is by no means a drop in replacement for the
push_back() and insert() we have.
Bernd Strieder