fork download
copy 
  1. #include <iostream>
  2. #include <list>
  3. #include <map>
  4. #include <memory>
  5.  
  6. template <typename T> class List;
  7.  
  8. template <typename T> class ListTraits {
  9. protected:
  10.     typedef std::list<std::shared_ptr<T>> Impl;
  11.     typedef typename Impl::iterator Iterator;
  12.     typedef typename Impl::const_iterator ConstIterator;
  13.     typedef typename Impl::reverse_iterator Rotareti;
  14.     typedef typename Impl::const_reverse_iterator ConstRotareti;
  15.     typedef std::map<const List<T> *, typename Impl::iterator> Ref;
  16. };
  17.  
  18. template <typename T>
  19. class List : public ListTraits<T> {
  20.     template <typename ITER> class IteratorT;
  21.     typedef ListTraits<T> Traits;
  22.     typename Traits::Impl impl_;
  23. public:
  24.     typedef typename Traits::Impl::size_type size_type;
  25.     typedef typename Traits::Impl::value_type pointer;
  26.     typedef pointer value_type;
  27.     typedef IteratorT<typename Traits::Iterator> iterator;
  28.     typedef IteratorT<typename Traits::ConstIterator> const_iterator;
  29.     typedef IteratorT<typename Traits::Rotareti> reverse_iterator;
  30.     typedef IteratorT<typename Traits::ConstRotareti> const_reverse_iterator;
  31.     class Item;
  32.     ~List () { while (!empty()) pop_front(); }
  33.     size_type size () const { return impl_.size(); }
  34.     bool empty () const { return impl_.empty(); }
  35.     iterator begin () { return impl_.begin(); }
  36.     iterator end () { return impl_.end(); }
  37.     const_iterator begin () const { return impl_.begin(); }
  38.     const_iterator end () const { return impl_.end(); }
  39.     reverse_iterator rbegin () { return impl_.rbegin(); }
  40.     reverse_iterator rend () { return impl_.rend(); }
  41.     const_reverse_iterator rbegin () const { return impl_.rbegin(); }
  42.     const_reverse_iterator rend () const { return impl_.rend(); }
  43.     pointer front () const { return !empty() ? impl_.front() : pointer(); }
  44.     pointer back () const { return !empty() ? impl_.back() : pointer(); }
  45.     void push_front (const pointer &e);
  46.     void pop_front ();
  47.     void push_back (const pointer &e);
  48.     void pop_back ();
  49.     void erase (const pointer &e);
  50.     bool contains (const pointer &e) const;
  51. };
  52.  
  53. template <typename T>
  54. template <typename ITER>
  55. class List<T>::IteratorT : public ITER {
  56.     friend class List<T>;
  57.     ITER iter_;
  58.     IteratorT (ITER i) : iter_(i) {}
  59. public:
  60.     IteratorT () : iter_() {}
  61.     IteratorT & operator ++ () { ++iter_; return *this; }
  62.     IteratorT & operator -- () { --iter_; return *this; }
  63.     IteratorT operator ++ (int) { return iter_++; }
  64.     IteratorT operator -- (int) { return iter_--; }
  65.     bool operator == (const IteratorT &x) const { return iter_ == x.iter_; }
  66.     bool operator != (const IteratorT &x) const { return iter_ != x.iter_; }
  67.     T & operator * () const { return **iter_; }
  68.     pointer operator -> () const { return *iter_; }
  69. };
  70.  
  71. template <typename T>
  72. class List<T>::Item {
  73.     friend class List<T>;
  74.     mutable typename Traits::Ref ref_;
  75. };
  76.  
  77. template <typename T>
  78. inline void List<T>::push_front (const pointer &e) {
  79.     const Item &item = *e;
  80.     typename Traits::Ref::iterator i = item.ref_.find(this);
  81.     if (i == item.ref_.end()) {
  82.         item.ref_[this] = impl_.insert(impl_.begin(), e);
  83.     } else if (front() != e) {
  84.         impl_.erase(i->second);
  85.         i->second = impl_.insert(impl_.begin(), e);
  86.     }
  87. }
  88.  
  89. template <typename T>
  90. inline void List<T>::pop_front () {
  91.     if (!empty()) {
  92.         const Item &item = *front();
  93.         item.ref_.erase(this);
  94.         impl_.pop_front();
  95.     }
  96. }
  97.  
  98. template <typename T>
  99. inline void List<T>::push_back (const pointer &e) {
  100.     const Item &item = *e;
  101.     typename Traits::Ref::iterator i = item.ref_.find(this);
  102.     if (i == item.ref_.end()) {
  103.         item.ref_[this] = impl_.insert(impl_.end(), e);
  104.     } else if (back() != e) {
  105.         impl_.erase(i->second);
  106.         i->second = impl_.insert(impl_.end(), e);
  107.     }
  108. }
  109.  
  110. template <typename T>
  111. inline void List<T>::pop_back () {
  112.     if (!empty()) {
  113.         const Item &item = *back();
  114.         item.ref_.erase(this);
  115.         impl_.pop_back();
  116.     }
  117. }
  118.  
  119. template <typename T>
  120. inline void List<T>::erase (const pointer &e) {
  121.     const Item &item = *e;
  122.     typename Traits::Ref::iterator i = item.ref_.find(this);
  123.     if (i != item.ref_.end()) {
  124.         item.ref_.erase(i);
  125.         impl_.erase(i->second);
  126.     }
  127. }
  128.  
  129. template <typename T>
  130. inline bool List<T>::contains (const pointer &e) const {
  131.     const Item &item = *e;
  132.     typename Traits::Ref::iterator i = item.ref_.find(this);
  133.     return i != item.ref_.end();
  134. }
  135.  
  136. class MyItem;
  137. typedef List<const MyItem> MyList;
  138.  
  139. class MyItem : public MyList::Item {
  140.     int i_;
  141. public:
  142.     MyItem (int i = 0) : i_(i) {}
  143.     operator int () const { return i_; }
  144.     int value () const { return i_; }
  145. };
  146.  
  147. void dump_list (const MyList &l, const char *label = 0) {
  148.     if (label) std::cout << label;
  149.     for (auto x = l.begin(); x != l.end(); ++x) {
  150.         std::cout << " " << x->value();
  151.     }
  152.     std::cout << '\n';
  153. }
  154.  
  155. int main ()
  156. {
  157.     MyList l1;
  158.     MyList l2;
  159.     MyList::pointer p1(new MyItem(1));
  160.     MyList::pointer p2(new MyItem(2));
  161.     MyList::pointer p3(new MyItem(3));
  162.     l1.push_back(p1);
  163.     l1.push_back(p2);
  164.     l1.push_back(p3);
  165.     l2.push_front(p1);
  166.     l2.push_front(p2);
  167.     l2.push_front(p3);
  168.     std::cout << "l1 size: " << l1.size() << std::endl;
  169.     std::cout << "l2 size: " << l2.size() << std::endl;
  170.     dump_list(l1, "l1:");
  171.     dump_list(l2, "l2:");
  172.     l1.erase(p2);
  173.     l1.pop_back();
  174.     l2.pop_front();
  175.     std::cout << "l1 size: " << l1.size() << std::endl;
  176.     std::cout << "l2 size: " << l2.size() << std::endl;
  177.     dump_list(l1, "l1:");
  178.     dump_list(l2, "l2:");
  179. }
  180.  
Success #stdin #stdout 0s 3036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
l1 size: 3
l2 size: 3
l1: 1 2 3
l2: 3 2 1
l1 size: 1
l2 size: 2
l1: 1
l2: 2 1
https://ideone.com/9WcVsL
language:
C++14 (gcc 8.3)
created:
11 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!