Is this valid code?

[Bob Brian]

I was having a discussion with a friend about if the following is valid
code. I'm fairly sure it isn't allowed, but my friend seems to think
it's fine. It definatly appears to run fine in all the compilers we can
get access to. Any comments?

Bob

void remove_duplicates(std::list<int>& in_list)
{
std::list<int>::iterator it = in_list.begin();
in_list.remove(*it);
}

 

[matthias_k]

I was having a discussion with a friend about if the following is valid
code. I'm fairly sure it isn't allowed, but my friend seems to think
it's fine. It definatly appears to run fine in all the compilers we can
get access to. Any comments?

Bob

void remove_duplicates(std::list<int>& in_list)
{
std::list<int>::iterator it = in_list.begin();
in_list.remove(*it);
}

Well, why do YOU think it wouldn't compile?

I think it would compile, but it wouldn't do what it's supposed to.
What it does is to remove all elements in in_list which equal the value
of *(in_list.begin()).

On top of that, if in_list is empty, the behavior of your function is
most probably undefined.

Regards,
Matthias

 

[matthias_k]

Well, why do YOU think it wouldn't compile?

I think it would compile, but it wouldn't do what it's supposed to.
What it does is to remove all elements in in_list which equal the value
of *(in_list.begin()).

On top of that, if in_list is empty, the behavior of your function is
most probably undefined.

Regards,
Matthias

// test.cpp
#include <list>

void remove_duplicates(std::list<int>& in_list)
{
std::list<int>::iterator it = in_list.begin();
in_list.remove(*it);
}

$ g++ -pedantic -Wall -std=c++98 -o test test.cpp
--> no errors.

This may be a hint that this code is at least syntactically correct

Regards,
Matthias

 

[matthias_k]

What it does is to remove all elements in in_list which equal the value
of *(in_list.begin()).

This should of course read:
.... remove all *duplicates* in in_list which equal the value
of *(in_list.begin()).

 

[Bob Brian]

Well, why do YOU think it wouldn't compile?

I think it would compile, but it wouldn't do what it's supposed to.
What it does is to remove all elements in in_list which equal the value
of *(in_list.begin()).

On top of that, if in_list is empty, the behavior of your function is
most probably undefined.

Sorry, I have just realised I pasted in a bit of code without any
explanation as to the problem!

The code does compile, and apart from the empty list case (woops! forgot
that!) does what it is supposed to do, which is remove all copies of the
first element of the list.

However, it is my belief that this code isn't actually defined, as I
read that in_list.remove is supposed to take *it by reference, and there
is no need for it to make an internal copy. Therefore as soon as the
first element of in_list has been removed then the rest of the remove
function is getting the value of it from freed memory. The code happens
to work because the value of it is generally pulled into a register and
kept there.

My friend believes it is valid, as there isn't a comment in the standard
that you can't call in_list.remove with an element of in_list.

Bob

 

[matthias_k]

The code does compile, and apart from the empty list case (woops! forgot
that!) does what it is supposed to do, which is remove all copies of the
first element of the list.

However, it is my belief that this code isn't actually defined, as I
read that in_list.remove is supposed to take *it by reference, and there
is no need for it to make an internal copy. Therefore as soon as the
first element of in_list has been removed then the rest of the remove
function is getting the value of it from freed memory. The code happens
to work because the value of it is generally pulled into a register and
kept there.

First of all, it doesn't remove the first element, it removes all
elements which duplicate it (in your case the first one, if it should
happen to exist, but not the element itself).
Furthermore, it takes its argument by const reference, so there is no
way it will ever be overwritten. How should remove() lose the
information which elements to remove?

Honestly, I don't know how remove() internally works. But I think we can
have enough trust in the implementors of std::list that this function
does what it's supposed to =)

Regards,
Matthias

 

[Richard Herring]

I tend to agree with this analysis - but it would be more compelling for
a list, not of int, but of something with a destructor.

First of all, it doesn't remove the first element, it removes all
elements which duplicate it (in your case the first one, if it should
happen to exist, but not the element itself).

???

The first element, by definition, is equal to the value passed to
remove(), and will therefore get removed. If it were a user-defined type
rather than int, its destructor would be called. After that, all
attempts to use it are UB.

Furthermore, it takes its argument by const reference, so there is no
way it will ever be overwritten.

That reference is to the first element. What is that a reference to,
once remove() has erased the first element (and maybe called its
destructor)?

How should remove() lose the information which elements to remove?

By carrying around a reference to something which has been deleted.

Honestly, I don't know how remove() internally works. But I think we
can have enough trust in the implementors of std::list that this
function does what it's supposed to =)

Certainly. But are we supposing what they supposed?

 

[matthias_k]

Yes you are right of course, my bad. Late afternoon tiredness

 

[matthias_k]

By the way:

01010 /**
01011 * @brief Remove consecutive duplicate elements.
01012 *
01013 * For each consecutive set of elements with the same value,
01014 * remove all but the first one. Remaining elements stay in
01015 * list order. Note that this function only erases the
01016 * elements, and that if the elements themselves are pointers,
01017 * the pointed-to memory is not touched in any way. Managing
01018 * the pointer is the user's responsibilty.
01019 */
01020 void
01021 unique();

Just use this one

 

[Richard Herring]

By the way:

01010 /**
01011 * @brief Remove consecutive duplicate elements.
01012 *
01013 * For each consecutive set of elements with the same value,
01014 * remove all but the first one. Remaining elements stay in
01015 * list order. Note that this function only erases the
01016 * elements, and that if the elements themselves are pointers,
01017 * the pointed-to memory is not touched in any way. Managing
01018 * the pointer is the user's responsibilty.
01019 */
01020 void
01021 unique();

Just use this one

Did you miss the word "consecutive" above?

 

[matthias_k]

Did you miss the word "consecutive" above?

Good point. Nevermind.

 

[Bob Brian]

I tend to agree with this analysis - but it would be more compelling for
a list, not of int, but of something with a destructor.



???

The first element, by definition, is equal to the value passed to
remove(), and will therefore get removed. If it were a user-defined type
rather than int, its destructor would be called. After that, all
attempts to use it are UB.



That reference is to the first element. What is that a reference to,
once remove() has erased the first element (and maybe called its
destructor)?



By carrying around a reference to something which has been deleted.



Certainly. But are we supposing what they supposed?

I'm supposing that they don't assume they have to copy the reference
they recieve before they use it, and I'm not sure there is a way to go
from *it and get back to the iterator "it" (well actually in most
implementations there probably is, but the standard doesn't say there
is).. on the other hand it seems like perhaps the standard should say
something like "If any function during it's normal operation would
result in a change to any of its parameters, the results are undefined"
or something?" Or is it just assumed people have to figure that out for
themselves?

 

[msalters]

I was having a discussion with a friend about if the following is valid
code. I'm fairly sure it isn't allowed, but my friend seems to think
it's fine. It definatly appears to run fine in all the compilers we can
get access to.

void remove_duplicates(std::list<int>& in_list)
{
std::list<int>::iterator it = in_list.begin();
in_list.remove(*it);
}

Illegal. (and it doesn't do what the name suggests, either).

23.2.2.4/18 makes it clear that operator== is applied repeatedly,
possibly using the reference (not copied). 24.1.3 Table 74 makes
it clear that *it doesn't copy the value_type either. Hence, after
the first removal, the reference becomes unusable but .remove( )
may still assume it's valid.

One fix is obvious: in_list.remove(int(*it));
Just introduce a temporary which does remain valid.
HTH,
Michiel Salters