fork download
copy 
  1. #include <memory>
  2.  
  3. struct list_node_base {
  4.   list_node_base(list_node_base *prev, list_node_base *next)
  5.     : next(next), prev(prev) {}
  6.   list_node_base *next;
  7.   list_node_base *prev;
  8. };
  9.  
  10. template <typename T>
  11. class list {
  12.   struct node : list_node_base {
  13.     template <typename... Args>
  14.     node(list_node_base *prev, list_node_base *next, Args&&... args)
  15.       : list_node_base(prev, next), data(std::forward<Args>(args)...) {}
  16.     T data;
  17.   };
  18.   list_node_base pointer_to_first;
  19.   list_node_base* data() { return &pointer_to_first; }
  20.  
  21. public:
  22.   list() : pointer_to_first(data(), data()) {}
  23.  ~list() { clear(); }
  24.  
  25.   list(list const& o) =delete;
  26.   list& operator=(list const& o) =delete;
  27.  
  28.   class iterator {
  29.     friend class list;
  30.     list_node_base *n;
  31.     iterator (list_node_base *n) : n(n) {}
  32.  
  33.     node *as_node() noexcept { return static_cast<node*>(n); }
  34.  
  35.   public:
  36.     typedef std::ptrdiff_t               difference_type;
  37.     typedef std::forward_iterator_tag    iterator_category;
  38.     typedef T                            value_type;
  39.     typedef T*                           pointer;
  40.     typedef T&                           reference;
  41.  
  42.     iterator& operator++()    { n = n->next; return *this; }
  43.     iterator  operator++(int) { iterator tmp = *this; n = n->next; return tmp; }
  44.  
  45.     iterator& operator--()    { n = n->prev; return *this; }
  46.     iterator  operator--(int) { iterator tmp = *this; n = n->prev; return tmp; }
  47.  
  48.     bool operator==(const iterator& o) const { return n == o.n; }
  49.     bool operator!=(const iterator& o) const { return n != o.n; }
  50.  
  51.     T& operator* () { return  as_node()->data; }
  52.     T* operator->() { return &as_node()->data; }
  53.   };
  54.  
  55.   void clear()
  56.   {
  57.     for (iterator i=begin(); i!=end();)
  58.       std::unique_ptr<node>(i++.as_node());
  59.   }
  60.  
  61.   template <typename... Args>
  62.   iterator emplace(iterator i, Args&&... args)
  63.   {
  64.     std::unique_ptr<node> n(new node(i.n->prev, i.n, std::forward<Args>(args)...));
  65.     i.n->prev->next = n.get();
  66.     i.n->prev       = n.get();
  67.     return n.release();
  68.   }
  69.  
  70.   iterator erase(iterator i)
  71.   {
  72.     std::unique_ptr<node> erased(i.as_node());
  73.     erased->prev->next = erased->next;
  74.     erased->next->prev = erased->prev;
  75.     return erased->next;
  76.   }
  77.  
  78.   iterator insert(iterator i, T const& x) { return emplace(i, x); }
  79.   iterator insert(iterator i, T&& x)      { return emplace(i, std::move(x)); }
  80.  
  81.   iterator emplace_front(T const& x) { return emplace(begin(), x); }
  82.   iterator push_front(T const& x)    { return emplace_front(x); }
  83.   iterator push_front(T&&      x)    { return emplace_front(std::move(x)); } 
  84.   void     pop_front() { erase(begin()); }  
  85.  
  86.   iterator emplace_back(T const& x) { return emplace(end(), x); }
  87.   iterator push_back(T const& x)    { return emplace_back(x); }
  88.   iterator push_back(T&&      x)    { return emplace_back(std::move(x)); }
  89.   void     pop_back() { erase(data()->prev); }  
  90.  
  91.   iterator begin() { return data()->next; }
  92.   iterator end()   { return data();       }
  93. };
  94.  
  95. #include <iostream>
  96. #include <iterator>
  97. #include <cassert>
  98. #include <string>
  99.  
  100. int main()
  101. {
  102. #define check(s) assert(std::string(l.begin(), l.end()) == s)
  103.  
  104.   list<char> l;
  105.   l.push_back('m');  check("m");
  106.   l.push_back('z');  check("mz");
  107.   l.push_front('a'); check("amz");
  108.   l.erase(l.begin());check("mz");
  109.   l.insert(l.begin(), 'a');check("amz");
  110.   l.insert(l.end(), '!');  check("amz!");
  111.   l.pop_front();     check("mz!");
  112.   l.pop_back();      check("mz");
  113.   list<char>::iterator i=l.begin(); i++;
  114.   i = l.insert(i, '-'); check("m-z");
  115.   i = l.erase(i);       check("mz");
  116.   l.erase(i);           check("m");
  117.   l.push_front('a');    check("am");
  118.   l.push_back('z');     check("amz");
  119.   i=l.end(); i--; i--;
  120.   i=l.erase(i);         check("az");
  121. } 
  122.  
Success #stdin #stdout 0s 3028KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NMRpbG
language:
C++14 (gcc 8.3)
created:
13 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!