前提・実現したいこと
以下のような要件を満たすコンテナがほしいです。
ざっくりいえば、ファイルシステムのようなツリー構造
のコンテナです。
要素の要件
- 0個以上の下位階層の要素を持てる。階層数の上限なし。
- 以下のような、先頭からの順序関係(位置)を持つ。ルート要素からの深さ優先で振られる。
位置 | データ |
---|---|
1 | 家康 |
2 | ----長男:信康(子供なし) |
3 | ----次男:秀康(子供なし) |
4 | ----三男:秀忠 |
5 | --------家光 |
6 | --------忠長 |
7 | --------和子 |
8 | --------正之 |
9 | ----四男:忠輝 |
- 階層の展開(開いている/閉じている)状態と要素自体の有効(有効/無効)属性を持ち、外部からの操作によって切り替えることができる。
- 要素の挿入/削除、展開/有効の切替の処理時間は、速いにこしたことはない。がO(n)は勘弁。
見える、見えないという状態
- 閉じている要素は、自身だけが見える。下位の要素は見えない。
- 無効の要素は、自身も下位の要素も見えない。
走査(イテレータ)の要件
見える要素のみ
または展開、有効に関係なく全要素
の2種類の状態を対象とした走査ができる。vecor
のように先頭からの任意の位置指定で要素を参照できる。走査時間は速いにこしたことはない。- 順方向(先頭→末尾)の次の要素への移動は定数時間でできる。
以上の走査の各要件は、個別に満たせればよい(異なるイテレータでよい)
展開の切替や要素の挿入など操作された時点で、現イテレータは無効になってもよい。
要件のまとめ
- 展開状態と有効属性から発生する「見えない」状態(要素)がある。
- (見えない要素は飛ばしつつ)先頭からの順序位置で走査できる。
という要件が、独自に実装するとなるとややこしいものになりそうですので、すでに実装されたライブラリなどご存じであれば教えてください。そのものズバリはないと思いますので、類似ライブラリの情報でもありがたいです。
また、C++(STL)
での実装系が理想ですが、他言語でもかまいません。
補足
こんなコンテナいいな♪あったらいいな♪なノリの質問です。
回答4件
あなたの回答
tips
プレビュー