やあ子供たち、元気にしてたかな。おじさんは環境のせいかもうすっかり精神エネルギーがすり減らされて日記も書く気力が失せてしまっていた感じだよ。子供たちは元気にしていたかい。子供は風の子だからな。スノボとか行ってちゃんと遊んでるか。
今日は要素リストの各要素をめぐるループ処理の途中で、リストへの要素追加案件やあるいはリストからの要素削除案件が発生するような、そういうぐるぐるまわる一連の処理をどう設計すればいいのかというお話だ。
こういう話はどこにでもあるわけなんだね。いくつかうまい例えを考えてみたよ。
- しょっちゅう旅行をするのだが、各旅行中に旅行の日程が変わったり、延びたり、短くなったりする。
- 毎日洗濯をするのだけれども、洗濯機が洗濯物の量を認識して適量の水量で洗濯スタートした後に洗濯物を洗濯槽に投げ込んだり、そこから取り出したりする。
- 年度がスタートしてるのに新入りがどんどん入ってきたり、退職していったりしまくることを許している。
どうだろう？イメージつかめただろうか。
このような問題は「list delete within loop」でググるとこれで困っている人の書き込みをたくさん見ることができるわけだけれども、その中の何人かの人たちが言っているように、おじさんも「リスト要素の加減は、それを回しているループの中では決して行わないこと」という設計理念を貫きたいと考えている一人だよ。
もちろんいろんなコンテナのerase()メソッドが反復子を返してくれたりするしループをまわしながら要素の加減をやりくりするテクニックも実際存在するわけだけれども、たとえばリスト要素が適切な順番でソートされていて、equal_range() の中の要素について処理をしてるようなループだった場合はとても複雑なしかけを仕組まなくてはならなくなる。
上のたとえ話でいくと、
- 旅行中に日程は絶対に変えない。今の旅行を終えて次の旅行に行くまでの間にしっかり日程の長さを調整する。
- 洗濯機が動き出したら洗濯槽の中の洗濯物を出し入れはしない。入れ忘れた分は明日の洗濯にまわす。
- 年度ごとにその年度の定員をしっかり定める。既定人数以上は受け付けない。また、退職のタイミングは必ず年度末とする。
さて、それはいい。ループの中で要素の加減は行わない。方針は決まった。
おじさんが今日書きたいのはここからだよ。この場合、要素エントリやリストにはどんなデータ構造や機能があればいいのかという話になってくるよ。
まず要素側には削除フラグが必要だ。リストのループ中で削除扱いと決まったものについては処理する必要はないし、削除されたので処理されては困る場合もある。なのでこの要素は削除されましたとわかるように、各要素には削除フラグを設ける。そして今から処理しようとする要素の削除フラグがついていたならその要素については処理をスキップする。ループの外側において、削除フラグのついた要素をremove_ifなどで一気に本リストから削除しよう。
次に新規追加待ち要素用のリストだ。ループ中ではリストの本体には要素を追加できないので、別途設置したこの新規追加待ちリストに要素を追加しておき、ループの外であることが保証されている箇所で一気にこの追加待ちリストの内容を本リストの方にオフにした削除フラグとともに登録する。それが完了次第、追加待ちリスト自体をクリアする。
また、要素の削除案件が発生した際にそれがまだ本リストに追加されていない場合もある。つまり削除案件が発生した要素がまだ新規追加待ちリストにある場合だ。これを放置すると、削除フラグがオフにされて本リストの方にいずれは登録されてしまうことになるので、要素の削除案件が発生した場合は必ず、対象要素が追加待ちリストの中にないかまで調べ、もしあればその時点で追加待ちリストからその要素の登録を削除しよう。追加待ちリストはループで回しているわけではないので、その要素削除は問題なく行える。
最後に、処理としては以上の三つ、ループと、ループ外追加処理と、ループ外削除処理が直列に三つブロックに並んで記述する形になるのが自然だが、この一連の処理自体が再帰的に呼ばれる可能性がある場合は、再帰のネスト階層をカウントし、ネストしていない最上レベルにいないのであれば、ループ外加減処理（追加敢行と削除敢行の２ブロック）を行ってはならない。
さ、ちょっと長くなったけどどうかな？簡単そうで結構めんどくさい実装になってくるのでちょっとメモさせてもらったぞ。じゃ、今日はこの辺で！
(以上の話の、より実践的な実装についての未来日記はここ)
