Thread safety of a std::deque

Question

Could I let one thread hold a reference (or iterator) to the first element of a std::deque while another is adding/removing elements at the back, but never touching the first element?

I know I can use a mutex to lock the entire data structure, but I was wondering since adding/removing elements at the back never invalidate iterators at the front (assuming back != front) if doing this could work.

EDIT

Here's an example that shows a race condition (the assertion fails) with clang-15 on a mac os. Interestingly, the same example but where insertions/removals are done at the back and the element is read at the front seems to work.

#include <deque>
#include <thread>
#include <cassert>
#include <chrono>

int main()
{
  std::deque<int> deque;
  deque.push_back(42);
  auto thread1 = std::thread([&](){
    for (auto i = 0u; i < 1000000000; ++i)
    {
      auto& j = deque.back();
      using namespace std::chrono_literals;
      std::this_thread::sleep_for(10ms);
      assert(j == deque.back());
    }
  });
  auto thread2 = std::thread([&](){
    for (auto i = 0u; i < 1000000000; ++i)
      if (deque.size() == 1)
        deque.push_front(43);
      else
        deque.pop_front();
  });
  thread1.join();
  thread2.join();
}

very related/dupe: https://stackoverflow.com/questions/50626405/is-writing-stddeque-at-different-memory-locations-concurrently-thread-safe — NathanOliver, Mar 15 '23 at 20:38
Yep, I fell into that trap a while ago in production code. Iterators definitely not safe (if the container is modified). I think this question requires a specific example of what problem OP is trying to solve. Simply storing references to stuff contained in the deque is fine. — paddy, Mar 15 '23 at 20:48
I have a function that returns a reference to the first element that is called in one thread. Concurrently, other thread is removing elements at the back, but never touching the first element. — mvc, Mar 15 '23 at 20:55
If the container itself is modified (insert, erase, remove etc) then the operations are not thread safe see the answers to the proposed dup above. — Richard Critten, Mar 15 '23 at 20:56
I can't really wrap my mind about how can there be a race condition since the first element is never reallocated by removals at the back. But anyway, being unsafe explains all sorts of weird things I am seeing in the code. — mvc, Mar 15 '23 at 21:08
Damn, found another duplicate. Sorry. https://stackoverflow.com/questions/41001062/are-concurrent-calls-to-emplace-back-and-operator-from-stddeque-thread-s?rq=1 — mvc, Mar 15 '23 at 21:33
@mvc `std::deque` has an internal vector of pointers, If another thread modifies the internal vector, then the iterators can't advance to the "next" item safely. — Mooing Duck, Mar 15 '23 at 23:00
@mvc I missed that you included iterators in your question. I have updated my answer: You should be aware that _iterators_ are invalidated _always_ when adding elements to a `std::deque`. — user17732522, Mar 15 '23 at 23:12

user17732522 · Accepted Answer · 2023-03-16T09:56:53.347

The shown program is not guaranteed to be free of data races and has therefore undefined behavior. See end of this answer.

Could I let one thread hold a reference (or iterator) to the first element of a std::deque while another is adding/removing elements at the back, but never touching the first element?

Yes, accessing different elements of a standard library container does not in itself cause data races (each element is at a different memory location) and removing/ading elements at the beginning or end from a std::deque does not invalidate references to other elements, nor is a container's member function allowed to touch elements of the container other than required by its specification.

Of course you can't delete the referenced object or have two threads access the same element of the container unsynchronized.

Also when using .erase/.emplace/etc to erase/add elements other than at the beginning or end of the std::deque or if you use shrink_to_fit, then all references are invalidated and using the reference is already forbidden in the single-threaded scenario.

Also for iterators, any operation adding elements (whether at the ends or not) will invalidate them. In that case it is also UB whether single-threaded or multi-threaded.

Also accessing/modifying iterators is not guaranteed to be data race free when the container is (potentially) modified unsynchronized (because the iterator has read-only access to the container), whether that is adding or removing elements. That applies to all standard library containers.

All of the above applies only to storing and reusing a reference/iterator. There is never a guarantee that there is no data race when calling a modifying member function in one thread unsynchronized with calling any member function in another thread, as you are doing in your example by calling back in the first thread.

Thanks. I've edited my question with an example showing a race condition. Am I misunderstanding your answer and is my example flawed in some other way? — mvc, Mar 16 '23 at 09:23
@mvc Calling `back()` and a modifying member function (e.g. `push_front`) without synchronization is not safe. You can't call a modifying member function in one thread and another member function in another thread without synchronization. Your original question didn't include that. The assumption was that you are storing only a reference or iterator and never call a member function in the first thread while the second thread modifies the `std::deque`. — user17732522, Mar 16 '23 at 09:33
I see. If I reverse the example (call front() and do push_back()) but instead of front() use deque[0], would that be safe? — mvc, Mar 16 '23 at 09:35
@mvc Also note that iterators are really never data race safe when the container is being modified. (Added to answer.) — user17732522, Mar 16 '23 at 09:46

Thread safety of a std::deque

1 Answers1