Может ли std :: map перебалансироваться после операций только для чтения (например, Splay Tree)

Question

Некоторые структуры данных бинарного дерева (например, Splay trees) будут перебалансированы при чтениях, чтобы переместить недавно использованные элементы к корню, так что последующее время поиска может быть уменьшено.

Разрешено ли это делать стандартным контейнерам (std::map, std::set)?

По крайней мере, одной проблемой является безопасность потоков.Раньше я думал, что, пока вы выполняете операции только для чтения со стандартными контейнерами, было безопасно делать это из нескольких потоков без введения мьютексов / блокировок и т. Д. Может быть, мне нужно переосмыслить это?

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

Мой c ++ - standard-foo нуждается в улучшении, но я не уверен, касается ли текущий стандарт безопасности потоков для контейнеров.Это отличается в c++0x?

Answer 1

Из c++0x черновика:

§23.2.2 / 1:

Во избежание гонок данных (17.6.5.9) реализации должны учитывать следующие функции как const: начало, конец, rbegin, ренд, фронт, назад, данные, поиск, lower_bound, upper_bound, equal_range, at и кроме ассоциативных или неупорядоченных ассоциативных контейнеров, оператор [].

Обратите внимание, что c++03 ничего не говорит о многопоточности, но, как вы говорите, большинство реализаций используют RB-деревья, которые не будут перебалансированы при операции чтения.

Answer 2

Функции чтения на картах и ​​т. Д. Должны иметь определенную функцию const .Следовательно, вы получаете гарантию, что объект не изменился.

Это верно как для C ++ 11 (23.4.4.1), так и для C ++ 03 (23.3.1).

23.2.2 нового стандарта C ++ 11 может представлять особый интерес здесь:

1. Во избежание скачек данных (17.6.5.9), реализации должны рассматривать следующие функции как const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at и, за исключением ассоциативных или неупорядоченных ассоциативных контейнеров, operator [].

2. Несмотря на (17.6.5.9), реализации должны избегать гонок данных, когда содержимое содержимого объекта в разных элементах в одной и той же последовательности, за исключением vector<bool>, изменяется одновременно.