読み取り専用操作（Splayツリーのような）の後にstd :: mapの再調整が可能です

Question

一部のバイナリツリーデータ構造（Splayツリーなど）は、最近アクセスした項目をルートに向かって移動させるために、その後のルックアップ時間を短縮することができる。

標準容器（std::map、std::set）はこれを許可されていますか？

少なくとも1つの懸念は、スレッドの安全性です。以前は、標準のコンテナでのみ読み取り専用の操作を行っていれば、mutex/locksなどを導入しなくても、複数のスレッドからこの操作を行うことができたと思いました。これを再考する必要があるかもしれません。

通常、標準のツリーコンテナには赤黒のツリーが使用されており、これらのデータ構造は通常読み取り時に変更されないことがわかります。しかし、修正を加えた仮想的な実装が適合するだろうか？

私のC++標準fooは改善が必要ですが、現在の標準がコンテナのスレッドセーフティを扱っているかどうかはわかりません。 c++0xでこれは違いますか？ c++0xドラフトから

Answer 1

：

§23.2.2/ 1：

データ競合を回避する目的のために（17.6.5.9）、実装がconstのように、以下の機能を考慮しなければならない：開始、連合または順序付けられていない連想配列の演算子[]を除く、end、rbegin、rend、front、back、data、find、lower_bound、upper_bound、equal_range、atおよび

マルチスレッドについては何も言わないが、ほとんどの実装では、読み取り操作で再調整しないRBツリーが使用されていることに注意してください。

Answer 2

constファンクションが定義されている必要があります。したがって、オブジェクトが変更されていないという保証が得られます。

これは、C++ 11（23.4.4.1）とC++ 03（23.3.1）の両方に当てはまります。

（17.6.5.9）のデータ競合を回避する目的のために

1. 、実装は 考慮しなければならない：新しいC++ 11標準の

   23.2.2

   は、ここでは特別な関心であってもよいです以下の関数をconst、begin、end、rbegin、 レンダリング、フロント、バック、データ、検索、lower_bound、upper_bound、equal_range、 at、および連想型または順序付けられていない連想型コンテナを除く operator []。 vector<bool>を除いて同じ順序で 異なる要素に含まれるオブジェクトの内容は、 が同時に変更されたとき

2. かかわらず（17.6.5.9）が、実装は、データ競合を回避するために を必要としています。