Одновременная итерация по карте при вставке, как это небезопасно

Question

Примечание: я знаю, что это небезопасно и не определено стандартом, чтобы посмотреть, определено ли оно моим компилятором или безопасно на практике.

Я перебираю диапазон карты в одном потоке, потенциально вставляя в другой поток

// thread 1:
for(auto it = map.begin(); it != map.end(); ++it){
    // it's okay if "it" is out of order, repeats an element, or skips an element
    // it's bad  if "it" can skip map.end() or turn to mush (invalid iterator)
}

// thread 2:
map[Key(...)] = Type(...); // insertions are extremely rare but inevitable

Это небезопасно, но ... как небезопасно? Эта карта служит подсказкой по оптимизации для облегчения конкуренции за потоки, поэтому сама по себе она не может способствовать этому конфликту. Если возможными исходами являются только то, что вставленный элемент может быть пропущен или что он будет считывать элементы не по порядку или дважды, это приемлемо и ничего не сломает.

Повернет ли это итераторы в суп или приведет к пропуску map.end()? Это только два результата, которые могут разрушить мою жизнь.

Answer 1

Да, эти результаты могут произойти абсолютно, и хуже .

Когда вы вставляете в карту, происходят различные внутренние операции. Это не просто [] и =: под ним работает целый алгоритм, возможно, включающий операции перебалансировки! (Обратитесь к вашим старым университетским заметкам по управлению древовидной структурой для получения дополнительной информации.)

Нет никаких гарантий относительно того, к чему приведет «наблюдение» карты в ходе такого алгоритма, и стандарт очень ясно показывает, что ваша программа будет иметь неопределенное поведение . Это двоякая проблема: вы не только можете столкнуться с практическими проблемами с картой, но и ваш компилятор знает, что никакая четко определенная программа не может попасть в эту ситуацию, и может выполнить оптимизацию, основываясь на предположении, что вы не сделали этого. «т . Теперь все чертовски далеко, потенциально в коде, даже не связанном с вашей картой .

Изменение карты в одном потоке и чтение из нее в другом без синхронизации самоубийство, просто и понятно. Не пытайтесь перехитрить компилятор / реализацию: просто код для контракта.

Answer 2

Здесь я частично снимаю с бедра, но, скажем, базовая коллекция реализуется путем выделения фиксированного размера заранее, тогда, когда потребуется увеличить, она потенциально может выделить, например. На 50% больше, чтобы избежать повторных небольших перераспределений. Затем старые записи коллекции будут перемещены во вновь выделенную память, а старая коллекция освобождена.

Если вы выполняете итерацию такой коллекции при вставке, «следующий» итератор может в итоге удерживать указатель на освобожденное место.