About invalidating iterators

STL containers have the problem that iterators can be invalidated when the container changes. Would it be possible for the container to announce that it has changed by adding a call has_changed()?

It is common to query empty() before certain operatio开发者_开发问答ns. If the container set a bool on operations that would affect iterators like insert() or erase() then it would be possible to query has_changed() before reusing an iterator.

Crazy?

EDIT Thanks for a bunch of good replies and food for thought. I wish I could award more than one winner.

Kinda crazy, if well intentioned.

I think the main problem with that is how does a container know when it has "unchanged"? In other words, something is erased and the "changed" flag is set. What is the precipitating event whereby it resets the flag because it is back to a normal or stable state? It is really the iterators rather than the container that are in an invalid state.

I think for this to work at all iterators would need to be much, much smarter than they currently are and operate more like Observers to the container. The container could send an event to registered iterators that it has changed and they could check their own state before attempting an operation. But even this has so many holes it would probably lead to a bigger mess than what you are trying to solve.

The (approximate) way fail-fast iterators work in Java is that the container increments a counter each time it changes. The iterators copy this counter on creation, and increment it each time the container is changed through them. If the iterator detects a mismatch, it throws an exception.

C++ has the exciting property that some operations invalidate some iterators on the container, but not others. For example, assuming sufficient space has been reserved vector::insert invalidates iterators after the insertion point, but not before.

Another difficult case is list::remove. This leaves all iterators valid except the one removed, and all copies of it.

As you can imagine, it would be pretty difficult to track this precisely. What happens in practice is that your implementation might offer debug options in which iterators will do their best to detect whether they're valid or not. This might depend on implementation details of whether they'll currently "work", though, rather than on whether the standard guarantees that they still work.

It would be possible to do something in C++ similar to the "version number" in Java, but it would give false positives of iterators which appear invalid but in fact are valid.

The rules of when iterators are invalidated are clear enough that if you pay by the rules, you shouldn't need to ask the container when its containers are invalidated.

Moreover, iterators aren't always invalidated at the same time. Removing an element from the middle of a vector only invalidates that element and the one after it. But iterators pointing to the beginning of the vector stay valid.

In lists, iterators are generally only invalidated when the specific node they point to is destroyed.

So you can't ask the container whether or not your iterator is valid.

Common standard library implementations have the option to enable additional runtime checks similar to what you're requesting, although the implementation is more complex (it has to be, in order to be correct), and it hurts performance.

It would be inefficient, because the container would need to A) provide yet another data field and B) update it accordingly. The STL, however, was thought up in an attempt to do the impossible and combine efficiency with abstraction. (And it succeeded, I should add.)

If you need to keep references into a changing container, either use one that doesn't invalidate iterators (std::list, std::set) or keep indexes into a std::vector.

This is technically possible, and MSVC implements 'checked iterators' (http://msdn.microsoft.com/en-us/library/aa985965.aspx) that provide a similar functionality. While you don't get notification when the iterator becomes invalid, and you can't directly query the state (that I know of), an exception is thrown and/or call invalid_parameter depending on how the build is configured.

However, it's decidedly non-standard and hits performance significantly. It is useful for debugging.

Would it be possible for the container to announce that it has changed by adding a call has_changed()?

I think, yes, it can be implemented. Here is one very simple attempt (not so elegant, but still):

bool has_changed(std::vector<int> &v)
{
    static std::map<void*, size_t> has_changed_info;
    void *ptr = &v;
    std::map<void*, size_t>::iterator it = has_changed_info.find(ptr);
    if (it == has_changed_info.end())
    {
       has_changed_info[ptr] = v.capacity();  
       return false;
    }
    if ( it->second != v.capacity() )
    {
        it->second = v.capacity();
        return true;
    }
    return false;
}

Testing code as:

int main() {
        std::vector<int> v;
        has_changed(v);
        for ( int i = 0 ; i < 100 ; ++i )
        {
            v.push_back(i);
            if (has_changed(v))
                  cout << "changed at " << i << endl;
        }       
        return 0;
}

Output (GCC-4.3.4):

changed when inserting i = 0
changed when inserting i = 1
changed when inserting i = 2
changed when inserting i = 4
changed when inserting i = 8
changed when inserting i = 16
changed when inserting i = 32
changed when inserting i = 64

Online Demo : http://www.ideone.com/QmO5q