| 0,0 → 1,192 |
|---|
| #ifndef _LIST_INCLUDED |
| #define _LIST_INCLUDED |
| #include <stdlib.h> |
| namespace std |
| { |
| struct __list_node_base |
| { |
| __list_node_base* prev; |
| __list_node_base* next; |
| }; |
| template <class T> struct __list_node : __list_node_base |
| { |
| T data; |
| __list_node(const T& d):data(d){} |
| }; |
| template <class T> class list |
| { |
| __list_node_base head; // head.prev = end, head.next = start |
| unsigned _size; |
| public: |
| list():_size(0) {head.prev=head.next=&head;} |
| ~list() {clear();} |
| void clear() |
| { |
| __list_node<T>* a = |
| static_cast<__list_node<T>*>(head.next); |
| while (a!=&head) |
| { |
| __list_node<T>* b = |
| static_cast<__list_node<T>*>(a->next); |
| delete a; |
| a = b; |
| } |
| head.prev = head.next = &head; |
| _size = 0; |
| } |
| class iterator |
| { |
| public: |
| __list_node_base* cur; |
| friend class list; |
| iterator(){} |
| iterator(__list_node_base*c):cur(c){} |
| iterator(const iterator& it):cur(it.cur){} |
| iterator& operator++() |
| {cur=cur->next;return *this;} |
| iterator operator++(int) |
| {iterator tmp(*this);cur=cur->next;return tmp;} |
| iterator& operator--() |
| {cur=cur->prev;return *this;} |
| iterator operator--(int) |
| {iterator tmp(*this);cur=cur->prev;return tmp;} |
| bool operator!=(const iterator& it) |
| {return cur!=it.cur;} |
| bool operator==(const iterator& it) |
| {return cur==it.cur;} |
| T& operator*() |
| {return static_cast<__list_node<T>*>(cur)->data;} |
| T* operator->() {return &**this;} |
| }; |
| class const_iterator |
| { |
| const __list_node_base* cur; |
| friend class list; |
| public: |
| const_iterator(){} |
| const_iterator(const __list_node_base*c):cur(c){} |
| const_iterator(const const_iterator& it):cur(it.cur){} |
| const_iterator(const iterator& it):cur(it.cur){} |
| const_iterator& operator++() |
| {cur=cur->next;return *this;} |
| const_iterator operator++(int) |
| {const_iterator tmp(*this);cur=cur->next;return tmp;} |
| const_iterator& operator--() |
| {cur=cur->prev;return *this;} |
| const_iterator operator--(int) |
| {const_iterator tmp(*this);cur=cur->prev;return tmp;} |
| bool operator!=(const const_iterator& it) |
| {return cur!=it.cur;} |
| bool operator==(const const_iterator& it) |
| {return cur==it.cur;} |
| const T& operator*() |
| {return static_cast<const __list_node<T>*>(cur)->data;} |
| const T* operator->() {return &**this;} |
| }; |
| iterator erase(iterator it) |
| { |
| if (it==end()) return it; |
| it.cur->prev->next = it.cur->next; |
| it.cur->next->prev = it.cur->prev; |
| iterator res(it.cur->next); |
| delete static_cast<__list_node<T>*>(it.cur); |
| --_size; |
| return res; |
| } |
| iterator erase(iterator first, iterator last) |
| { |
| while (first!=last) |
| first=erase(first); |
| return first; |
| } |
| void pop_front(void) {erase(begin());} |
| class reverse_iterator |
| { |
| __list_node_base* cur; |
| friend class list; |
| public: |
| reverse_iterator(){} |
| reverse_iterator(__list_node_base*c):cur(c){} |
| reverse_iterator(const reverse_iterator& it): |
| cur(it.cur){} |
| reverse_iterator& operator++() |
| {cur=cur->prev;return *this;} |
| reverse_iterator operator++(int) |
| {reverse_iterator tmp(*this); |
| cur=cur->prev;return tmp;} |
| bool operator!=(const reverse_iterator& it) |
| {return cur!=it.cur;} |
| bool operator==(const reverse_iterator& it) |
| {return cur==it.cur;} |
| T& operator*() |
| {return static_cast<__list_node<T>*>(cur)->data;} |
| }; |
| class const_reverse_iterator |
| { |
| const __list_node_base* cur; |
| friend class list; |
| public: |
| const_reverse_iterator(){} |
| const_reverse_iterator(const __list_node_base*c):cur(c){} |
| const_reverse_iterator(const const_reverse_iterator& it): |
| cur(it.cur){} |
| const_reverse_iterator& operator++() |
| {cur=cur->prev;return *this;} |
| const_reverse_iterator operator++(int) |
| {const_reverse_iterator tmp(*this); |
| cur=cur->prev;return tmp;} |
| bool operator!=(const const_reverse_iterator& it) |
| {return cur!=it.cur;} |
| bool operator==(const const_reverse_iterator& it) |
| {return cur==it.cur;} |
| const T& operator*() |
| {return static_cast<__list_node<T>*>(cur)->data;} |
| }; |
| void push_front(const T& x) |
| { |
| __list_node<T>* a = new __list_node<T>(x); |
| a->next = head.next; |
| a->prev = &head; |
| head.next = a; |
| a->next->prev = a; |
| ++_size; |
| } |
| void push_back(const T& x) |
| { |
| __list_node<T>* a = new __list_node<T>(x); |
| a->next = &head; |
| a->prev = head.prev; |
| head.prev = a; |
| a->prev->next = a; |
| ++_size; |
| } |
| iterator begin() {return iterator(head.next);} |
| const_iterator begin() const {return const_iterator(head.next);} |
| iterator end() {return iterator(&head);} |
| const_iterator end() const {return const_iterator(&head);} |
| reverse_iterator rbegin() |
| {return reverse_iterator(head.prev);} |
| reverse_iterator rend() {return reverse_iterator(&head);} |
| void remove(const T& x) |
| { |
| __list_node<T>* a = |
| static_cast<__list_node<T>*>(head.next); |
| while (a!=&head) |
| { |
| __list_node<T>* b = |
| static_cast<__list_node<T>*>(a->next); |
| if (a->data==x) |
| { |
| a->prev->next = a->next; |
| a->next->prev = a->prev; |
| delete a; |
| --_size; |
| } |
| a=b; |
| } |
| } |
| unsigned size() const {return _size;} |
| bool empty() const {return _size==0;} |
| }; |
| } |
| #endif |