Home > Archive > VC STL > January 2006 > BUG? list::remove may refer to an already destroyed element
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
BUG? list::remove may refer to an already destroyed element
|
|
| Igor Tandetnik 2006-01-25, 9:59 pm |
| list::remove takes value to be removed by const reference. This
reference may refer to an element stored in the list. When this happens,
the element is destroyed in the middle of the operation, but is still
being used for comparisons. This invokes undefined behavior.
Consider:
#include <iostream>
#include <list>
using namespace std;
struct Val {
int value;
unsigned canary;
Val(int val) : value(val), canary(0x600DF00D) {}
~Val() {canary = 0xDEADBEEF;}
};
bool operator==(const Val& val1, const Val& val2) {
if (val1.canary != 0x600DF00D || val2.canary != 0x600DF00D) {
cout << "Oops!" << endl;
}
return (val1.value == val2.value);
}
int main() {
list<Val> l;
l.push_back(Val(1));
l.push_back(Val(2));
l.remove(l.front());
return 0;
}
It prints "Oops!" on both VC7.1 and VC8.
I don't believe such usage is prohibited by the standard.
Bug report here:
http://lab.msdn.microsoft.com/Produ...a4-bd978f1b90f1
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
| |
| Tom Widmer [VC++ MVP] 2006-01-26, 8:01 am |
| Igor Tandetnik wrote:
> I don't believe such usage is prohibited by the standard.
>
> Bug report here:
> http://lab.msdn.microsoft.com/Produ...a4-bd978f1b90f1
Here's another related one:
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
struct Val {
unsigned canary;
Val() : canary(0x600DF00D) {}
Val(Val const& val):canary(val.canary) {
if (canary != 0x600DF00D)
cout << "Oops!\n";
}
~Val() { canary = 0xDEADBEEF; }
};
int main()
{
vector<Val> v(1);
fill_n(back_inserter(v), 2, v.front());
}
However, I'm not *completely* convinced that these are bugs either. In
each case, the value referred to becomes invalid, thus the expressions
required by the algorithm (e.g. *i == value) become invalid, so it could
be argued that the usage is incorrect. The cure involves taking a single
(assuming a good implementation) copy of the T element inside the
algorithms, which presumably is unlikely to kill performance.
Tom
| |
| Doug Harrison [MVP] 2006-01-26, 7:08 pm |
| On Thu, 26 Jan 2006 10:29:31 +0000, "Tom Widmer [VC++ MVP]"
<tom_usenet@hotmail.com> wrote:
>Igor Tandetnik wrote:
>
>
>Here's another related one:
<snip>
>However, I'm not *completely* convinced that these are bugs either. In
>each case, the value referred to becomes invalid, thus the expressions
>required by the algorithm (e.g. *i == value) become invalid, so it could
>be argued that the usage is incorrect. The cure involves taking a single
>(assuming a good implementation) copy of the T element inside the
>algorithms, which presumably is unlikely to kill performance.
Subtle, and probably correct. I recall one function takes this into
account, vector::resize(size_type, T), but then there are vector::insert
and push_back, map::erase, etc, all of which take const T&. I'd ask about
this in one of the comp. groups.
--
Doug Harrison
Visual C++ MVP
| |
| Igor Tandetnik 2006-01-26, 7:08 pm |
| Tom Widmer [VC++ MVP] <tom_usenet@hotmail.com> wrote:
> Igor Tandetnik wrote:
>
>
> However, I'm not *completely* convinced that these are bugs either. In
> each case, the value referred to becomes invalid, thus the expressions
> required by the algorithm (e.g. *i == value) become invalid
But the value becomes invalid due to internal implementation details of
the function, not as a direct corollary of its specification. Taken to
the extreme, your argument seems to imply that, to write portable code,
the user of the function must consider all possible ways this function
could be implemented, and make sure not to rub any of them the wrong
way.
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
| |
| Igor Tandetnik 2006-01-26, 7:08 pm |
| Doug Harrison [MVP] <dsh@mvps.org> wrote:
> Subtle, and probably correct. I recall one function takes this into
> account, vector::resize(size_type, T), but then there are
> vector::insert and push_back, map::erase, etc, all of which take
> const T&.
All of them handle the situation correctly in Dinkumware implementation.
vector::insert and vector::remove specifically make a copy of the value
before modifying the container in any way. map::erase (and other
associative containers) uses equal_range to find a pair of iterators and
does not check the value anymore. I've actually gone through the source
code of all STL containers - list::remove appears to be the only one
with the problem.
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
| |
| Doug Harrison [MVP] 2006-01-26, 7:08 pm |
| On Thu, 26 Jan 2006 13:16:39 -0500, "Igor Tandetnik" <itandetnik@mvps.org>
wrote:
>Doug Harrison [MVP] <dsh@mvps.org> wrote:
>
>All of them handle the situation correctly in Dinkumware implementation.
>vector::insert and vector::remove specifically make a copy of the value
>before modifying the container in any way. map::erase (and other
>associative containers) uses equal_range to find a pair of iterators and
>does not check the value anymore. I've actually gone through the source
>code of all STL containers - list::remove appears to be the only one
>with the problem.
Regardless of what the intent is, it's not clearly specified in the C++
Standard, AFAICT. I hope you'll ask about this over in
comp.lang.c++.moderated or comp.std.c++. I've always wondered about the
oddball resize function vs. all the rest...
--
Doug Harrison
Visual C++ MVP
| |
| P.J. Plauger 2006-01-26, 7:08 pm |
| "Igor Tandetnik" <itandetnik@mvps.org> wrote in message
news:ufvyqSqIGHA.2828@TK2MSFTNGP12.phx.gbl...
> Doug Harrison [MVP] <dsh@mvps.org> wrote:
>
> All of them handle the situation correctly in Dinkumware implementation.
> vector::insert and vector::remove specifically make a copy of the value
> before modifying the container in any way. map::erase (and other
> associative containers) uses equal_range to find a pair of iterators and
> does not check the value anymore. I've actually gone through the source
> code of all STL containers - list::remove appears to be the only one with
> the problem.
Not anymore. I just changed our baseline to copy the test value.
Thanks,
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
| |
| Igor Tandetnik 2006-01-26, 7:08 pm |
| P.J. Plauger <pjp@dinkumware.com> wrote:
> "Igor Tandetnik" <itandetnik@mvps.org> wrote in message
> news:ufvyqSqIGHA.2828@TK2MSFTNGP12.phx.gbl...
>
>
> Not anymore. I just changed our baseline to copy the test value.
Could you please also comment on my other post in this group, with the
subject of "BUG? std::remove incorrect when value to be removed is in
the sequence" ?
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
| |
| Tom Widmer [VC++ MVP] 2006-01-30, 8:02 am |
| Igor Tandetnik wrote:
> Tom Widmer [VC++ MVP] <tom_usenet@hotmail.com> wrote:
>
>
>
> But the value becomes invalid due to internal implementation details of
> the function, not as a direct corollary of its specification. Taken to
> the extreme, your argument seems to imply that, to write portable code,
> the user of the function must consider all possible ways this function
> could be implemented, and make sure not to rub any of them the wrong
> way.
Given the specification of the list::remove, however it is implemented
you are guaranteed to end up with a hanging reference by the end of the
function call if you pass l.front(), which is something I always feel
slightly uncomfortable with even if the reference is never 'used'.
For sure, this should be (and has been according to this thread) fixed
as a QOI issue, since removing all elements that have the same value as
a particular element of a list is not an unlikely operation. However, I
think the problem may lie with the standard - if all of these modifying
members and algorithms took a T rather than a T const&, the problem
would never have arisen.
Finally, I do take the argument to the extreme - you can't assume
anything about an implementation except that it meets the specification.
Because the function takes its parameter by reference, I think you have
the responsibility to only pass a reference that isn't going to be
invalidated by the call according to the element invalidation rules for
the sequence in question (e.g. for list, erased elements are invalidated).
Tom
|
|
|
|
|