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

Answer 1

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.