This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [RFA] Algorithms vs operator* and operator==
On Nov 6, 2004, at 8:13 PM, Joe Buck wrote:
On Sat, Nov 06, 2004 at 09:41:42PM +0000, chris jefferson wrote:
Connected to this, I've been investigating a number of the algorithms
where it can be much more efficent to implement them purely in terms
of
swap rather than assignments (reverse, sort, and others) for those
classes where a swap is MUCH cheaper than an assignment (lists and
vectors come to mind). However a swap is twice as expensive as an
assignment for scalar classes, and could in theory be 3 times as
expensive for a big class which didn't implement a swap (although I'm
tempted to ignore these).
Therefore, similarily I have 3 options..
1) Make the int, float, etc. case efficent
2) Make the vector, list, etc case efficent
3) Use somethiing like _is_scalar (and perhaps others.. is_pod comes
to
mind) to try to decide when to make the choice
The needed property is something that might be called "relocatable".
Many classes have the property that they can be relocated by means of
a shallow copy. This is true of vector, list, string, map, hash_map,
and many user-written classes that store part of their state on the
heap.
This property means that swap has a very efficient implementation, but
it goes beyond this. Consider resizing a vector of strings, or a
vector
of vectors. It turns out that it would suffice to do a bitwise copy
of the old vector storage to the new vector storage, without calling
any constructors or destructors! This can be hugely more efficient.
We're reinventing what Howard Hinnant calls "move semantics".
If we're going down this route, let's build on his work.
--Matt