Iterator from both ends of a Vector

Question

Hi,

I have a vector of IntRect: vector.

How can I iterate from both ends of the list and stop the iterator when the iterator intersects?

vector<IntRect>::iterator itr = myVector.begin();
  vector<IntRect>::reverse_iterator revItr.rbegin();

  for (; /*check itr and revItr does not intersect, and itr and revItr do not end */ ; ++itr, ++revItr) {
    IntRect r1 = *itr;
    IntRect r2 = *revItr;

    // do something with r1 and r2

  }

Thank you.

Answer 1

Your iterators point to the same thing if &(*itr) == &(*revItr)

Assuming nobody has done something stupid and overloaded operator& on IntRect.

Answer 2

You can use base function on the reverse iterator and compare the result with your forward iterator.

Remember that if you're moving both iterators, they will never be equal if the sequence has odd number of elements. You have to check the equality twice in each iteration.

Answer 3

I would replace the second (reverse) iterator with a regular one and have that initialised to --myVector.end(). Instead of incrementing it, decrement it and compare the iterator values.

Answer 4

if(!myVector.empty()) {
    for(vector<IntRect>::iterator forwards = myVector.begin(), 
                                  backwards = myVector.end()-1;
        forwards < backwards;
        ++forwards, --backwards) {

            // do stuff
    }
}

I think you need to check empty() with that implementation - suspect that end()-1 isn't defined if the vector is empty. I haven't used it before, but Dinkumware STL at least has operator < defined for vector iterators and it appears to do something sensible.

Also note that you need to check <, not just equality - that takes care of the (common) case where your vector has an even number of entries and the two iterators would step past one another.

Answer 5

None of the answers that I've seen account for the two iterators "passing in the night."

vector<IntRect>::iterator forward = myVector.begin(), backward = myVector.end();

while (forward != backward)
{
    ++forward;

    // at this point they could be equal
    if (forward == backward)
        break;

    --backward;
}