List iterator and the next element

Discussion in 'C++' started by Boon, Feb 12, 2009.

  1. Boon

    Boon Guest

    Hello everyone,

    Consider a list of integers: 1 2 3 4 5

    I want to print every pair (v(i),v(j)) where i < j

    With a plain old array, I'd write something along the lines of

    #include <stdio.h>
    #define N 5
    int main(void)
    {
    int i, j, v[N];
    for (i=0; i < N; ++i) v = i+1;
    for (i=0; i < N; ++i)
    for (j=i+1; j < N; ++j)
    printf("(%d,%d)\n", v, v[j]);
    return 0;
    }

    but I need to be able to remove elements in the middle of the list, and
    reinsert them later. Therefore, I thought I'd use an std::list.

    #include <list>
    #include <cstdio>
    #define N 5
    typedef std::list<int> int_list;
    int main(void)
    {
    int i;
    int_list v;
    int_list::iterator it1, it2;
    for (i=0; i < N; ++i) v.push_back(i+1);
    for (it1=v.begin(); it1 != v.end(); ++it1)
    for (it2=it1+1; it2 != v.end(); ++it2) // ILLEGAL
    ^^^^^
    printf("(%d,%d)\n", *it1, *it2);
    return 0;
    }

    AFAIU, an std::list iterator is not a Random Access Iterator, thus
    "it1+1" is invalid. Is this correct?

    How can I say "initialize it2 to something that points to the next
    element after that pointed to by it1" ?

    For the moment, I've settled for

    for (it2=it1, ++it2; it2 != v.end(); ++it2)

    but I find it ugly.

    Regards.
    Boon, Feb 12, 2009
    #1
    1. Advertising

  2. Boon

    Boon Guest

    Victor Bazarov wrote:

    > Boon wrote:
    >
    >> Consider a list of integers: 1 2 3 4 5
    >>
    >> I want to print every pair (v(i),v(j)) where i < j
    >>
    >> With a plain old array, I'd write something along the lines of
    >>
    >> #include <stdio.h>
    >> #define N 5
    >> int main(void)
    >> {
    >> int i, j, v[N];
    >> for (i=0; i < N; ++i) v = i+1;
    >> for (i=0; i < N; ++i)
    >> for (j=i+1; j < N; ++j)
    >> printf("(%d,%d)\n", v, v[j]);
    >> return 0;
    >> }
    >>
    >> but I need to be able to remove elements in the middle of the list,
    >> and reinsert them later. Therefore, I thought I'd use an std::list.
    >>
    >> #include <list>
    >> #include <cstdio>
    >> #define N 5
    >> typedef std::list<int> int_list;
    >> int main(void)
    >> {
    >> int i;
    >> int_list v;
    >> int_list::iterator it1, it2;
    >> for (i=0; i < N; ++i) v.push_back(i+1);
    >> for (it1=v.begin(); it1 != v.end(); ++it1)
    >> for (it2=it1+1; it2 != v.end(); ++it2) // ILLEGAL
    >> ^^^^^
    >> printf("(%d,%d)\n", *it1, *it2);
    >> return 0;
    >> }
    >>
    >> AFAIU, an std::list iterator is not a Random Access Iterator, thus
    >> "it1+1" is invalid. Is this correct?
    >>
    >> How can I say "initialize it2 to something that points to the next
    >> element after that pointed to by it1" ?
    >>
    >> For the moment, I've settled for
    >>
    >> for (it2=it1, ++it2; it2 != v.end(); ++it2)
    >>
    >> but I find it ugly.

    >
    > Wrap it in a function:
    >
    > template<class It> It next_after(It const& it) {
    > It next_it = it;
    > return ++next_it;
    > }
    >
    > and do
    >
    > for (it2 = next_after(it1); it2 != v.end(); ++it2)
    >
    > . Is that better?


    I do find it slightly better. Thanks for the suggestion.

    I was also wondering about element removal and insertion.

    Suppose I want to remove the second element, then reinsert it.

    AFAIU, the following code is incorrect, right?

    int_list::iterator it = v.begin(); // point to 1
    ++it; // point to 2
    int backup = *it; // save element 2
    v.erase(it) // remove element 2
    v.insert(it, backup); // NOT VALID AFAIU

    v.erase(it) invalidates it which means I can no longer use it for anything?

    Regards.
    Boon, Feb 12, 2009
    #2
    1. Advertising

  3. Boon wrote:
    > for (it2=it1+1; it2 != v.end(); ++it2) // ILLEGAL
    > ^^^^^


    for (it2=it1; ++it2 != v.end();)


    Marcel
    Marcel Müller, Feb 12, 2009
    #3
  4. Boon

    Leandro Melo Guest

    On 12 fev, 14:04, Boon <root@localhost> wrote:
    > Hello everyone,
    >
    > Consider a list of integers: 1 2 3 4 5
    >
    > I want to print every pair (v(i),v(j)) where i < j
    >
    > With a plain old array, I'd write something along the lines of
    >
    > #include <stdio.h>
    > #define N 5
    > int main(void)
    > {
    >    int i, j, v[N];
    >    for (i=0; i < N; ++i) v = i+1;
    >    for (i=0; i < N; ++i)
    >      for (j=i+1; j < N; ++j)
    >        printf("(%d,%d)\n", v, v[j]);
    >    return 0;
    >
    > }
    >
    > but I need to be able to remove elements in the middle of the list, and
    > reinsert them later. Therefore, I thought I'd use an std::list.
    >
    > #include <list>
    > #include <cstdio>
    > #define N 5
    > typedef std::list<int> int_list;
    > int main(void)
    > {
    >    int i;
    >    int_list v;
    >    int_list::iterator it1, it2;
    >    for (i=0; i < N; ++i) v.push_back(i+1);
    >    for (it1=v.begin(); it1 != v.end(); ++it1)
    >      for (it2=it1+1; it2 != v.end(); ++it2) // ILLEGAL
    >               ^^^^^
    >        printf("(%d,%d)\n", *it1, *it2);
    >    return 0;
    >
    > }
    >
    > AFAIU, an std::list iterator is not a Random Access Iterator, thus
    > "it1+1" is invalid. Is this correct?
    >
    > How can I say "initialize it2 to something that points to the next
    > element after that pointed to by it1" ?
    >
    > For the moment, I've settled for
    >
    >      for (it2=it1, ++it2; it2 != v.end(); ++it2)
    >
    > but I find it ugly.


    The following is essentially the same thing as yours. But some
    developers might think it's clearer.

    //...
    #include <iterator>

    int main(void)
    {
    //...

    for (it1=v.begin(); it1 != v.end(); ++it1)
    {
    it2 = it1;
    std::advance(it2, 1);
    for (; it2 != v.end(); ++it2)
    {
    printf("(%d,%d)\n", *it1, *it2);
    }
    }

    return 0;
    }

    --
    Leandro T. C. Melo
    Leandro Melo, Feb 12, 2009
    #4
  5. Boon

    Boon Guest

    Victor Bazarov wrote:

    > Boon wrote:
    >
    >> I was also wondering about element removal and insertion.
    >>
    >> Suppose I want to remove the second element, then reinsert it.
    >>
    >> AFAIU, the following code is incorrect, right?

    >
    > Right.
    >
    >> int_list::iterator it = v.begin(); // point to 1
    >> ++it; // point to 2
    >> int backup = *it; // save element 2
    >> v.erase(it) // remove element 2

    >
    > Very simple. Do this instead
    >
    > it = v.erase(it); // remove element 2 (now 'it' refers to former 3)
    >
    > Now 'it' is valid (again) and the old value is not needed anymore.


    If I understand correctly, given a valid iterator "it" then the
    following code is always a NOP.

    val = *it;
    toto.insert(toto.erase(it), val);

    My problem is that I want to remove /two/ elements from the list, do
    some work, and reinsert the two elements (the list must be restored to
    its original condition).

    It seems I have to make a special case when I remove two consecutive
    elements versus when I remove two elements separated by other elements.

    What do you think?

    Regards.
    Boon, Feb 17, 2009
    #5
  6. Boon

    Bo Persson Guest

    Boon wrote:
    > Victor Bazarov wrote:
    >
    >> Boon wrote:
    >>
    >>> I was also wondering about element removal and insertion.
    >>>
    >>> Suppose I want to remove the second element, then reinsert it.
    >>>
    >>> AFAIU, the following code is incorrect, right?

    >>
    >> Right.
    >>
    >>> int_list::iterator it = v.begin(); // point to 1
    >>> ++it; // point to 2
    >>> int backup = *it; // save element 2
    >>> v.erase(it) // remove element 2

    >>
    >> Very simple. Do this instead
    >>
    >> it = v.erase(it); // remove element 2 (now 'it' refers to former
    >> 3) Now 'it' is valid (again) and the old value is not needed
    >> anymore.

    >
    > If I understand correctly, given a valid iterator "it" then the
    > following code is always a NOP.
    >
    > val = *it;
    > toto.insert(toto.erase(it), val);
    >
    > My problem is that I want to remove /two/ elements from the list, do
    > some work, and reinsert the two elements (the list must be restored
    > to its original condition).
    >
    > It seems I have to make a special case when I remove two consecutive
    > elements versus when I remove two elements separated by other
    > elements.
    > What do you think?
    >


    Depending on what you do with the list, perhaps you can use a filter
    that ignores the two elements during the operation? Something in line
    with copy_if and replace_if among the standard algorithms.


    Bo Persson
    Bo Persson, Feb 17, 2009
    #6
    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. Deniz Bahar
    Replies:
    2
    Views:
    446
    Andrey Tarasevich
    Mar 9, 2005
  2. Replies:
    6
    Views:
    625
    Jim Langston
    Oct 30, 2005
  3. David Bilsby
    Replies:
    5
    Views:
    2,024
    David Bilsby
    Oct 9, 2007
  4. Victor Bazarov
    Replies:
    15
    Views:
    1,169
    Vaclav Haisman
    Aug 16, 2009
  5. Kourosh
    Replies:
    1
    Views:
    113
    Kourosh
    Jun 8, 2006
Loading...

Share This Page