永続スタック (生ポインタ) (Heuristic/raw_pointer_persistent_stack.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-17 19:46:16+09:00
• Include: #include "Heuristic/raw_pointer_persistent_stack.hpp"

永続スタック (生ポインタ)

永続スタックのポインタに関する内部実装を生ポインタに変更したクラスです。
ポインタの開放処理が速くなる半面、メモリリークやダングリングポインタなどのリスクが生じることを理解したうえで使用すること。
ビームサーチの行動履歴管理に使用したことがある。

コンストラクタ

RawPointerPersistentStack<T> ps

• 型 T を要素に持つ空のスタックを作成します。

計算量

• $O(1)$

push

void ps.push(const T &v)

要素 v をスタックに追加します。

計算量

• $O(1)$

pop

void ps.pop()

スタックの先頭の要素を削除します。

制約

• スタックが空でないこと。

計算量

• $O(1)$

top

T ps.top()

スタックの先頭の要素を返します。

制約

• スタックが空でないこと。

計算量

• $O(1)$

empty

bool ps.empty()

スタックが空かどうかを返します。

計算量

• $O(1)$

size

int ps.size()

スタックに含まれる要素の数を返します。

計算量

• $O(1)$

extract_values

vector<T> ps.extract_values()

スタックのすべての要素を順番に取り出し、vector に格納して返します。
スタックの順番は保持され、最初に追加した要素が最初に、最後に追加した要素が最後に配置されます。

計算量

• $O(n)$

Verified with

• test/Heuristic/raw_pointer_persistent_stack/abc273-e.cpp

Code

#include <bits/stdc++.h>

using namespace std;

template <class T>
class RawPointerPersistentStack
{
protected:
    struct History
    {
        T v;
        History *previous;
        int size = 1;
        History(const T &v, History *previous) : v(v), previous(previous)
        {
            if (previous == nullptr)
            {
                size = 1;
                return;
            }

            size = previous->size + 1;
        }

        ~History()
        {
            delete previous;
        }
    };

private:
    History *latest;

public:
    RawPointerPersistentStack() : latest(nullptr)
    {
    }

    RawPointerPersistentStack(History *latest) : latest(latest)
    {
    }

    bool empty() const
    {
        return latest == nullptr;
    }

    T top() const
    {
        assert(!empty());
        return latest->v;
    }

    void push(const T &v)
    {
        latest = new History(v, latest);
    }

    void pop()
    {
        assert(!empty());
        latest = latest->previous;
    }

    int size() const
    {
        if (empty())
        {
            return 0;
        }

        return latest->size;
    }

    vector<T> extract_values()
    {
        vector<T> result;
        auto now = PersistentStack(latest);
        while (!now.empty())
        {
            result.push_back(now.top());
            now.pop();
        }

        reverse(result.begin(), result.end());

        return result;
    }
};

#line 1 "Heuristic/raw_pointer_persistent_stack.hpp"
#include <bits/stdc++.h>

using namespace std;

template <class T>
class RawPointerPersistentStack
{
protected:
    struct History
    {
        T v;
        History *previous;
        int size = 1;
        History(const T &v, History *previous) : v(v), previous(previous)
        {
            if (previous == nullptr)
            {
                size = 1;
                return;
            }

            size = previous->size + 1;
        }

        ~History()
        {
            delete previous;
        }
    };

private:
    History *latest;

public:
    RawPointerPersistentStack() : latest(nullptr)
    {
    }

    RawPointerPersistentStack(History *latest) : latest(latest)
    {
    }

    bool empty() const
    {
        return latest == nullptr;
    }

    T top() const
    {
        assert(!empty());
        return latest->v;
    }

    void push(const T &v)
    {
        latest = new History(v, latest);
    }

    void pop()
    {
        assert(!empty());
        latest = latest->previous;
    }

    int size() const
    {
        if (empty())
        {
            return 0;
        }

        return latest->size;
    }

    vector<T> extract_values()
    {
        vector<T> result;
        auto now = PersistentStack(latest);
        while (!now.empty())
        {
            result.push_back(now.top());
            now.pop();
        }

        reverse(result.begin(), result.end());

        return result;
    }
};

Back to top page