PersistentQueue
クラス · 永続キュー
template <class T>
struct PersistentQueue;
概要
永続キュー
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
T |
— |
計算量
- 追加・先頭取得は $O(\log n)$、削除・サイズ取得は $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空のqueueを構築する (2) 既存の根からサイズnのversionを構築する |
$O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
size |
要素数を返す | $O(1)$ |
empty |
空か返す | $O(1)$ |
top |
先頭要素を返す | $O(\log n)$ |
front |
先頭要素を返す | $O(\log n)$ |
push |
(1) 末尾にvalを追加した新しいversionを返す (2) 末尾にvalをmoveして追加した新しいversionを返す |
$O(\log n)$ |
emplace |
末尾に要素を直接構築した新しいversionを返す | $O(\log n)$ |
pop |
先頭を削除した新しいversionを返す | $O(1)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
node_ptr |
内部ノードへのpointer型 | 型エイリアスで実行時計算量はない |
メンバの詳細
(constructor)
// (1)
constexpr PersistentQueue();
// (2)
constexpr PersistentQueue(int n, node_ptr _root);
(1) 空のqueueを構築する
- 計算量: $O(1)$
(2) 既存の根からサイズnのversionを構築する
- 計算量: $O(1)$
push
// (1)
PersistentQueue push(const T &val) const;
// (2)
PersistentQueue push(T &&val) const;
(1) 末尾にvalを追加した新しいversionを返す
- 計算量: $O(\log n)$
(2) 末尾にvalをmoveして追加した新しいversionを返す
- 計算量: $O(\log n)$