Archived

This topic is now archived and is closed to further replies.

CWizard

[STL] List iterators

Recommended Posts

I've stumbled across an annoying problem with STL lists and their iterators, and I'm not sure how to work around them. The problem is that I want to access the next and previous elements of an element, but lists do not have random access iterators. To illustrate:
std::list<int> ints;
for(std::list<int>::iterator i = ints.begin(); i != ints.end(); i++) {
    // I want to access the neighbor elements like this.
    // In this case, nevermind the out-of-bounds access.
    if(*(i - 1) == *i);
    if(*(i + 1) == *i);
}
  
This would work fine with a vector, as the random access iterator has the - and + operators overloaded. I need to use list because its iterators aren't invalidated when inserting/erasing elements. I can, of course, us post-/pre- inc-/decrement, but that modifies the iterator itself. How should I go about accessing the iterator's neighbors in a clean way? I'm sure I'm missing something obvious, because my mind isn't as sharp as it could be right now.
[edited by - CWizard on May 4, 2003 9:09:38 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Holy Fuzz
I''m assuming you could create a copy of the iterator, then increment/decrement THAT.
Yes, but that I doubt is a clean way. Wouldn''t you need to something like this:

if(*(--std::list<int>::iterator(i)) == *i);

Share this post


Link to post
Share on other sites
Thanks, kind of awkward, but about what I had in mind doing myself. I''ll keep it in mind, for this particular problem I worked around it in this way:

std::list<int> ints;
std::list<int>::iterator i_prev;
std::list<int>::iterator i_next;
for(std::list<int>::iterator i = ints.begin(); i != ints.end(); i++) {
(i_prev = i)--;
(i_next = i)++;
}

Share this post


Link to post
Share on other sites
I''m not really sure what was awkward about the boost solution


  
// write this once and only once

// you won''t have to repeat code with possible mistakes

// and it is obvious to read

template <class T>
T next(T x) { return ++x; }

template <class X>
T prior(T x) { return --x; }



  
std::list<int> ints;
std::list<int>::iterator i_prior;
std::list<int>::iterator i_next;
for(std::list<int>::iterator i = ints.begin(); i != ints.end(); ++i) {
i_prior = prior(i);
i_next = next(i);
}

Share this post


Link to post
Share on other sites
I''m not sure if you can do this (never tried), but if you''re feeling brave, you can derive your own list class and simply overload the iterator objects to include addition and subtraction operators. That way it works for more than just adjacent elements. You could implement it as a loop, using the existing increment/decrement code inside.

The only thing you''d have to take of is if it gets to the bounds of the list, you set it equal to either end() or begin(), depending which end it went off, and then break.

Just my 2 cents

Share this post


Link to post
Share on other sites
petewood: True, its wasn''t very awkward; I think I misunderstood it when I saw it first. It will be useful next time. I needed this when throwing together a code piece for this thread: http://www.gamedev.net/community/forums/topic.asp?topic_id=154639.

Zipster: Yup, that was what I primarily had in mind of doing, I just wasn''t sure exactly how to overload it. I''ll maybe try it later, as it could be useful to have.

Share this post


Link to post
Share on other sites
quote:
Zipster: Yup, that was what I primarily had in mind of doing, I just wasn't sure exactly how to overload it. I'll maybe try it later, as it could be useful to have.

It depends on which implementation you are using, but just browsing the VC6 implementation it doesn't seem too difficult.

Off the top of my head, maybe something like this:

      
iterator operator+(unsigned int i)
{
iterator tmp = *this;

for(; i; --i)
{
if( (tmp = _Acc::_Next(tmp)) == end() )
break;
}

return tmp;
}

The biggest hack is forcing an unsigned integer, and therefore assuming it only goes forward. Otherwise, you might get an expression like this:

(i + (-5))

And all is lost! You will have to figure out a way around that. My suggestion is to include some conditional logic inside the operator functions themselves, but it's up to you. It might make the functions a bit bloated. Hmmm.

[edited by - Zipster on May 4, 2003 8:58:16 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Digitalfiend
In general you shouldn''t derive from STL containers as they do not define a virtual destructor.

That''s only an issue if you expect to use pointers to the iterator''s base class, which I think would not be an issue for what the OP is trying to do.


How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
It depends on which implementation you are using, but just browsing the VC6 implementation it doesn't seem too difficult.

Off the top of my head, maybe something like this:

/ code /
Yes, but what I had trouble bending my head around was where to overload it; my own iterator class? My own list class? Both?
quote:
The biggest hack is forcing an unsigned integer, and therefore assuming it only goes forward.
Something like this may be possible: (note, this is before-coffee for me )

iterator operator-(int i)
{
return *this + (-i);
}

iterator operator+(int i)
{
iterator tmp = *this;
if(i > 0) while(i--) tmp++;
else while(i++) tmp--;
return tmp;
}

// or

iterator operator+(int i)
{
iterator tmp = *this;
if(i > 0) {
while(i--) {
tmp++;
if(tmp == end()) tmp = begin();
}
}
else {
while(i++) {
if(tmp == begin()) tmp = end();
tmp--;
}
}
return tmp;
}





[edited by - CWizard on May 5, 2003 5:41:39 AM]

Share this post


Link to post
Share on other sites
I don''t like the first block, because all subtraction is turned into addition. If you are doing some regular subtraction like this:

(i - 2)

Then it turns into an addition of -2, which is just a bit ackward for iterator logic IMO. Not only that, but there aren''t any bounds checks in the first block. This solution would defintely work though, just add the bounds checking.

The second block on the other hand is much nicer - to me at least. You just have to duplicate what you have for the subtraction operator, change the logic a bit, and it should work.

However I disagree with the wrap-around logic. It could cause undesired behavior. You''d be better off just breaking the loop if it reaches the boundaries.

Share this post


Link to post
Share on other sites
Ugh, post-increments all over the place

Why not this?


list< int >::iterator it = L.begin();
list< int >::iterator prev = it; --prev;
list< int >::iterator next = it; ++next;
list< int >::const_iterator end = L.end();

for( ; it != end; ++it, ++prev, ++next ) {
// whatever
}


You'll have to do something funny with the begin() - 1 case, but you get the picture.

Regards,
Jeff

[edited by - rypyr on May 5, 2003 3:58:30 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
I don't like the first block, because all subtraction is turned into addition. If you are doing some regular subtraction like this:

(i - 2)

Then it turns into an addition of -2, which is just a bit ackward for iterator logic IMO.
Are you sure about that? I know well that in the processor, subtraction is simply addition by the two-complemented (negated) value. I also see that the compiler could "optimize" by doing that to a hard coded number. But, I don't think the compiler does that with a - b, as that would add an extra instruction to negate b before adding it to a.

I think, but I'm not sure, that the compiler would violate standard behaviour if it arbitrary exchanged operators, escpecially when they are overloaded.
quote:
However I disagree with the wrap-around logic. It could cause undesired behavior. You'd be better off just breaking the loop if it reaches the boundaries.
Perhaps. What I was coding worked with polygons, so in this case it was desirable that the vector was "cyclic", so that end() == begin() and (begin() - 1) == (end() - 1).
quote:
Original post by rypyr
Ugh, post-increments all over the place
Sorry, bad habits.

[edited by - CWizard on May 5, 2003 4:35:16 PM]

Share this post


Link to post
Share on other sites
What I meant was that all subtraction turns into addition since your subtraction operator invokes the addition operator. I just didn't like the logic behind adding -2 to an iterator. It's like saying, "go forward by -2"

[edited by - Zipster on May 5, 2003 5:26:28 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

  
list<int>::iterator c, prev, next;
list<int>::const_iterator end(L.end());

c = prev = next = L.begin();

if (c == end) {
// empty list

f();
} else if (next == end) {
// single element list; no previous or next elements

f(c++);
} else {
// at least two elements; must handle first, middle, and last element cases

// first case; no previous element

f(c++, ++next);

// middle case; previous and next elements

for (; next != last; ++c, ++prev, ++next)
f(c, prev, next);

// last case; no next element

f(c++, prev++);
}


No subtraction, just pre- and post-increments. Partially stolen from rypyr.

Share this post


Link to post
Share on other sites
you can use the advance() function to move forward or backward but it will have bad complexity if a nonradom iterator is used. Take a look at the "STL Docs" link in Kylotan sig.


    
list<int>::iterator i = L.begin();
advance(i, 2);//2 is to move forward 2 spaces, -2 will backward




-----------------------------
"There are ones that say they can and there are those who actually do."

"...u can not learn programming in a class, you have to learn it on your own."





[edited by - cMADsc on May 5, 2003 7:58:44 PM]

Share this post


Link to post
Share on other sites