List iterator and the next element

[Boon]

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]

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.

 

[Marcel Müller]

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

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


Marcel

 

[Leandro Melo]

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;
}

 

[Boon]

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.

 

[Bo Persson]

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