集約値取得可能な deque
ソースコード
nachia/array/deque-operate-aggregation.hpp
主な機能
モノイドの要素列に対して、以下の操作を行う。
- 列の末尾に要素を追加
- 列の先頭に要素を追加
- 列の末尾の要素を削除
- 列の先頭の要素を削除
- 二項演算
+によって全体を集約した値を取得
モノイドの操作を定数時間とすると、各操作は償却定数時間である。
最悪は要素数に対して線形時間かかりうる。
構造体テンプレート DequeOperateAggregation
テンプレート引数
template<class Val>
struct DequeOperateAggregation;
Valどうしの二項演算+を正しく処理しなければならない。
コンストラクタ
DequeOperateAggregation(Val e);
$e+a=a$ の性質をもつ $e$ を渡さなければ構築できない。
pushFront, pushBack
void pushFront(Val v);
void pushBack(Val v);
要素を追加する。
popFront, popBack
void popFront();
void popBack();
要素を削除する。
sum
Val sum();
集約値を返す。