 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
chris jefferson
Guest
|
 Posted: Wed Sep 14, 2005 3:14 pm Post subject: Defect Report : Is it undefined if a function in the standar |
 |
|
[ Note: Forwarded to C++ Committee. -sdc ]
Problem: There are a number of places in the C++ standard library where
it is possible to write what appear to be sensible ways of calling
functions, but which can cause problems in some (or all)
implementations, as they cause the values given to the function to be
changed in a way not specified in standard (and therefore not coded to
correctly work). These fall into two similar categories.
1) Parameters taken by const reference can be changed during execution
of the function
Examples:
Given std::vector<int> v:
v.insert(v.begin(), v[2]);
v[2] can be changed by moving elements of vector
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.
2) A range is given which changes during the execution of the function:
Similarly,
v.insert(v.begin(), v.begin()+4, v.begin()+6);
This kind of problem has been partly covered in some cases. For example
std::copy(first, last, result) states that result cannot be in the range
[first, last). However, does this cover the case where result is a
reverse_iterator built from some iterator in the range [first, last)?
Also, std::copy would still break if result was reverse_iterator(last +
1), yet this is not forbidden by the standard
Solution:
One option would be to try to more carefully limit the requirements of
each function. There are many functions which would have to be checked.
However as has been shown in the std::copy case, this may be difficult.
A simpler, more global option would be to somewhere insert text similar to:
If the execution of any function would change either any values passed
by reference or any value in any range passed to a function in a way not
defined in the definition of that function, the result is undefined.
Such code would have to at least cover chapters 23 and 25 (the sections
I read through carefully). I can see no harm on applying it to much of
the rest of the standard.
Some existing parts of the standard could be improved to fit with this,
for example the requires for 25.2.1 (Copy) could be adjusted to:
Requires: For each non-negative integer n < (last - first), assigning to
*(result + n) must not alter any value in the range [first + n, last).
However, this may add excessive complication.
One other benefit of clearly introducing this text is that it would
allow a number of small optimisations, such as caching values passed
by const reference.
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 ]
|
|
| Back to top |
|
 |
John Nagle
Guest
|
| Posted: Fri Sep 16, 2005 2:27 am Post subject: Re: Defect Report : Is it undefined if a function in the sta |
|
|
chris jefferson wrote:
| Quote: | 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.
| Quote: | 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.
| Quote: |
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 ]
|
|
| Back to top |
|
|
chris jefferson
Guest
|
| Posted: Sat Sep 17, 2005 2:04 am Post subject: Re: Defect Report : Is it undefined if a function in the sta |
|
|
John Nagle wrote:
| Quote: | 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]).
| Quote: |
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 ]
|
|
| Back to top |
|
|
rogero@howzatt.demon.co.u
Guest
|
| Posted: Sat Sep 17, 2005 6:12 pm Post subject: Re: Defect Report : Is it undefined if a function in the sta |
|
|
chris jefferson wrote:
| Quote: | 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 ]
|
|
| Back to top |
|
|
chris jefferson
Guest
|
| Posted: Sat Sep 17, 2005 8:05 pm Post subject: Re: Defect Report : Is it undefined if a function in the sta |
|
|
[email]rogero (AT) howzatt (DOT) demon.co.uk[/email] wrote:
| Quote: | 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 ]
|
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Fri Sep 23, 2005 3:00 am Post subject: Re: Defect Report : Is it undefined if a function in the sta |
|
|
In article <432C6B43.3000602 (AT) cs (DOT) york.ac.uk>,
[email]caj (AT) cs (DOT) york.ac.uk[/email] (chris jefferson) wrote:
| Quote: | 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 ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
