rogero@howzatt.demon.co.uk wrote:
> 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.

I should of course have not used the word best, but instead talked about
 "more efficent'. The point I was trying to make is that the "most
efficent", and arguably simplest, implementation isn't safe. Therefore
if the intention of the standard is that it should be safe, the standard
should specify so explicitally. I'd personally perfer it was safe, but
when you have vectors of large types, extra copies can be quite expensive.

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 ^_^)

Chris

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

> Given std::vector<int> v:
> v.insert(v.begin(), v[2]);
> v[2] can be changed by moving elements of vector

     Implementations should make that work right.  It works
if the vector isn't being resized.  If the vector is being
resized, all its elements usually have to be copied, and
the additional overhead of copying the incoming parameter
is a small fraction of the total overhead.

     If the argument were by value, this would work.  Making
it a const reference is an optimization, which puts the burden
on the implementor to make it work right.

> Given std::list<int> l:
> l.remove(*l.begin());
> Will delete the first element, and then continue trying to access it.
> This is particularily vicious, as it will appear to work in almost all
> cases.

     That's a search, and a relatively expensive (O(N)) operation.
I'd suggest that there, the argument to "remove" should be by value,
not reference, so that this will work.   It's a search key; its value,
not its identity, matters.
>
> 2) A range is given which changes during the execution of the function:
> Similarly,
>
> v.insert(v.begin(), v.begin()+4, v.begin()+6);

     As above, using a const ref here is a O(1) optimization
for an O(N) operation, and may not be worth it.

    John Nagle
    Animats

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

John Nagle wrote:
> chris jefferson wrote:
>
>> Given std::vector<int> v:
>> v.insert(v.begin(), v[2]);
>> v[2] can be changed by moving elements of vector
>
>
>     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. By that
point the value pointed to by the reference would have already changed
(to what used to be v[1]).

>>
>> 2) A range is given which changes during the execution of the function:
>> Similarly,
>>
>> v.insert(v.begin(), v.begin()+4, v.begin()+6);
>
>
>     As above, using a const ref here is a O(1) optimization
> for an O(N) operation, and may not be worth it.

For the same reason as in the first example, the problem is we move the
range v.begin()+4 to v.begin()+6 before we come to try to copy it.

I actually agree that a useful option would be to try to fix as many of
these things as possible so they actually work correctly. All I really
want to escape from the current state, where different implementations
make different operations safe, and don't exactly document how they do
it as well.

Chris

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