fork download
copy 
  1. #include <iostream>
  2. #include <memory>
  3.  
  4. class List {
  5.  
  6.     class Node;
  7.     typedef std::shared_ptr<Node> Ptr;
  8.     typedef std::weak_ptr<Node> Ref;
  9.  
  10.     class NodeState {
  11.         friend class List;
  12.  
  13.         Ptr next_;
  14.         Ref prev_;
  15.         int data_;
  16.  
  17.         NodeState (int x) : data_(x) {}
  18.         NodeState (const Ptr &p) : next_(p), prev_(p) {}
  19.     };
  20.  
  21.     class Node {
  22.         friend class List;
  23.  
  24.         virtual ~Node () = default;
  25.         virtual NodeState & state () = 0;
  26.  
  27.         Ptr & next () { return state().next_; }
  28.         Ptr prev () { return Ptr(state().prev_); }
  29.         int & data () { return state().data_; }
  30.  
  31.         void insert (const Ptr &p) {
  32.             p->next() = prev()->next();
  33.             p->state().prev_  = state().prev_;
  34.             prev()->next() = p;
  35.             state().prev_ = p;
  36.         }
  37.     };
  38.  
  39.     NodeState sentinel_state_;
  40.  
  41.     Ptr head () { return sentinel_state_.next_; }
  42.     Ptr sentinel () { return head()->prev(); }
  43.  
  44.     struct NodeImplementation : Node, NodeState {
  45.         NodeImplementation (int x) : NodeState(x) {}
  46.         NodeState & state () { return *this; }
  47.     };
  48.  
  49.     struct NodeSentinel : Node {
  50.         List &list_;
  51.         NodeSentinel (List &l) : list_(l) {}
  52.         NodeState & state () { return list_.sentinel_state_; }
  53.     };
  54.  
  55.     class Iterator {
  56.         friend class List;
  57.         Ptr ptr_;
  58.         Iterator (const Ptr &p) : ptr_(p) {}
  59.     public:
  60.         int operator * () const { return ptr_->data(); }
  61.         Iterator operator ++ () { ptr_ = ptr_->next(); return *this; }
  62.         Iterator operator -- () { ptr_ = ptr_->prev(); return *this; }
  63.         bool operator != (const Iterator &i) const { return ptr_ != i.ptr_; }
  64.     };
  65.  
  66. public:
  67.  
  68.     typedef Iterator iterator;
  69.  
  70.     List () : sentinel_state_(std::make_shared<NodeSentinel>(*this)) {}
  71.  
  72.     iterator begin () { return head(); }
  73.     iterator end () { return head()->prev(); }
  74.  
  75.     void push_back (int x) {
  76.         sentinel()->insert(std::make_shared<NodeImplementation>(x));
  77.     }
  78.     void push_front (int x) {
  79.         head()->insert(std::make_shared<NodeImplementation>(x));
  80.     }
  81.  
  82. };
  83.  
  84. int main ()
  85. {
  86.     auto x = [](List &l) {
  87.         std::cout << "->";
  88.         for (auto x : l) std::cout << '|' << x;
  89.         std::cout << "|\n";
  90.     };
  91.  
  92.     List l1;
  93.     l1.push_front(3);
  94.     l1.push_front(7);
  95.     l1.push_front(5);
  96.     l1.push_front(1);
  97.     // result: 1, 5, 7, 3
  98.     x(l1);
  99.  
  100.     List l2;
  101.     l2.push_back(4);
  102.     l2.push_back(8);
  103.     l2.push_back(6);
  104.     l2.push_back(2);
  105.     // result: 4, 8, 6, 2
  106.     x(l2);
  107. }
Success #stdin #stdout 0s 3280KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
->|1|5|7|3|
->|4|8|6|2|
https://ideone.com/pzhbct
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!