永続キュー

data_structure/persistent_queue.hpp · GitHub で見る

共通ページ

過去版からの末尾追加・先頭削除・先頭取得を行います。任意の位置の要素も取得できます。両端の更新や列の分割・連結には 永続 Deque を使います。

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

int main() {
	PersistentQueue<int> queue;
	auto v0 = queue.initial_root();
	auto v1 = queue.push(v0, 10);
	auto v2 = queue.push(v1, 20);
	auto v3 = queue.pop(v2);
	auto v4 = queue.push(v1, 30);
	assert(queue.front(v3) == 20 && queue.front(v2) == 10);
	assert(queue.back(v4) == 30 && queue.get(v4, 1) == 30);
}

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

操作	内容	計算量
size(root) / empty(root)	要素数／空か	\(O(1)\)
push(root,x)	x を末尾に追加した版	\(O(1)\)
pop(root)	先頭を削除した版。非空が必要	\(O(1)\)
front(root)	先頭要素。非空が必要	\(O(\log u)\)
back(root)	末尾要素。非空が必要	\(O(1)\)
get(root,p)	先頭から 0 始まり p 番目の要素	\(O(\log u)\)

get は 0 <= p < size(root) とします。u は空になるまでの同じ分岐上での push 回数です。u <= INT_MAX とし、T はコピー可能な型とします。T のデフォルト構築は不要です。root_type のフィールドは書き換えず、そのまま保存してください。

front_many(roots) は std::vector<root_type> で渡した非空の版それぞれの先頭要素を、指定順の std::vector<T> として返します。同じ版を複数回指定できます。空の版リストには空の列を返します。版の数は INT_MAX 以下とします。版や格納済みのノードは変更しません。

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

push は償却 \(O(1)\)、pop・back・size は \(O(1)\)、front・添字アクセスは \(O(\log u)\) 時間です。push 1 回につき 1 ノードを追加します。他の操作はノードを作りません。過去版から何度分岐してもこれらの計算量を保ちます。空または 1 ノードの履歴に対する操作は定数時間です。

作成済みノード数を \(N\)、指定した版の数を \(Q\) とすると、front_many は \(O(N+Q)\) 時間・追加空間です。

依存ライブラリ

• 永続スタック

検証コード

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

コード

#ifndef PERSISTENT_QUEUE_HPP
#define PERSISTENT_QUEUE_HPP

#include "persistent_stack.hpp"
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

template <class T>
class PersistentQueue {
	PersistentStack<T> stack;
  public:
	using value_type = T;
	struct root_type {
		typename PersistentStack<T>::root_type tail = 0;
		int length = 0;
		bool operator==(const root_type &) const = default;
	};
	root_type initial_root() const { return {}; }
	int size(root_type root) const { return root.length; }
	bool empty(root_type root) const { return size(root) == 0; }
	root_type push(root_type root, T value) { return {stack.push(root.tail, std::move(value)), root.length + 1}; }
	root_type pop(root_type root) const {
		assert(!empty(root));
		return root.length == 1 ? root_type{} : root_type{root.tail, root.length - 1};
	}
	T front(root_type root) const { assert(!empty(root)); return stack.get(root.tail, root.length - 1); }
	T back(root_type root) const { assert(!empty(root)); return stack.top(root.tail); }
	T get(root_type root, int p) const { assert(0 <= p && p < size(root)); return stack.get(root.tail, root.length - 1 - p); }
	std::vector<T> front_many(const std::vector<root_type> &roots) const {
		assert(roots.size() <= std::size_t(std::numeric_limits<int>::max()));
		std::uint64_t work = 0;
		unsigned limit = std::bit_width(stack.node_count());
		for (auto root : roots) { assert(!empty(root)); unsigned distance = unsigned(root.length - 1); work += distance < limit ? distance : limit; }
		if (work <= 3 * std::uint64_t(stack.node_count())) {
			std::vector<T> result;
			result.reserve(roots.size());
			for (auto root : roots) result.push_back(front(root));
			return result;
		}
		std::vector<std::pair<typename PersistentStack<T>::root_type, int>> queries;
		queries.reserve(roots.size());
		for (auto root : roots) { assert(!empty(root)); queries.emplace_back(root.tail, root.length - 1); }
		return stack.get_many(queries);
	}
	void reserve(std::size_t count) { stack.reserve(count); }
	std::size_t node_count() const { return stack.node_count(); }
	std::size_t memory_usage() const { return stack.memory_usage(); }
};

#endif

Back to top page