使うのか分からないリングバッファのライブラリを書いた
C++でコンテナクラスを一から書いたことがなかったので、ちょっと書いてみようと思ったんですけど、競プロで使いそうなデータ構造は目についたものは一通りライブラリ化してあったので、使うのかは分からないけど、リングバッファを書いてみました。
リングバッファとは
ガバガバな説明をすると配列で最後尾の次の要素にアクセスしようとすると、最前列の要素にアクセスできるような循環している配列です。
要するに、普段要素数nの配列arrayに対して、任意のiを使って
array[i%n]
みたいなことをしてるやつのことです。
このままだと、負数を与えてしまうと、環境依存でセグフォったり、そもそも書くのがめんどくさかったりするので、コンテナクラスにしてみます。
実装した機能
- O(1)で要素数を超える添え字は循環してアクセス
- O(1)で負の添え字を使っても循環してアクセス
- O(1)で起点をずらす(array[0]で参照できるオブジェクトを切り替えられる)
- O(1)で起点を元に戻す
- O(NlogN)でソート
- O(1)で逆順にする
- O(N)で全要素をダンプ
このあたりがあると使いやすいのかなぁと思って実装しました。
他にも思いついたら追加していくかも。
実装はこんな感じになりました(575)
作ってみて
気がついたら200行を超えてて長大な感じになりました。
template<typename T>をタイプしすぎて疲れた。
ちゃんとしたverifyを行なっていないので、もしかしたらバグってるかもしれません。
あとbegin()とend()はイテレータを返しません。
起点をずらす処理ができるのは便利な瞬間が訪れるかもしれません
dump()はDEBUGシンボルはdefineされているときだけ出力されるので、普段は#define DEBUGしておいて、ジャッジ提出時には#define DEBUGをコメントアウトすると使いやすいと思います。
あと地味にO(1)で逆順にできるので、何回も逆順にする必要がある問題とか(そんな問題見たことないが?)ではリングバッファである必要がなくても使えるかもしれません。
今後の展望
vectorを継承して、可変長配列風にするとvectorのメンバ関数も使えるし便利なのかもしれないけど、イマイチこのライブラリを使う場面が少なそうなので、多分やらない。