#include<iostream> using namespace std; template <class T> struct List_Node { List_Node<T>* prev; List_Node<T>* next; T data; }; template <class T> class List { public: class iterator { public: List_Node<T>* node; iterator() {} iterator(List_Node<T>* x) : node(x) {} iterator(const iterator& x) : node(x.node) {} bool operator==(const iterator& x) const { return node == x.node; } bool operator!=(const iterator& x) const { return node != x.node; } T& operator*() const { return (node->data); } T* operator->() const { return &(operator*()); } iterator& operator++() { node = node->next; return *this; } iterator& operator--() { node = node->prev; return *this; } iterator operator++(int) { iterator tmp = *this; node = node->next; return tmp; } iterator operator--(int) { iterator tmp = *this; node = node->prev; return tmp; } }; protected: List_Node<T>* node; protected: void initialize() { node = new List_Node<T>(); node->prev = node; node->next = node; } public: iterator begin() { return node->next; } iterator end() { return node; } bool empty() const { return node->next == node; } T& front() { return *begin(); } T& back() { return *(--end()); } List() { initialize(); } iterator insert(iterator it, const T& x) { List_Node<T>* tmp = new List_Node<T>(); tmp->data = x; tmp->next = it.node; tmp->prev = it.node->prev; it.node->prev->next = tmp; it.node->prev = tmp; return tmp; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator erase(iterator it) { it.node->next->prev = it.node->prev; it.node->prev->next = it.node->next; iterator tmp = it.node->next; delete it.node; return tmp; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } void clear() { List_Node<T>* cur = node->next; while (cur != node) { cur = cur->next; delete cur->prev; } node->prev = node; node->next = node; } void remove(const T& value) { iterator first = begin(); iterator last = end(); while (first != last) { iterator next = first; ++next; if (*first == value) erase(first); first = next; } } }; #define Test #ifdef Test int main() { List<int> l; for (int i = 1; i <= 10; i++) l.push_back(i); for (List<int>::iterator i = l.begin(); i != l.end(); i++) cout << (*i) << ' '; cout << endl; l.remove(5); for (List<int>::iterator i = l.begin(); i != l.end(); i++) cout << (*i) << ' '; return 0; } #endif