C++简易list

#ifndef __MYLIST_H__ #define __MYLIST_H__ // list节点 template <class Type> class list_node { public: list_node<Type> *prev; list_node<Type> *next; Type data; }; // list迭代器 template <class Type> class list_iterator { public: // 迭代器必须定义的五个相应类型 typedef Type value_type; typedef Type* pointer; typedef Type& reference; typedef size_t difference_type; typedef std::bidirectional_iterator_tag iterator_category; list_iterator() : node(NULL) {} list_iterator(list_node<Type> *x) : node(x) {} list_iterator(const list_iterator<Type> &x) : node(x.node) {} // 成员函数尽量加const bool operator== (const list_iterator<Type> &rhs) const { return node == rhs.node; } bool operator!= (const list_iterator<Type> &rhs) const { return !(operator==(rhs)); // 调用现有函数，好的策略 } // 对迭代器接引用返回指向数据的引用 reference operator* () const { return node->data; } pointer operator-> () const { return &(operator*()); // 调用现有函数，好的策略 } list_iterator& operator++ () { node = node->next; return *this; } list_iterator operator++ (int) { list_iterator<Type> old = *this; ++(*this); return old; } list_iterator& operator-- () { node = node->prev; return *this; } list_iterator operator-- (int) { list_iterator<Type> old = *this; --(*this); return old; } // 迭代器通过这个指针与某个节点相联系 list_node<Type> *node; }; // list数据结构，SGI中的list是一个环形链表，这里相同 // list内部使用list_node访问每一个保存数据的节点，对外则返回给用户一个list_iterator迭代器，这是需要注意的 template <class Type> class List { public: typedef list_iterator<Type> iterator; // iterator类型是每个容器必备的，应该尽早定义它 typedef size_t size_type; // 构造函数 List() { node = get_node(); // 前后指针都指向自己，表示此list为空 node->next = node; node->prev = node; } iterator begin() { return (list_iterator<Type>)node->next; } iterator end() { return (list_iterator<Type>)node; } bool empty() { return node->next == node; // 参见默认构造函数 } size_type size() { size_type len = 0; distance(begin(), end(), len); return len; } Type& front() { return *begin(); } Type& back() { return *(--end()); } // 插入操作 iterator insert(iterator position, const Type &value) { list_node<Type> *newNode = create_node(value); newNode->next = position.node; newNode->prev = position.node->prev; position.node->prev->next = newNode; position.node->prev = newNode; return (iterator)newNode; // 显示类型转换 } void push_back(const Type &value) { insert(end(), value); } void push_front(const Type &value) { insert(begin(), value); } // 删除操作 iterator erase(iterator position) { list_node<Type> *next = position.node->next; list_node<Type> *prev = position.node->prev; prev->next = next; next->prev = prev; destroy_node(position.node); return (iterator)next; } void pop_back() { iterator tmp = end(); erase(--tmp); } void pop_front() { erase(begin()); } // 清除所有节点 void clear() { list_node<Type> *pnode = node->next; while (pnode != node) { list_node<Type> *tmp = pnode->next; destroy_node(pnode); pnode = tmp; } node->next = node; node->prev = node; } // 删除值为value的所有节点 void remove(const Type &value) { // 为了使用上面的erase，这里定义iterator而不是list_node iterator first = begin(); iterator last = end(); while (first != last) { iterator next = first; ++next; if (*first == value) erase(first); first = next; } } private: // 分配一个节点 list_node<Type>* get_node() { return alloc.allocate(1); } // 释放一个节点 void put_node(list_node<Type> *p) { alloc.deallocate(p, 1); } // 分配并构造一个节点 list_node<Type>* create_node(const Type &value) { list_node<Type> *p = get_node(); alloc.construct(&(p->data), value); return p; } // 析构并释放一个节点 void destroy_node(list_node<Type> *p) { alloc.destroy(&(p->data)); put_node(p); } private: list_node<Type> *node; // 空白节点，指向list.end() static std::allocator< list_node<Type> > alloc; // 空间配置器 }; // 类中的静态成员一定要记得在类外定义，否则链接时会出错 template <class Type> std::allocator< list_node<Type> > List<Type>::alloc; #endif

~List() { clear(); if (node != NULL) delete node; }

int main() { List<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); l.push_back(5); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 3 4 5 List<int>::iterator iter = find(l.begin(), l.end(), 3); iter = l.erase(iter); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 4 5 l.insert(iter, 123); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 123 4 5 l.push_front(0); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 0 1 2 123 4 5 l.pop_back(); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 0 1 2 123 4 l.pop_front(); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 123 4 l.clear(); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // null l.push_back(1); l.push_back(2); l.push_back(3); l.push_front(4); l.push_front(5); l.push_front(6); l.remove(1); l.remove(2); l.remove(3); l.remove(5); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; system("pause"); return 0; }