georgiy110802

Untitled

Sep 21st, 2021
795
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Node {
  6.     Node(Node *n, int v) : next_(n), value(v){}
  7.     Node *next_;
  8.     int value;
  9. };
  10.  
  11. struct PersistentStack {
  12.     vector<Node* > versions;
  13.     vector<Node* > memory;
  14.  
  15.     PersistentStack() {
  16.         versions.push_back(nullptr);
  17.     }
  18.  
  19.     void push(int version, int value) {
  20.         auto newRoot = new Node(versions[version], value);
  21.         versions.push_back(newRoot);
  22.         memory.push_back(newRoot);
  23.     }
  24.  
  25.     void pop(int version) {
  26.         versions.push_back(versions[version]->next_);
  27.     }
  28.  
  29.     void print(int version) {
  30.         cout << version << ": ";
  31.         auto curr = versions[version];
  32.         while (curr) {
  33.             cout << curr->value << ' ';
  34.             curr = curr->next_;
  35.         }
  36.         cout << "\n";
  37.     }
  38.  
  39. //    void destroy(Node* n) {
  40. //        while (n) {
  41. //            Node *newRoot = n->next_;
  42. //            delete n;
  43. //            n = nullptr;
  44. //            n = newRoot;
  45. //        }
  46. //    }
  47.  
  48.     ~PersistentStack(){
  49.         for (auto & m : memory) {
  50.             delete m;
  51.         }
  52.     }
  53. };
  54.  
  55. int main() {
  56.     PersistentStack st;
  57.     st.print(0);
  58.     st.push(0, 1);
  59.     st.print(1);
  60.     st.push(1, 3);
  61.     st.print(2);
  62.     st.pop(1);
  63.     st.print(3);
  64.     st.push(3, 10);
  65.     st.print(4);
  66.     st.push(4, 15);
  67.     st.print(5);
  68.     st.push(5, 20);
  69.     st.print(4);
  70.     st.print(6);
  71.     st.print(3);
  72. }
  73.  
RAW Paste Data