Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > List iterator and the next element

Reply
Thread Tools

List iterator and the next element

 
 
Boon
Guest
Posts: n/a
 
      02-12-2009
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] = i+1;
for (i=0; i < N; ++i)
for (j=i+1; j < N; ++j)
printf("(%d,%d)\n", v[i], 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.
 
Reply With Quote
 
 
 
 
Boon
Guest
Posts: n/a
 
      02-12-2009
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] = i+1;
>> for (i=0; i < N; ++i)
>> for (j=i+1; j < N; ++j)
>> printf("(%d,%d)\n", v[i], 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.
 
Reply With Quote
 
 
 
 
Marcel Müller
Guest
Posts: n/a
 
      02-12-2009
Boon wrote:
> for (it2=it1+1; it2 != v.end(); ++it2) // ILLEGAL
> ^^^^^


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


Marcel
 
Reply With Quote
 
Leandro Melo
Guest
Posts: n/a
 
      02-12-2009
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] = i+1;
> * *for (i=0; i < N; ++i)
> * * *for (j=i+1; j < N; ++j)
> * * * *printf("(%d,%d)\n", v[i], 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






 
Reply With Quote
 
Boon
Guest
Posts: n/a
 
      02-17-2009
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.
 
Reply With Quote
 
Bo Persson
Guest
Posts: n/a
 
      02-17-2009
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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Find next element in multimap not matching current element Key, How to? Victor Bazarov C++ 15 08-16-2009 08:26 PM
List iterator assignment fails, assert iterator not dereferencable David Bilsby C++ 5 10-09-2007 02:05 PM
Get next element given a certain element? Kourosh Javascript 1 06-08-2006 02:23 AM
How to convert from std::list<T*>::iterator to std::list<const T*>::iterator? PengYu.UT@gmail.com C++ 6 10-30-2005 03:31 AM
CurrentElement->next = CurrentElement->next->next (UNDEFINED?) Deniz Bahar C Programming 2 03-09-2005 12:45 AM



Advertisments