Is this valid code?

Discussion in 'C++' started by Bob Brian, Jan 24, 2005.

  1. Bob Brian

    Bob Brian Guest

    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);
    }
    Bob Brian, Jan 24, 2005
    #1
    1. Advertising

  2. Bob Brian

    matthias_k Guest

    Bob Brian wrote:
    > 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, Jan 24, 2005
    #2
    1. Advertising

  3. Bob Brian

    matthias_k Guest

    matthias_k wrote:
    > Bob Brian wrote:
    >
    >> 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


    // 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, Jan 24, 2005
    #3
  4. Bob Brian

    matthias_k Guest

    matthias_k wrote:
    > 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()).
    matthias_k, Jan 24, 2005
    #4
  5. Bob Brian

    Bob Brian Guest

    matthias_k wrote:
    > Bob Brian wrote:
    >
    >> 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.
    >


    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
    Bob Brian, Jan 24, 2005
    #5
  6. Bob Brian

    matthias_k Guest

    Bob Brian wrote:
    >> Bob Brian wrote:

    > 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
    matthias_k, Jan 24, 2005
    #6
  7. In message <ct3047$rio$00$-online.com>, matthias_k
    <> writes
    >Bob Brian wrote:
    >>> Bob Brian wrote:

    >> 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
    >>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.


    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?

    --
    Richard Herring
    Richard Herring, Jan 24, 2005
    #7
  8. Bob Brian

    matthias_k Guest

    Yes you are right of course, my bad. Late afternoon tiredness :D
    matthias_k, Jan 24, 2005
    #8
  9. Bob Brian

    matthias_k Guest

    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 :)
    matthias_k, Jan 24, 2005
    #9
  10. In message <ct36tc$ni6$02$-online.com>, matthias_k
    <> writes
    >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?

    --
    Richard Herring
    Richard Herring, Jan 24, 2005
    #10
  11. Bob Brian

    matthias_k Guest

    Richard Herring wrote:
    > Did you miss the word "consecutive" above?
    >


    Good point. Nevermind. :D
    matthias_k, Jan 24, 2005
    #11
  12. Bob Brian

    Bob Brian Guest

    Richard Herring wrote:
    > In message <ct3047$rio$00$-online.com>, matthias_k
    > <> writes
    >
    >> Bob Brian wrote:
    >>
    >>>> Bob Brian wrote:
    >>>
    >>> 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 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.

    >
    >
    > 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?
    >


    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? :)
    Bob Brian, Jan 24, 2005
    #12
  13. Bob Brian

    msalters Guest

    Bob Brian wrote:
    > 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
    msalters, Jan 25, 2005
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    443
    Adam P. Jenkins
    Jan 18, 2005
  2. Eric Biller

    Embedding VRML-Objects in valid code

    Eric Biller, Nov 13, 2003, in forum: HTML
    Replies:
    6
    Views:
    3,753
    Toby A Inkster
    Nov 14, 2003
  3. Gianni Mariani

    is this code valid ?

    Gianni Mariani, May 17, 2004, in forum: C++
    Replies:
    5
    Views:
    361
    Gianni Mariani
    May 19, 2004
  4. Replies:
    64
    Views:
    1,252
    Dave Thompson
    Dec 20, 2004
  5. Any C code are valid C++ code?

    , Dec 10, 2004, in forum: C Programming
    Replies:
    67
    Views:
    1,168
    Dave Thompson
    Dec 20, 2004
Loading...

Share This Page