Back to General and Gameplay Programming

[STL] List iterators

General and Gameplay Programming Programming

Started by CWizard May 04, 2003 08:07 AM

19 comments, last by CWizard 20 years, 11 months ago

CWizard

127

Author

May 04, 2003 08:07 AM

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]

Holy Fuzz

213

May 04, 2003 08:10 AM

I''m assuming you could create a copy of the iterator, then increment/decrement THAT.

CWizard

127

Author

May 04, 2003 08:21 AM

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

Kylotan

10,510

May 04, 2003 10:43 AM

CWizard

127

Author

May 04, 2003 10:58 AM

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

Qw3r7yU10p!

819

May 04, 2003 05:56 PM

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

Zipster

2,420

May 04, 2003 06:09 PM

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

CWizard

127

Author

May 04, 2003 06:19 PM

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.