一些二叉树数据结构(例如 Splay 树)将在读取时重新平衡以将最近访问的项目移向根，这样可以减少后续查找时间。
标准容器(std::map、std::set)是否允许这样做？
至少一个问题是线程安全。以前，我认为只要您只对标准容器执行只读操作，从多线程执行此操作是安全的，而无需引入互斥锁/锁等。也许我需要重新考虑一下？
我知道通常红黑树用于标准树容器，并且这些数据结构通常不会在读取时被修改。但是，确实修改过的假设实现是否符合要求？
我的 c++-standards-foo 需要改进，但我不确定当前标准是否解决了容器的线程安全问题。这在 c++0x 中有什么不同吗？
最佳答案
来自 c++0x 草案:
§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[].
请注意，c++03 并未提及任何关于多线程的内容，但正如您所说，大多数实现都使用 RB 树，它不会在读取操作时重新平衡。
关于c++ - std::map 是否允许在只读操作后重新平衡(如 Splay 树)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7225914/