Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4973 | right-hear | 1 | #ifndef _LIST_INCLUDED |
2 | #define _LIST_INCLUDED |
||
3 | #include |
||
4 | namespace std |
||
5 | { |
||
6 | struct __list_node_base |
||
7 | { |
||
8 | __list_node_base* prev; |
||
9 | __list_node_base* next; |
||
10 | }; |
||
11 | template |
||
12 | { |
||
13 | T data; |
||
14 | __list_node(const T& d):data(d){} |
||
15 | }; |
||
16 | template |
||
17 | { |
||
18 | __list_node_base head; // head.prev = end, head.next = start |
||
19 | unsigned _size; |
||
20 | public: |
||
21 | list():_size(0) {head.prev=head.next=&head;} |
||
22 | ~list() {clear();} |
||
23 | void clear() |
||
24 | { |
||
25 | __list_node |
||
26 | static_cast<__list_node |
||
27 | while (a!=&head) |
||
28 | { |
||
29 | __list_node |
||
30 | static_cast<__list_node |
||
31 | delete a; |
||
32 | a = b; |
||
33 | } |
||
34 | head.prev = head.next = &head; |
||
35 | _size = 0; |
||
36 | } |
||
37 | class iterator |
||
38 | { |
||
39 | public: |
||
40 | __list_node_base* cur; |
||
41 | friend class list; |
||
42 | iterator(){} |
||
43 | iterator(__list_node_base*c):cur(c){} |
||
44 | iterator(const iterator& it):cur(it.cur){} |
||
45 | iterator& operator++() |
||
46 | {cur=cur->next;return *this;} |
||
47 | iterator operator++(int) |
||
48 | {iterator tmp(*this);cur=cur->next;return tmp;} |
||
49 | iterator& operator--() |
||
50 | {cur=cur->prev;return *this;} |
||
51 | iterator operator--(int) |
||
52 | {iterator tmp(*this);cur=cur->prev;return tmp;} |
||
53 | bool operator!=(const iterator& it) |
||
54 | {return cur!=it.cur;} |
||
55 | bool operator==(const iterator& it) |
||
56 | {return cur==it.cur;} |
||
57 | T& operator*() |
||
58 | {return static_cast<__list_node |
||
59 | T* operator->() {return &**this;} |
||
60 | }; |
||
61 | class const_iterator |
||
62 | { |
||
63 | const __list_node_base* cur; |
||
64 | friend class list; |
||
65 | public: |
||
66 | const_iterator(){} |
||
67 | const_iterator(const __list_node_base*c):cur(c){} |
||
68 | const_iterator(const const_iterator& it):cur(it.cur){} |
||
69 | const_iterator(const iterator& it):cur(it.cur){} |
||
70 | const_iterator& operator++() |
||
71 | {cur=cur->next;return *this;} |
||
72 | const_iterator operator++(int) |
||
73 | {const_iterator tmp(*this);cur=cur->next;return tmp;} |
||
74 | const_iterator& operator--() |
||
75 | {cur=cur->prev;return *this;} |
||
76 | const_iterator operator--(int) |
||
77 | {const_iterator tmp(*this);cur=cur->prev;return tmp;} |
||
78 | bool operator!=(const const_iterator& it) |
||
79 | {return cur!=it.cur;} |
||
80 | bool operator==(const const_iterator& it) |
||
81 | {return cur==it.cur;} |
||
82 | const T& operator*() |
||
83 | {return static_cast |
||
84 | const T* operator->() {return &**this;} |
||
85 | }; |
||
86 | iterator erase(iterator it) |
||
87 | { |
||
88 | if (it==end()) return it; |
||
89 | it.cur->prev->next = it.cur->next; |
||
90 | it.cur->next->prev = it.cur->prev; |
||
91 | iterator res(it.cur->next); |
||
92 | delete static_cast<__list_node |
||
93 | --_size; |
||
94 | return res; |
||
95 | } |
||
96 | iterator erase(iterator first, iterator last) |
||
97 | { |
||
98 | while (first!=last) |
||
99 | first=erase(first); |
||
100 | return first; |
||
101 | } |
||
102 | void pop_front(void) {erase(begin());} |
||
103 | class reverse_iterator |
||
104 | { |
||
105 | __list_node_base* cur; |
||
106 | friend class list; |
||
107 | public: |
||
108 | reverse_iterator(){} |
||
109 | reverse_iterator(__list_node_base*c):cur(c){} |
||
110 | reverse_iterator(const reverse_iterator& it): |
||
111 | cur(it.cur){} |
||
112 | reverse_iterator& operator++() |
||
113 | {cur=cur->prev;return *this;} |
||
114 | reverse_iterator operator++(int) |
||
115 | {reverse_iterator tmp(*this); |
||
116 | cur=cur->prev;return tmp;} |
||
117 | bool operator!=(const reverse_iterator& it) |
||
118 | {return cur!=it.cur;} |
||
119 | bool operator==(const reverse_iterator& it) |
||
120 | {return cur==it.cur;} |
||
121 | T& operator*() |
||
122 | {return static_cast<__list_node |
||
123 | }; |
||
124 | class const_reverse_iterator |
||
125 | { |
||
126 | const __list_node_base* cur; |
||
127 | friend class list; |
||
128 | public: |
||
129 | const_reverse_iterator(){} |
||
130 | const_reverse_iterator(const __list_node_base*c):cur(c){} |
||
131 | const_reverse_iterator(const const_reverse_iterator& it): |
||
132 | cur(it.cur){} |
||
133 | const_reverse_iterator& operator++() |
||
134 | {cur=cur->prev;return *this;} |
||
135 | const_reverse_iterator operator++(int) |
||
136 | {const_reverse_iterator tmp(*this); |
||
137 | cur=cur->prev;return tmp;} |
||
138 | bool operator!=(const const_reverse_iterator& it) |
||
139 | {return cur!=it.cur;} |
||
140 | bool operator==(const const_reverse_iterator& it) |
||
141 | {return cur==it.cur;} |
||
142 | const T& operator*() |
||
143 | {return static_cast<__list_node |
||
144 | }; |
||
145 | void push_front(const T& x) |
||
146 | { |
||
147 | __list_node |
||
148 | a->next = head.next; |
||
149 | a->prev = &head; |
||
150 | head.next = a; |
||
151 | a->next->prev = a; |
||
152 | ++_size; |
||
153 | } |
||
154 | void push_back(const T& x) |
||
155 | { |
||
156 | __list_node |
||
157 | a->next = &head; |
||
158 | a->prev = head.prev; |
||
159 | head.prev = a; |
||
160 | a->prev->next = a; |
||
161 | ++_size; |
||
162 | } |
||
163 | iterator begin() {return iterator(head.next);} |
||
164 | const_iterator begin() const {return const_iterator(head.next);} |
||
165 | iterator end() {return iterator(&head);} |
||
166 | const_iterator end() const {return const_iterator(&head);} |
||
167 | reverse_iterator rbegin() |
||
168 | {return reverse_iterator(head.prev);} |
||
169 | reverse_iterator rend() {return reverse_iterator(&head);} |
||
170 | void remove(const T& x) |
||
171 | { |
||
172 | __list_node |
||
173 | static_cast<__list_node |
||
174 | while (a!=&head) |
||
175 | { |
||
176 | __list_node |
||
177 | static_cast<__list_node |
||
178 | if (a->data==x) |
||
179 | { |
||
180 | a->prev->next = a->next; |
||
181 | a->next->prev = a->prev; |
||
182 | delete a; |
||
183 | --_size; |
||
184 | } |
||
185 | a=b; |
||
186 | } |
||
187 | } |
||
188 | unsigned size() const {return _size;} |
||
189 | bool empty() const {return _size==0;} |
||
190 | }; |
||
191 | } |
||
192 | #endif |