In article <432C6B43.3000602@cs.york.ac.uk>,
 caj@cs.york.ac.uk (chris jefferson) wrote:

> This issue will become somewhat simpler when move semantics are
> introduced, as then the value can be copied stright away (expensive) and
> then moved to it's final location after the vector is rearranged
> (cheap). In that case it might be sensible to change the function so it
> accepts by value rather than by reference.
>
> (It increasingly feels like whenever discussing efficency and
> optimisation, I end up writing "when move semantics are introduced.."
> all the time ^_^)

Imho changing the vector/deque::insert signature to take the value_type
by value would be a premature pessimization (as it is for resize today).

One can either internally copy and then move from as you propose, or the
implementation can detect if the reference refers into the container,
and then locate the new position of the element.  For vector, except for
the very simplest of value_type's, it will be faster to do the latter.
For deque it will be faster to do the latter for expensive to copy
objects and for deque's with relatively few internal segments.

Fwiw, the new proposed signatures:

insert(iterator position, T&& x);

are specifically given permission to avoid the check for self
referencing.  The implementation may assume that the x is truly an
rvalue, and not a reference to a moved-from lvalue that may be internal
to the container:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1858.html

23.1p13.  The lack of the self referencing test will not only increase
performance, it will also avoid the CopyConstructible requirement for
these new signatures.

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

chris jefferson wrote:
> John Nagle wrote:
> > chris jefferson wrote:
> >
> >     Implementations should make that work right.  It works
> > if the vector isn't being resized.
>
> Actually, the (I believe) most efficent implementation won't work even
> if the vector isn't resized.
>
> The best implementation would either copy or move all the elements of
> the vector forwards one before even looking at the reference.

That depends on your definition of 'best'.
I prefer 'corrrect' over 'efficient' - at least for a general framework
like the STL.  Micro-optimisations can be worked on done later if the
code is too slow.  This applies in my usual computing environments,
anyway - YMMV.

Roger Orr
--
MVP in C++ at www.brainbench.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]