What's the cleanest way to walk and unwalk a std::vector using iterators?

Question

I have a situation where I'm marching through a vector, doing things:

std::vector<T>::iterator iter = my_list.begin();

for ( ; iter != my_list.end(); ++iter )
{
  if ( iter->doStuff() )   // returns true if successful, false o/w
  {
    // Keep going...
  }
  else
  {
    for ( ; iter != m_list.begin(); --iter )  // ...This won't work...
    {
      iter->undoStuff();
    }
  }
}

Under normal conditions - assuming everything goes well - I march all the way to my_list.end() and end the loop successfully.

However, if something goes wrong while I'm doing stuff, I want to be able to undo everything - basically retrace my steps back to the very beginning of the vector, undoing everything one at a time in reverse order.

My problem is that when I get to my_list.begin() - as shown in the nested for loop - I'm really not done yet because I still need to call undoStuff() on my first element in the list. Now, I could just make the final call outside of the loop, but this seems a little unclean.

The way I see it, I'm only done when I get to my_list.rend(). However, I can't compare a std::vector::iterator to a std::vector::reverse_iterator.

Given what I'm trying to do, what's the best choice of iterator-type / loop combination?

Answer 1

I'm a little rusty when it comes to STL vectors, but would it be possible to create a std::vector::reverse_iterator from your initial iterator? Then you would only need to start at the last item you were at when going forward, and would be able to compare it to my_list.rend() to make sure that the first item is processed.

Answer 2

There is of course no reason not to use the vectors operator[]() if that makes your code clearer, simpler and/or more efficient.

Answer 3

While using reverse iterators via rbegin() and rend() works nicely, unfortunately I find that converting between reverse and non-reverse iterarotrs tends to be quite confusing. I can never remember without having to go through a logic-puzzle exercise whether I need to increment or decrement before or after the conversion. As a result I generally avoid the conversion.

Here's the way I'd probably code your error handling loop. Note that I'd think that you wouldn't have to call undoStuff() for the iterator that failed - after all, doStuff() said it didn't succeed.

// handle the situation where `doStuff() failed...

// presumably you don't need to `undoStuff()` for the iterator that failed
// if you do, I'd just add it right here before the loop:
//
//     iter->undoStuff();

while (iter != m_list.begin()) {
    --iter;
    iter->undoStuff();
}

Answer 4

Without using a reverse_iterator, you can walk backwards this way:

while(iter-- != m_list.begin())
{
    iter->undoStuff();
}

Though this creates a copy of iter, the cost shouldn't be too great. You can refactor for better speed:

while(iter != m_list.begin())
{
    --iter;
    iter->undoStuff();
}

Answer 5

It depends on what your doStuff() function does, and how important performance is in your context. If possible, it would probably be clearer (ie - easier for the reader) to work on a copy of your vector, and only if everything is okay, swap the vectors.

std::vector<Foo> workingCopy;
workingCopy.assign(myVector.begin(), myVector.end());

bool success = true;
auto iter = workingCopy.begin();
for( ; iter != workingCopy.end() && success == true; ++iter )
    success = iter->doStuff();

if( success )
    myVector.swap(workingCopy);

Answer 6

You need to use rbegin() to get a reversible iterator.

Personally I still prefer

for (int i=0;i<vecter.size();i++) { }

Answer 7

Ok, I'll go out on a limb here..

std::vector iterator iter = my_list.begin();
bool error = false;

while(iter != my_list.end())
{
  error = !iter->doStuff();
  if(error)
    break
  else
    iter++;
}

if(error)
do
{
  iter->undoStuff();
  iter--;
} 
while(iter != my_list.begin())

Answer 8

This is what I call over engineering, but it is so much fun

// This also can be done with adaptators I think
// Run DoStuff until it failed or the container is empty
template <typename Iterator>
Iterator DoMuchStuff(Iterator begin, Iterator end) {
  Iterator it = begin;
  for(; it != end; ++it) {
    if(!*it->DoStuff()) {
      return it;
    }
  }
  return it;
}

// This can be replaced by adaptators
template <typename Iterator>
void UndoMuchStuff(Iterator begin, Iterator end) {
  for(Iterator it = begin; it != end; ++it) {
    it->UndoStuff();
  }
}

// Now it is so much easier to read what we really want to do
typedef std::vector<MyObject*> MyList;
typedef MyList::iterator Iterator;
typedef MyList::reverse_iterator ReverseIterator;
Iterator it = DoMuchStuff(my_list.begin(), my_list.end());
if(it != my_list.end()) {
  // we need to unprocess [begin,it], ie including it
  UndoMuchStuff(ReverseIterator(1+it), ReverseIterator(my_list.begin()));
}

Answer 9

This can be done with a reverse_iterator:

bool shouldUndo(false);
std::vector::iterator iter(my_list.begin()), end(my_list.end());
for ( ; iter != end && !shouldUndo; ++iter )
{
  shouldUndo = iter->doStuff();   // returns true if successful, false o/w
}
if (shouldUndo) {
  reverse_iterator<std::vector::iterator> riter(iter), rend(my_list.rend());
  //Does not call `undoStuff` on the object that failed to `doStuff`
  for ( ; riter != rend; ++riter )
  {
    iter->undoStuff();
  }
}