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?
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.