1

バランスの取れた BST と二重にリンクされたリストがあるデータ構造を作成しようとしています。リンクされたリストは BST よりも小さいため、常に BST の要素のサブセットのみを保持します。LL の各ノードはポイントしますノードがリンクされたリストに存在する場合、BST ノードはその LL ノードを指し、それ以外の場合は null を格納します。

このデータ構造を作成するために、BST に std::set< data, std::list::iterator > を使用し、双方向リンク リストに std::list< data,std::set::iterator > を使用する予定でした。これを行うために、他の各要素イテレータへの参照を保存しても問題ありません。セットがバランスを取り、リンクされたリストが保持するイテレータを無効にする可能性はありますか?アプローチに他の問題はありますか?

STL やその他のライブラリを使用して C++ でこれを行うにはどうすればよいですか?

(このデータ構造を作成して LRU キャッシュを作成したかった)

4

2 に答える 2

2

std::setセットに新しい要素を挿入しても反復子は有効なままであるため、反復子をリストに保持する場合に問題が発生することはありません。セットから要素を消去すると、それらの要素への反復子は (明らかに) 無効になりますが、他の反復子は有効なままです。

于 2013-05-13T13:27:35.100 に答える
0

C++ の二重リンク リストを使用したバランスのとれた二分探索木

ここにある：

http://archive.gamedev.net/archive/reference/programming/features/TStorage/index.html

于 2013-07-26T03:12:57.377 に答える