persistent stack

ソースコード

 1#include <vector>
 2#include <cassert>
 3using namespace std;
 4
 5// PersistentStack
 6namespace titan23 {
 7
 8    template<typename T>
 9    class PersistentStack {
10      private:
11        struct Node;
12        using NodePtr = Node*;
13        NodePtr node;
14
15        struct Node {
16            T key;
17            Node* prev;
18            Node() {}
19            Node(T key) : key(key), prev(nullptr) {}
20            Node(T key, NodePtr prev) : key(key), prev(prev) {}
21        };
22
23        PersistentStack(NodePtr new_node) : node(new_node) {}
24
25      public:
26        PersistentStack() : node(nullptr) {}
27
28        T top() const {
29            assert(node);
30            return node->key;
31        }
32
33        T pop() {
34            T res = node->key;
35            assert(node->prev);
36            node = node->prev;
37            return res;
38        }
39
40        PersistentStack copy() const {
41            NodePtr new_node = node ? (new Node(node->key, node->prev)) : nullptr;
42            PersistentStack s(new_node);
43            return s;
44        }
45
46        PersistentStack push(T key) {
47            NodePtr new_node = new Node(key);
48            new_node->prev = this->node;
49            PersistentStack s(new_node);
50            return s;
51        }
52
53        vector<T> tovector() const {
54            vector<T> a;
55            NodePtr s = node;
56            while (s) {
57                a.emplace_back(s->key);
58                s = s->prev;;
59            }
60            reverse(a.begin(), a.end());
61            return a;
62        }
63    };
64}  // namespase titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/persistent_stack.cpp