6

一部のバイナリ ツリー データ構造 ( Splayツリーなど) は、読み取り時に再調整して、最近アクセスしたアイテムをルートに移動し、その後のルックアップ時間を短縮できるようにします。

標準コンテナ ( std::map、std::set) はこれを行うことができますか?

少なくとも 1 つの懸念事項は、スレッドの安全性です。以前は、標準コンテナーで読み取り専用操作のみを実行している限り、ミューテックス/ロックなどを導入せずに複数のスレッドからこれを実行しても安全だと考えていました。

通常、標準ツリー コンテナーには赤黒ツリーが使用され、これらのデータ構造は通常、読み取り時に変更されないことがわかっています。しかし、変更を加えた仮想の実装は準拠しているのでしょうか?

私の c++-standards-foo には改善が必要ですが、現在の標準がコンテナーのスレッド セーフに対応しているかどうかはわかりません。これは で違いc++0xますか?

4

2 に答える 2

8

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 and、連想を除くまたは順序付けられていない連想コンテナー、operator[]。

マルチスレッドについては何も言っていないことに注意してくださいc++03。しかし、あなたが言うように、ほとんどの実装では RB ツリーが使用されます。

于 2011-08-29T04:05:48.773 に答える
3

マップなどの読み取り関数は、const関数を定義する必要があります。したがって、オブジェクトが変更されていないという保証が得られます。

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

新しい C++11 標準の23.2.2は、ここで特に興味深いかもしれません。

  1. データ競合 (17.6.5.9) を回避する目的で、実装は次の関数を const と見なす必要があります: begin、end、rbegin、rend、front、back、data、find、lower_bound、upper_bound、equal_range、at and、連想を除くまたは順序付けられていない連想コンテナー、operator[]。

  2. (17.6.5.9)にもかかわらず、 を除く同じシーケンス内の異なる要素に含まれるオブジェクトの内容が同時にvector<bool>変更される場合、実装はデータ競合を回避する必要があります。

于 2011-08-29T04:26:56.490 に答える