D言語にもDequeがほしい！
Dequeとその実装の話
Dequeについて
dequeは、double-ended queue（両端キュー）の略で、次のような操作ができるデータ構造のことです。
insertFront(value): 先頭への値の追加insertBack(value): 末尾への値の追加removeFront(): 先頭の値の削除removeBack(): 末尾の値の削除
先頭・末尾に対して、値の追加・削除ができます。
定番の実装方法は次の2つ。
1. 双方向連結リスト(doubly linked list)による実装
- 先頭・末尾の値の追加・削除が
O(1) - 途中の値の追加・削除が（参照をすでに持っていれば）
O(1) - 要素へのランダムアクセスが
O(n)
2. 動的配列による実装
- 先頭・末尾の値の削除が
O(1) - 先頭・末尾の値の追加が
amortized O(1)- 基本的に
O(1)だけど、メモリの再割り当て等で最悪計算量はO(n)
- 基本的に
- 途中の値の追加・削除が
O(n) - 要素へのランダムアクセスが
O(1)
競プロで単にdequeと言ったら動的配列の方のdequeを指すことが多い気がする。ぐぐったらarray dequeと言うらしい。
C++だと、双方向連結リストバージョンがstd::listで、動的配列バージョンがstd::dequeですかね。
で、D言語だとstd.container.dlistで双方向連結リストはあるけどarray dequeがない・・・
競プロで必要になってきたので実装しました。
実装方法
wikipediaによればarray dequeの実装方法は次の3つがあるみたい。
- リングバッファ(circular buffer)による実装。バッファが一杯になると領域を増やす。
- 動的配列を一つ用いる。配列の中心から前方・後方へキューの値を割り当てて、どちらか一方の端までいけば、サイズのより大きい配列へ再割り当てを行う。
- 小さな(静的)配列をポインタとしてもつ動的配列を用いる。値の追加にて、確保していた領域の先頭or末尾にいけば、新たな配列を加える。
3の実装、ページング方式みたいでおもしろい。C++のstd::dequeはこの実装方法が使われてるみたい（ちゃんと確かめてないので違ってるかも）
今回は2の方法を拡張して次のような実装をしました。
- 動的配列を2つ使う。
frontData、backDataとする。 - 前方に値が追加されれば
frontDataを伸ばしていく。逆に後方に値が追加されればbackDataを伸ばしていく。 - つまり内部のデータを1つの配列に変換すると
frontData.retro.array ~ backDataとなる。
領域の再割り当てなどの実装を手動でやるのが面倒だったのでD言語の動的配列の恩恵を授かろうという魂胆。
D言語の動的配列は拡大するとき、連続した次のヒープ領域が空き領域ならばO(1)、空き領域じゃなかったら配列全体をコピーして別の領域に再割当てするのでO(n)となります。よって、末尾への値の追加はamortized O(1)と思っていいんじゃないかな。
なので、上記のような単純な実装で大丈夫っしょという軽い気持ちで実装することにした。
ソースコード
下の方にunittestを書いてるのでだいたい使い方はわかると思う。
opSliceやopIndexAssignとかの演算子オーバーロードをしたことがなかったので少し勉強になった。
dequeを使うちょうど良さそうな問題があったので提出したらまともな速度が出たので実用上問題なさそう（ちなみにこの問題はdoubly linked listで機能的に十分なので例としては微妙）
その他
これ、ジャッジサーバーのコンパイラのバージョンが古いからかわからないけどなぜかコンパイルエラーが出る。UFCSを使わずに書くと通ったけどなんでエラーが出るんだろう・・・
