How to iterate over std::list, while other thread remove elements from it in C++?

Question

I have a multi-thread program, where one thread is iterating over a list only reading values and the second is removing some elements from it:

std::list<Type> items;

void* Thread1(void*)
{
    while(true)
        for(auto item = items.begin(); item != items.end(); ++item) {
            cout << item << std::endl;
            sleep(1);
        }
}

void* Thread2(void*)
{
    for(auto item = items.begin(); item != items.end(); ++item) {
        if(/*check some condition on item*/) {
            items.erase(item);
            break;
        }
    }
}

I can't put mutex over whole for loop in Thread1, because the list is pretty big and it will cause a big slow-down of the whole program.

Also, Thread2 will be called multiple times and we can't be sure when it will happen and Thread1 must look over the list all the time.

Is there a thread-safe way to iterate over a list whose size can change in real-time and not get a segmentation fault, undefined behavior, or potentially skip some elements?

Answer 1

Calling any other member function of the list unsynchronized with a call to erase (or any other modifying function) is not guaranteed to be free of a data race and therefore results in undefined behavior. Aside from that there is the obvious issue that the iterator in the other thread may be pointing to exactly the element that is being erased, against which std::list does not offer any protection or detection.

If you do not want to take locks, then you'll need to implement your own lock-free list which uses atomic pointers instead to achieve the protection from data races. The standard library does not have any containers of that kind. They all require external locking on modification.