#include <iostream>template<class T>class list{private: struct listnode { listnode* prev_; listnode* next_; T data_; listnode() {} listnode(const T& data) : data_(data) {} listnode(listnode* prev, listnode* next) : prev_(prev), next_(next) {} listnode(listnode* prev, listnode* next, const T& data) : prev_(prev), next_(next), data_(data) {} };private: listnode* head_;public: // Give iterators access to the private list::listnode class. friend class const_iterator; friend class iterator; // iterator for const lists. class const_iterator { friend class list; protected: const listnode* node_; public: const_iterator() : node_(0) {} protected: const_iterator(const listnode* node ) : node_(node) {} // All these member functions will be hidden in iterator, not overriden. public: const T& operator*() const { return node_->data_; } const T* operator->() const { return &(node_->data); } const_iterator& operator++() { node_ = node_->next_; return *this; } const_iterator& operator--() { node_ = node_->prev_; return *this; } bool operator==(const const_iterator& rhs) const { return node_ == rhs.node_; } bool operator!=(const const_iterator& rhs) const { return !(*this == rhs); } }; class iterator : // note: public inheritance without virtual destructor because we only use the // default destructor and iterator does not declare any new data members. public const_iterator { friend class list; public: iterator() : const_iterator(0) {} protected: iterator(listnode* node ) : const_iterator(node) {} // All these member functions will be hidden in iterator, not overriden. public: T& operator*() const { return const_cast<T&>(node_->data_); } T* operator->() const { return const_cast<T*>(&(node_->data)); } iterator& operator++() { node_ = node_->next_; return *this; } iterator& operator--() { node_ = node_->prev_; return *this; } };public: list() { // Can't put in init list, since we need the pointer to init the pointee. // It is also advised (Sutter?) not to put new in init lists (leak on exception) head_ = new listnode; head_->prev_ = head_; head_->next_ = head_; } list(const list& rhs) { // Can't put in init list, since we need the pointer to init the pointee. // It is also advised (Sutter?) not to put new in init lists (leak on exception) head_ = new listnode; head_->prev_ = head_; head_->next_ = head_; const_iterator first = rhs.begin(); const_iterator last = rhs.end(); for(;first != last; ++first) push_back(*first); } list(const_iterator first, const_iterator last) { // Can't put in init list, since we need the pointer to init the pointee. // It is also advised (Sutter?) not to put new in init lists (leak on exception) head_ = new listnode; head_->prev_ = head_; head_->next_ = head_; for(;first != last; ++first) push_back(*first); } ~list() { while( !empty() ) erase( begin() ); delete head_; } list& operator=(const list& rhs) { assign(rhs.begin(), rhs.end()); return *this; }public: void swap(list& rhs) { std::swap(head_, rhs.head_); } void assign(const_iterator first, const_iterator last) { list tmp(first, last); swap(tmp); }public: iterator begin() { return iterator(head_->next_); } iterator end() { return iterator(head_); } const_iterator begin() const { return const_iterator(head_->next_); } const_iterator end() const { return const_iterator(head_); } bool empty() const { return head_->next_ == head_; }public: // Insert a new element before the specified location iterator insert(const iterator& itor, const T& data) { listnode* node = const_cast<listnode*>(itor.node_); listnode* newnode = new listnode(node->prev_, node, data); node->prev_->next_ = newnode; node->prev_ = newnode; return iterator(newnode); } // Remove an element at the specified location iterator erase(const iterator& itor) { listnode* node = const_cast<listnode*>(itor.node_); listnode* nextnode = node->next_; node->next_->prev_ = node->prev_; node->prev_->next_ = node->next_; delete node; return iterator(nextnode); }public: void push_back(const T& data) { insert(end(), data); } void pop_back() { erase(--end()); } void push_front(const T& data) { insert(begin(), data); } void pop_front() { erase(begin()); }};template<class T>void swap(list<T>& lhs, list<T>& rhs){ lhs.swap(rhs);}int main(){ list<int> l, ll; std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; l.push_back(2); l.push_front(1); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; list<int>::iterator it; for( it = l.begin(); it != l.end(); ++it ) { std::cout << *it << std::endl; } l.push_front(0); l.push_back(3); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; for( it = l.begin(); it != l.end(); ++it ) { std::cout << *it << std::endl; } l.pop_back(); l.pop_back(); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; for( it = l.begin(); it != l.end(); ++it ) { std::cout << *it << std::endl; } ll = l; l.pop_front(); l.pop_front(); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; for( it = ll.begin(); it != ll.end(); ++it ) { std::cout << *it << std::endl; } ll.pop_front(); ll.pop_front(); std::cout << (ll.empty() ? "list empty" : "list not empty") << std::endl;}MrEvil - Yeah, I should have provided the postfix operators. Didn't bother since it's something trivial to add which wasn't indispensable to the class structure.
I prefer implementing them as follow rather than duplicate the code:
iterator operator++(int){ iterator old = *this; operator++(); return old;}
