永続スタック

data_structure/persistent_stack.hpp · GitHub で見る

共通ページ

過去版からの push・pop と、先頭から指定個数戻った要素の取得を行います。

#include "lib/data_structure/persistent_stack.hpp"
#include <cassert>

int main() {
	PersistentStack<int> stack;
	auto v0 = stack.initial_root();
	auto v1 = stack.push(v0, 10);
	auto v2 = stack.push(v1, 20);
	auto v3 = stack.push(v1, 30);
	assert(stack.top(v2) == 20 && stack.top(v3) == 30);
	assert(stack.get(v2, 1) == 10 && stack.pop(v2) == v1);
}

各更新は新しい root_type を返し、引数の版は変わりません。initial_root() が最初の版です。ルートをコピーするだけなら時間・追加領域ともに \(O(1)\) で、任意の過去版から分岐できます。同じオブジェクトから得たルートだけを渡してください。版ごとのノード解放は行いません。オブジェクト自体のコピーは全ノードの複製になります。

操作	内容	計算量
size(root) / empty(root)	要素数／空か	\(O(1)\)
push(root,x)	x を先頭に追加した版	\(O(1)\)
pop(root)	先頭を削除した版。非空が必要	\(O(1)\)
top(root)	先頭要素。非空が必要	\(O(1)\)
get(root,k)	先頭から 0 始まり k 番目の要素	\(O(\log n)\)
ancestor(root,k)	k 個 pop した版。0 <= k <= size(root)	\(O(\log n)\)

get は 0 <= k < size(root) とします。要素数は INT_MAX 以下、T はコピー可能な型とします。T のデフォルト構築は不要です。

get_many(queries) は std::vector<std::pair<root_type,int>> で渡した (root,k) それぞれの要素を、問い合わせ順の std::vector<T> として返します。各組は get(root,k) と同じ範囲を満たしてください。空の問い合わせ列には空の列を返します。問い合わせ数は INT_MAX 以下とします。ルートや格納済みのノードは変更しません。

reserve(count) は全版を合わせたノード数を予約します。node_count() は作成済みノード数、memory_usage() は予約済みノード領域のバイト数を返します。ルートは再確保後も有効です。値のコピー・演算は定数時間とします。更新の時間には領域確保の償却計算量を含みます。

push は償却 \(O(1)\)、pop・top・size は \(O(1)\)、祖先・添字アクセスは \(O(\log n)\) 時間です。push 1 回につき 1 ノードを追加し、他の操作はノードを作りません。長さ 0・1 の操作は定数時間です。

作成済みノード数を \(N\)、問い合わせ数を \(Q\) とすると、get_many は \(O(N+Q)\) 時間・追加空間です。

検証コード

• test/persistent_queue.test.cpp
• test/persistent_queue_batch.test.cpp

コード

#ifndef PERSISTENT_STACK_HPP
#define PERSISTENT_STACK_HPP

#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template <class T>
class PersistentStack {
  public:
	using value_type = T;
	using root_type = std::uint32_t;
  private:
	using Stored = std::conditional_t<std::is_trivially_default_constructible_v<T> && std::is_trivially_copyable_v<T>, T, std::optional<T>>;
	struct Node { Stored value; root_type next, jump; int size, jump_length; };
	std::vector<Node> nodes{{{}, 0, 0, 0, 0}};
	void check([[maybe_unused]] root_type root) const { assert(root < nodes.size()); }
	const T &value_at(root_type root) const {
		if constexpr (std::is_same_v<Stored, T>) return nodes[root].value;
		else return *nodes[root].value;
	}
  public:
	root_type initial_root() const { return 0; }
	int size(root_type root) const { check(root); return nodes[root].size; }
	bool empty(root_type root) const { return size(root) == 0; }
	root_type push(root_type root, T value) {
		check(root);
		assert(size(root) < std::numeric_limits<int>::max() && nodes.size() < std::numeric_limits<root_type>::max());
		auto a = nodes[root].jump;
		int length = nodes[root].jump_length;
		bool combine = length == nodes[a].jump_length;
		auto jump = combine ? nodes[a].jump : root;
		Node node{std::move(value), root, jump, size(root) + 1, combine ? 2 * length + 1 : 1};
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(std::move(node));
		return result;
	}
	root_type pop(root_type root) const { check(root); assert(root); return nodes[root].next; }
	T top(root_type root) const { check(root); assert(root); return value_at(root); }
	root_type ancestor(root_type root, int count) const {
		check(root); assert(0 <= count && count <= size(root));
		if (count == size(root)) return 0;
		while (count) {
			int length = nodes[root].jump_length;
			if (length <= count) count -= length, root = nodes[root].jump;
			else --count, root = nodes[root].next;
		}
		return root;
	}
	T get(root_type root, int k) const { assert(0 <= k && k < size(root)); return top(ancestor(root, k)); }
	std::vector<T> get_many(const std::vector<std::pair<root_type, int>> &queries) const {
		assert(queries.size() <= std::size_t(std::numeric_limits<int>::max()));
		if (queries.empty()) return {};
		std::uint64_t work = 0;
		unsigned limit = std::bit_width(nodes.size());
		for (auto [root, k] : queries) { check(root); assert(0 <= k && k < size(root)); work += unsigned(k) < limit ? unsigned(k) : limit; }
		if (work <= 3 * std::uint64_t(nodes.size())) {
			std::vector<T> result;
			result.reserve(queries.size());
			for (auto [root, k] : queries) result.push_back(get(root, k));
			return result;
		}
		std::vector<root_type> first(nodes.size()), next(nodes.size()), selected(queries.size()), path;
		std::vector<int> head(nodes.size(), -1), following(queries.size());
		for (root_type v = 1; v < nodes.size(); ++v) {
			root_type p = nodes[v].next;
			next[v] = first[p]; first[p] = v;
		}
		for (int i = 0; i < int(queries.size()); ++i) {
			root_type root = queries[i].first;
			following[i] = head[root]; head[root] = i;
		}
		for (root_type v = first[0]; v;) {
			path.push_back(v);
			for (int i = head[v]; i != -1; i = following[i]) selected[i] = path[path.size() - 1 - queries[i].second];
			if (first[v]) { v = first[v]; continue; }
			while (v && !next[v]) { path.pop_back(); v = nodes[v].next; }
			if (v) { path.pop_back(); v = next[v]; }
		}
		std::vector<T> result;
		result.reserve(queries.size());
		for (root_type v : selected) result.push_back(value_at(v));
		return result;
	}
	void reserve(std::size_t count) { assert(count < std::numeric_limits<root_type>::max()); nodes.reserve(count + 1); }
	std::size_t node_count() const { return nodes.size() - 1; }
	std::size_t memory_usage() const { return nodes.capacity() * sizeof(Node); }
};

#endif

Back to top page