Is std::map allowed to re-balance after read-only operations (like a Splay tree)

Question

Some binary tree data structures (such as Splay trees) will re-balance on reads to move recently accessed items toward the root, such that the subsequent look-up time may be reduced.

Are the standard containers (std::map, std::set) allowed to do this?

At least one concern is thread safety. Previously, I'd thought that as long as you were only doing read-only operations on standard containers, it was safe to do this from multiple threads without introducing mutexes/locks etc. Maybe I need to re-think this?

I know that typically red-black trees are used for the standard tree containers, and that these data structures aren't usually modified on reads. But would a hypothetical implementation that did modify be conforming?

My c++-standards-foo needs improvement, but I'm not sure whether the current standard addresses thread-safety for containers. Is this different in c++0x?

Answer 1

From the c++0x draft:

§23.2.2/1:

For purposes of avoiding data races (17.6.5.9), implementations shall consider the following functions to be const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at and, except in associative or unordered associative containers, operator[].

Note that c++03 does not say anything about multi-threading, but as you say, most implementations use RB-trees, which will not rebalance on a read operation.

Answer 2

Read functions on maps etc. are required to have a const function defined. Hence you get the guarantee that the object hasn't changed.

This is true both for C++11 ( 23.4.4.1 ) as well as C++03 ( 23.3.1 ).

23.2.2 of the new C++11 standard may be of special interest here:

1. For purposes of avoiding data races (17.6.5.9), implementations shall consider the following functions to be const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at and, except in associative or unordered associative containers, operator[].

2. Notwithstanding (17.6.5.9), implementations are required to avoid data races when the contents of the contained object in different elements in the same sequence, excepting vector<bool>, are modified concurrently.