0

Assuming I have a vector containing shared_ptrs to items:

std::vector<std::shared_ptr<Foo>> items;

Is it safe to iterate through items in that vector in one thread:

thread1()
{
   for( auto foo : items )
   {
      foo->something();
   }
}

While another thread removes items from that vector?

thread2()
{
   items.erase( std::remove_if( items.begin(), items.end(), 
      [](std::shared_ptr<Foo>& foo){
         return foo->shouldBeRemoved();
      }));
}

So in other words: If thread2 removes an item while thread1 is accessing it, will the vector itself remain valid / corruption-free?

I'm well aware, in this example, that its up to me to make sure Foo::something() and Foo::shouldBeRemoved() does not cause any problems should both threads hit the same ptr at the same time.

And I know if the vector directly contains instances of Foo() thread 2 could delete something while thread 1 once attempting to use it. The use of the shared_ptr in theory should prevent the referenced object from being deleted while in use, so its the iterators / integrity of the vector that are in question.

Update: For anybody else with similar questions struggling to fine good quick-reference documentation on this kind of thing, this seems to cover it for my purpose:

http://en.cppreference.com/w/cpp/container#Thread_safety

Iterator operations (e.g. incrementing an iterator) read, but do not modify the underlying container, and may be executed concurrently with operations on other iterators on the same container, with the const member functions, or reads from the elements. Container operations that invalidate any iterators modify the container and cannot be executed concurrently with any operations on existing iterators even if those iterators are not invalidated.

SO answer summing up iterator invalidation rules: Iterator invalidation rules

Community
  • 1
  • 1
Brian McFarland
  • 9,052
  • 6
  • 38
  • 56
  • 4
    `erase` invalidates iterators, `remove_if` assigns the elements all over the place...why on earth would you think this could possibly be safe? – T.C. Jan 22 '16 at 00:31
  • I'm fairly new to C++11 STL.... other high-level lanuages, (e.g. Python's lists) have data structures that let you get away with this kind of thing. Are there any *different* STL containers where this *would* be safe? – Brian McFarland Jan 22 '16 at 00:42
  • btw... I know I could do this with a std::mutex by just preventing *any* concurrent access to the vector entirely, but what I'm after is the ability to insert/remove things to/from the "list" *without* invalidating the entire collection. Does std::list fair any better, or is it across-the-board true that modifying a container from T2 invalidates iterators in T1? – Brian McFarland Jan 22 '16 at 00:48
  • 2
    @BrianMcFarland: Python wouldn't actually work correctly if you were removing multiple items in one thread while iterating in another. It wouldn't segfault, and you wouldn't get races freeing memory, but neither would you get remotely predictable or consistent behavior. The CPython reference interpreter charges you for this protection by preventing CPU bound threads from doing work simultaneously via the GIL, global interpreter lock. Lower level languages are trying to squeeze out speed, and protection of this sort would slow non-threaded cases unacceptably. – ShadowRanger Jan 22 '16 at 01:16
  • Read the docs for the various STL types. Deleting from the beginning or end of a [`std::deque`](http://en.cppreference.com/w/cpp/container/deque) won't invalidate iterators pointing to the remaining elements, [`std::list`](http://en.cppreference.com/w/cpp/container/list) iterators are invalidated only if the specific element they're currently pointing to is deleted. But in a threaded scenario, knowing that the iterator in some other thread is or is not pointing to a given element isn't trivial; you wouldn't be able to use these guarantees without locks in a threaded case. – ShadowRanger Jan 22 '16 at 01:19
  • After giving some thought to how I might implement said mythical collection, "isn't trivial" is an understatement. I'm thinking: 1) the collection would keep pointers back to any outstanding iterators, 2) the iterators destructor would need to remove itself from said parent container's iterator list, 3) collection mutators must iterate over the iterator references and update them as needed. 4) all mutators on both require locking. For my usage, blocking add/inserts on the (slow) method that needs to iterate is probably ok, so wrapping all operations in a std::lock_guard works for now. – Brian McFarland Jan 22 '16 at 16:06
  • Modifying an object while accessing it in another thread, without any synchronisation? Why should that ever be valid? – n. m. could be an AI Jan 22 '16 at 16:41
  • @n.m. - I get it. STL containers lack internal synchronization. But is that really such a crazy thing to ask about in a language that, in big scheme of things, only recently got "native" threading support? What value does your comment add to the conversation by insinuating that it is? I could just as easily ask why *shouldn't* a complete std library in a lang w/ good multithreading include data structures of this nature? And "because its hard" is not a good answer.... – Brian McFarland Jan 22 '16 at 16:58
  • Modifying **any** object while accessing it in another thread is not allowed without synchronisation. Standard containers are no exception. Why should they be? Do you propose to add internal synchronisation to all objects? – n. m. could be an AI Jan 22 '16 at 17:10

1 Answers1

2

No! The iterator in thread1 becomes invalid if another thread adds or removes a element from items.

This is similar to items.remove returning a new and valid iterator so you can continue iteration while removing elements from a collection.

iceisfun
  • 21
  • 2
  • It provides a perfectly good answer! I would maybe phrase it differently; the behaviour is entirely undefined – pm100 Jan 22 '16 at 18:26