B>Если хотя бы 1 поток может модифицировать дэк, то вся работа с ним (с дэком) должна быть синхронизирована. Похоже, что у тебя как раз такая ситуация.
B>Да, и в этом случае итераторы тоже хранить нельзя, т.к. при модификациях дэка они инвалидируются.

Вроде для дека только удаление элементов инвалидирует итераторы, нет?