Здравствуйте, Garrett, Вы писали:

G>Безопасно ли добавлять / удалять из двух потоков одновременно, при условии что вставка и удаление происходят в непересекающихся областях? Такое у меня чувство, что ничего страшного происходить не должно.

Сделайте критические секции — в чём проблема-то?
Зачем нужен лишний геморой для проверки, что эти области действительно не пересекаются.