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