Traversing a bidirectional iterator back to the first element

Question

There is something that I can't quite get my head around with bidirectional iterators.

Going forward through the collection is ok:

auto it = set.begin();
while (it != set.end())
{
  // Do something
  it++;
}

end() is the element after the last element. So let's say I want to go in reverse using the same iterator from the end:

if(it == set.end())
{
    it--; // Now points to last element
}
while(it != set.begin())
{
  // Do something
  it--;
}

But this last loop is flawed because begin() is the first element and we want to include it in processing. So how do we iterate back to (and including) the first element with a bidirectional iterator?

---

To provide context ...

The user iterates forward one by one. So they might be on the end() or any element before the end. Then, they decide they want to go backwards. Thus the sanity check since if we are at the end we must decrement by one. Now the user goes backwards one by one. Until they reach the first element.

I asked a similar question yesterday but deleted it since I did not grasp some of the concepts which I now have corrected for forward iteration.

Answer 1

Before starting this process, you need to be clear on what it is supposed to be. Your if statement suggests that you're not clear on that.

If it is supposed to point at the first element to be processed in the sequence, then the only way it will ever be the end element is if the list is empty (ie: end and begin are the same). In that case, decrementing the iterator is wrong.

To handle this case, your code should look like this:

if(it != set.end())
{
  for(; it != set.begin(); --it)
  {
    //Do stuff with *it.
  }
}

If it is supposed to point to the element after the first element to process, then your code would look like this:

while(it != set.begin())
{
  --it;
  //Do stuff with *it
}

The user iterates forward one by one. So they might be on the end() or any element before the end. Then, they decide they want to go backwards.

That user needs to figure out what they mean. When they provide the iterator to the code doing reverse processing, they are the ones who need to be clear on what the value of that iterator means. It either is always part of the range, or it never is part of the range.

It shouldn't be "it's part of the range, unless its the end iterator, then it isn't part of the range".