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;
    }
}

More info from guru: Three Guidelines for Effective Iterator Usage http://www.aristeia.com/Papers/CUJ_June_2001.pdf — lsalamon, Mar 23 '09 at 18:41

Eclipse · Accepted Answer · 2009-01-12T17:23:22.990

9

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:

edited Jan 12 '09 at 17:23

answered Jan 12 '09 at 16:39

Eclipse

44,851
20
112
171

The standard makes no guarantees about thread safety at all, but individual implementations may offer stronger guarantees. So check the docs to see if the implementation you're using is threadsafe. – jalf Jan 12 '09 at 16:53

Max Lybbert · Answer 2 · 2009-12-22T23:32:45.310

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.

score 2 · Answer 3 · answered Jan 12 '09 at 16:39

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.)

score 2 · Answer 4 · answered Jan 12 '09 at 16:46

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.

score 1 · Answer 5 · answered Apr 17 '09 at 15:17

1

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.

answered Apr 17 '09 at 15:17

The detail is exact that! if one thread erase it0 how detect what it1 is no longer valid. – lsalamon Apr 18 '09 at 00:17
That is the whole issue, at the time it1 checks the iterator it is valid, so just checkng validity will not work. You will have to use a semaphore to lock the resource while it is being modified. – Apr 19 '09 at 00:35
Locking resource access does not guarantee anything, you must use a flag to indicate that the iterator should be discarded. Was that I had to implement. – lsalamon Apr 22 '09 at 01:16
This is what semaphores are for. If you lock a resource, another thread would have to wait until that resource is free before it requested the iterator and it would always be valid. – Apr 23 '09 at 01:10

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

5 Answers5

Linked