1
template<class T>
2
struct ListNode
3
{
4
  T _val;
5
  ListNode* _next;
6
  ListNode* _prev;
7
  ListNode()
8
    :_val(0)
9
    ,_next(nullptr)
10
    ,_prev(nullptr)
11
  {}
12
};

1
template<class T,class Ptr, class Ref>
2
class ListIterator
3
{
4
private:
5
  typedef ListNode<T>* PNode;
6
  typedef ListIterator<T,Ptr,ref> Self;
7
public:
8
  PNode it;
9
  ListIterator(PNode x = nullptr)
10
    :it(x)
11
  {}
12
  Ptr operator-> ()
13
  {
14
    return &(it->_val);
15
  }
16
  Ref operator* ()
17
  {
18
    return it->val;
19
  }
20
  Self& operator++ ()
21
  {
22
    it=it->_next;
23
    return *this;
24
  }
25
  Self operator++ (int)
26
  {
27
    Self ret = it;
28
    it = it-> _next;
29
    return ret;
30
  }
31
  Self& operator-- ()
32
  {
33
    it=it->_prev;
34
    return *this;
35
  }
36
  Self operator-- (int)
37
  {
38
    Self ret = it;
39
    it = it-> _prev;
40
    return ret;
41
  }
42
  bool operator!=(const Slef& l)
43
  {
44
    return it != l.it;
45
  }
46
  bool operator==(const Slef& l)
47
  {
48
    return it == l.it;
49
  }
50
  Self& operator=(const Slef& l)
51
  {
52
    it = l.it;
53
    return *this;
54
  }
55
};

1
template<class Iterator, class Ptr, class Ref>
2
struct Reverse_iterator
3
{
4
    Iterator _it;
5

6
    typedef Reverse_iterator<Iterator, Ptr, Ref> Self;
7

8
    Reverse_iterator(Iterator x)
9
    {
10
        _it = x;
11
    }
12
    Reverse_iterator() {}
13

14
    bool operator!=(const Self& tmp)
15
    {
16
        return _it != tmp._it;
17
    }
18

19
  Ptr operator*()
20
    {
21
        Iterator ret = _it;
22
        --ret;
23
        return *ret;
24
    }
25

26
  Ref operator->()
27
  {
28
    return &(operator*());
29
  }
30

31
  Self& operator++()
32
    {
33
    --_it;
34
    return *this;
35
    }
36

37

38
  Self& operator--()
39
    {
40
    ++_it;
41
    return *this;
42
    }
43
};

1
template<class T>
2
class list
3
{
4
private:
5
  typedef ListNode<T> _Node;
6
  typedef ListNode<T>* _PNode;
7
  _PNode _head;
8
  size_t _size;
9

10
  void empty_init()
11
  {
12
    _head = new _Node;
13
    _head -> _next = _head -> _prev = nullptr;
14
    _size = 0;
15
  }
16
public:
17
  typedef ListIterator<T,T*,T&> iterator;
18
  typedef ListIterator<const T, const T*, const T&> const_iterstor;
19
  typedef Reverse_iterator<iterator, T*, T&> reverse_iterator;
20
  typedef Reverse_iterator<const_iterator, const T*, const T&> const_reverse_iterator;
21

22
  reverse_iterator rbegin()
23
  {
24
    return reverse_iterator(end());
25
  }
26

27
  const_reverse_iterator crbegin() const
28
  {
29
    return const_reverse_iterator(end());
30
  }
31

32
  reverse_iterator rend()
33
  {
34
    return reverse_iterator(begin());
35
  }
36

37
  const_reverse_iterator crend() const
38
  {
39
    return const_reverse_iterator(begin());
40
  }
41

42
  void insert(iterator pos, const T& val)
43
  {
44
    size++;
45
    PNode cur = new Node;
46
    PNode next = pos.it;
47
    PNode prev = next->_prev;
48

49

50
    cur->_next = next;
51
    cur->_prev = prev;
52
    next->_prev = cur;
53
    prev->_next = cur;
54
    cur->_val = val;
55
  }
56

57

58
  iterator begin()
59
  {
60
    return _head->_next;
61
  }
62

63

64
  iterator end()
65
  {
66
    return _head;
67
  }
68

69

70
  const_iterator begin() const
71
  {
72
    return _head->_next;
73
  }
74

75

76
  const_iterator end() const
77
  {
78
    return _head;
79
  }
80

81

82
  list()
83
  {
84
    empty_init();
85
  }
86
  list(int n, const T& value = T())
87
  {
88
    empty_init();
89
    while (n--)
90
    {
91
      push_back(value);
92
    }
93
  }
94
  template <class Iterator>
95
  list(Iterator first, Iterator last)
96
  {
97
    empty_init();
98
    while (first != last)
99
    {
100
      push_back(*first);
101
      ++first;
102
    }
103
  }
104
  list(const list<T>& l)
105
  {
106
    empty_init();
107
    for (auto& e : l)
108
      push_back(e);
109
  }
110

111

112
  list<T>& operator=(const list<T> l)
113
  {
114
    swap(l);
115
    return *this;
116
  }
117
  void clear()
118
  {
119
    iterator it = begin();
120
    while (it != end())
121
    {
122
      it = erase(it);
123
    }
124
  }
125
  ~list()
126
  {
127
    clear();
128
    delete _head;
129
  }
130

131

132
  void swap(list<T>& l)
133
  {
134
    std::swap(l.size, size);
135
    std::swap(l._head, _head);
136
  }
137

138

139
  void push_front(const T& val)
140
  {
141
    insert(begin(), val);
142
  }
143
  void push_back(const T& val)
144
  {
145
    insert(end(), val);
146
  }
147

148

149
  iterator erase(iterator pos)
150
  {
151
    size--;
152
    PNode next = (pos.it)->_next;
153
    PNode prev = (pos.it)->_prev;
154

155
    next->_prev = prev;
156
    prev->_next = next;
157
    delete pos.it;
158
    return next;
159
  }
160

161

162
  void pop_back()
163
  {
164
    erase(--end());
165
  }
166

167

168
  void pop_front()
169
  {
170
    erase(begin());
171
  }
172
};