一些二叉树数据结构（例如Splay树）将在读取时重新平衡以将最近访问的项目移向根，从而可以减少后续查找时间。
标准容器（std::map, std::set）是否允许这样做？
至少一个问题是线程安全。以前，我认为只要您只在标准容器上执行只读操作，就可以安全地从多个线程执行此操作而无需引入互斥锁/锁等。也许我需要重新考虑一下？
我知道通常红黑树用于标准树容器，并且这些数据结构通常不会在读取时修改。但是，修改后的假设实现是否符合要求？
我的 c++-standards-foo 需要改进，但我不确定当前标准是否解决了容器的线程安全问题。这有什么不同c++0x吗？
从c++0x草案中：
§23.2.2/1：
为避免数据竞争 (17.6.5.9)，实现应将以下函数视为 const：begin、end、rbegin、rend、front、back、data、find、lower_bound、upper_bound、equal_range、at 和，除了关联或无序的关联容器，operator[]。
请注意，这c++03并没有说明多线程，但正如您所说，大多数实现都使用 RB-trees，它不会在读取操作时重新平衡。
地图等上的读取函数需要定义一个const函数。因此，您可以保证对象没有更改。
对于 C++11 ( 23.4.4.1 ) 和 C++03 ( 23.3.1 ) 都是如此。
新的 C++11 标准的23.2.2可能在这里特别感兴趣：
为避免数据竞争 (17.6.5.9)，实现应将以下函数视为 const：begin、end、rbegin、rend、front、back、data、find、lower_bound、upper_bound、equal_range、at 和，除了关联或无序的关联容器，operator[]。
尽管有（17.6.5.9），当同时
vector<bool>修改相同序列中不同元素中包含的对象的内容时，需要实现来避免数据竞争。