質問編集履歴
3
無駄な修正
test
CHANGED
File without changes
|
test
CHANGED
@@ -1,87 +1,44 @@
|
|
1
|
-
###前提・実現したいこと
|
1
|
+
### 前提・実現したいこと
|
2
|
-
|
3
2
|
以下のような要件を満たすコンテナがほしいです。
|
4
|
-
|
5
3
|
ざっくりいえば、ファイルシステムのような`ツリー構造`のコンテナです。
|
6
4
|
|
7
|
-
|
8
|
-
|
9
|
-
###要素の要件
|
5
|
+
### 要素の要件
|
10
|
-
|
11
6
|
- 0個以上の下位階層の要素を持てる。階層数の上限なし。
|
12
|
-
|
13
7
|
- 以下のような、先頭からの順序関係(位置)を持つ。ルート要素からの深さ優先で振られる。
|
14
8
|
|
15
|
-
|
16
|
-
|
17
9
|
|位置|データ|
|
18
|
-
|
19
10
|
|--:|:--|
|
20
|
-
|
21
11
|
|1|家康|
|
22
|
-
|
23
12
|
|2|----長男:信康(子供なし)|
|
24
|
-
|
25
13
|
|3|----次男:秀康(子供なし)|
|
26
|
-
|
27
14
|
|4|----三男:秀忠|
|
28
|
-
|
29
15
|
|5|--------家光|
|
30
|
-
|
31
16
|
|6|--------忠長|
|
32
|
-
|
33
17
|
|7|--------和子|
|
34
|
-
|
35
18
|
|8|--------正之|
|
36
|
-
|
37
19
|
|9|----四男:忠輝|
|
38
20
|
|
39
|
-
|
40
|
-
|
41
21
|
- 階層の展開(開いている/閉じている)状態と要素自体の有効(有効/無効)属性を持ち、外部からの操作によって切り替えることができる。
|
42
|
-
|
43
22
|
- 要素の挿入/削除、展開/有効の切替の処理時間は、速いにこしたことはない。がO(n)は勘弁。
|
44
23
|
|
45
|
-
|
46
|
-
|
47
|
-
###見える、見えないという状態
|
24
|
+
### 見える、見えないという状態
|
48
|
-
|
49
25
|
- 閉じている要素は、自身だけが見える。下位の要素は見えない。
|
50
|
-
|
51
26
|
- 無効の要素は、自身も下位の要素も見えない。
|
52
27
|
|
53
|
-
|
54
|
-
|
55
|
-
###走査(イテレータ)の要件
|
28
|
+
### 走査(イテレータ)の要件
|
56
|
-
|
57
29
|
- `見える要素のみ`または`展開、有効に関係なく全要素`の2種類の状態を対象とした走査ができる。
|
58
|
-
|
59
30
|
- `vecor`のように先頭からの任意の位置指定で要素を参照できる。走査時間は速いにこしたことはない。
|
60
|
-
|
61
31
|
- 順方向(先頭→末尾)の次の要素への移動は定数時間でできる。
|
62
32
|
|
63
|
-
|
64
|
-
|
65
33
|
以上の走査の各要件は、個別に満たせればよい(異なるイテレータでよい)
|
66
|
-
|
67
34
|
展開の切替や要素の挿入など操作された時点で、現イテレータは無効になってもよい。
|
68
35
|
|
69
|
-
|
70
|
-
|
71
|
-
###要件のまとめ
|
36
|
+
### 要件のまとめ
|
72
|
-
|
73
37
|
- 展開状態と有効属性から発生する「見えない」状態(要素)がある。
|
74
|
-
|
75
38
|
- (見えない要素は飛ばしつつ)先頭からの順序位置で走査できる。
|
76
39
|
|
77
|
-
|
78
|
-
|
79
40
|
という要件が、独自に実装するとなるとややこしいものになりそうですので、すでに実装されたライブラリなどご存じであれば教えてください。そのものズバリはないと思いますので、類似ライブラリの情報でもありがたいです。
|
80
|
-
|
81
41
|
また、`C++(STL)`での実装系が理想ですが、他言語でもかまいません。
|
82
42
|
|
83
|
-
|
84
|
-
|
85
|
-
###補足
|
43
|
+
### 補足
|
86
|
-
|
87
44
|
こんなコンテナいいな♪あったらいいな♪なノリの質問です。
|
2
順序関係についての説明を修正
test
CHANGED
File without changes
|
test
CHANGED
@@ -10,7 +10,7 @@
|
|
10
10
|
|
11
11
|
- 0個以上の下位階層の要素を持てる。階層数の上限なし。
|
12
12
|
|
13
|
-
- 以下のような、先頭からの順序関係(位置)を持つ。
|
13
|
+
- 以下のような、先頭からの順序関係(位置)を持つ。ルート要素からの深さ優先で振られる。
|
14
14
|
|
15
15
|
|
16
16
|
|
@@ -20,11 +20,11 @@
|
|
20
20
|
|
21
21
|
|1|家康|
|
22
22
|
|
23
|
-
|2|----信康|
|
23
|
+
|2|----長男:信康(子供なし)|
|
24
24
|
|
25
|
-
|3|----秀康|
|
25
|
+
|3|----次男:秀康(子供なし)|
|
26
26
|
|
27
|
-
|4|----秀忠|
|
27
|
+
|4|----三男:秀忠|
|
28
28
|
|
29
29
|
|5|--------家光|
|
30
30
|
|
@@ -34,7 +34,7 @@
|
|
34
34
|
|
35
35
|
|8|--------正之|
|
36
36
|
|
37
|
-
|9|----忠輝|
|
37
|
+
|9|----四男:忠輝|
|
38
38
|
|
39
39
|
|
40
40
|
|
1
重複部分を削除
test
CHANGED
File without changes
|
test
CHANGED
@@ -68,20 +68,6 @@
|
|
68
68
|
|
69
69
|
|
70
70
|
|
71
|
-
- `見える要素のみ`または`展開、有効に関係なく全要素`の2種類の状態を対象とした走査ができる。
|
72
|
-
|
73
|
-
- `vecor`のように先頭からの任意の位置指定で要素を参照できる。走査時間は速いにこしたことはない。
|
74
|
-
|
75
|
-
- 順方向(先頭→末尾)の次の要素への移動は定数時間でできる。
|
76
|
-
|
77
|
-
|
78
|
-
|
79
|
-
以上の走査の各要件は、個別に満たせればよい(異なるイテレータでよい)
|
80
|
-
|
81
|
-
展開の切替や要素の挿入など操作された時点で、現イテレータは無効になってもよい。
|
82
|
-
|
83
|
-
|
84
|
-
|
85
71
|
###要件のまとめ
|
86
72
|
|
87
73
|
- 展開状態と有効属性から発生する「見えない」状態(要素)がある。
|