Is there any way to check if an iterator is valid?

Question

For two threads manipulating a container map for example, what the correct way to test whether an iterator still valid (for performance reason) ?
Or would be of only indirect way that this can be done. The sample code for this :

#define _SECURE_SCL 1
//http://msdn2.microsoft.com/en-us/library/aa985973.aspx
#define _SECURE_SCL_THROWS 1

#include "map"
#include "string"
#include "exception"
#include "iostream"

using namespace std;

void main(void)
{
    map<string, string> map_test;
    map<string, string>::iterator iter_map_test;

    map_test [ "AAAAA" ] = "11111";
    map_test [ "BBBBB" ] = "22222";
    map_test [ "CCCCC" ] = "33333";

    iter_map_test = map_test.find ("BBBBB");

    map_test.erase ("BBBBB");

    try
    {
        string value = (*iter_map_test).second;
    }
    catch ( exception & e )
    {
            cout << e.what() << endl;
    }
    catch ( ... )
    {
            cout << "generic exception." << endl;
    }
}

Answer 1

std::maps are not at all thread-safe. You'll end up with much worse problems than invalidated iterators, if you have more than one thread at a time modifying the same map. I don't even think you have a guarantee that you can read anything out of a map while it's being modified by another thread.

Some pages on the STL and threading:

• MSDN
• SGI
• GCC

Answer 2

If you know that one of the threads is only going to read the map while the other might be manipulating it, the simplest solution is to have the read-only thread clone the map and iterate over the clone.

(Caveat: I know Java's collection classes a lot better than I know STL, but this is how I'd do it in Java.)

Answer 3

If you implement a reader/writer solution, then you can have the writer set a flag that invalidates all the iterators of the readers.

http://en.wikipedia.org/wiki/Readers-writer_lock

I would not try to write to the map without synchronization, as Josh and Paul Tomblin mentioned.

Answer 4

If your STL does not offer a thread safe std::map, Intel's TBB offers a thread-safe concurrent_hash_map (pages 60 and 68).

Putting thread safety issues aside, std::map does guarantee that deletions do not invalidate iterators other than the one being deleted. Unfortunately there isn't a is_iterator_valid() method to validate iterators that you hold.

It may be possible to implement something like hazard pointers, and TBB has some workarounds to the problem as well.

Answer 5

Even you were able to tell if a pointer were valid, it would not solve your problem. You are sharing a single resource with no exlusivelty guarentee. Here is why it would fail.

It would fail in this thread sequence:

Thread0................................Thread1

Get iterator->it0

check that it0 is valid

.............................................Get Iterator->it1

.............................................Check that it1 is valid.

Erase (it0)

.............................................Erase (it1)

You can add a semaphore to access the shared resource.