You have repeatedly proven, and continue to do so, also by way of your exchanges with other commenters, that you're not asking out of curiosity. After all the previous comments we've exchanged, your line of asking was, "Which part of the STL are you expecting to be thread safe?" i.e. you were continuing to assume that I was somehow naive or uneducated. I did not assume anything to be thread safe in the way you imply (I used a simple mutex based approach to protect accesses).

If you'd been asking in good faith, the question would have been, "how did the concurrency problems look like"?

To which I'm going to answer, one of the bugs I hit was due to unexpected invalidation of a std::deque iterator. This came from being mislead to use std::deque as a quick & dirty implementation of a producer-consumer queue, and keeping iterators to track the read and write positions. Almost nobody has actually used std::deque (I hadn't either) but there is a common understanding (perhaps misunderstanding) that it is something like a chunk-queue. That vague understanding led me to believe that I can (and should, to avoid O(n) random access ) keep iterators after write operations. And using them that way did work for quite some time, I only hit confusing issues later.

(Actually random access is specified to be O(1) but this is even less widely known and makes std::deque a quite arcane data structure).

The problem with an abstract iterator interface here is that it doesn't help understanding what std::deque actually is. In case of std::deque, keeping read and write cursors works mostly fine, but it stops working (for example) if the read cursor pointed to the current end (was equal to deque::end) and the deque gets an append, which will invalidate the old end (read) cursor.

This is a good example of the complexity we have to deal with if we don't want to write a simple straightforward solution from scratch (chunk list) but instead code against something that we don't understand well. Not trying to use the STL but instead doing straightforward low level code would have made potential pitfalls more clear, and would have made bug search easier. It would have required less work to get the code to a working and maintainable state.

Another problem with std::deque is that the sizes of the chunks are not specified. They vary wildly between implementations, such that you can in practice get no performance guarantees from using std::deque, unless committing to a specific STL implementation (which is rarely practical). In fact, it is not even specified that deque uses something like chunks internally. It's too abstract to be useful.