MyList.h
#ifndef MY_LIST_H#define MY_LIST_H#includemain.cpp#include //list的节点结构template struct list_node{ typedef list_node * pointer; pointer prev; pointer next; T data;};//list的iteratortemplate struct list_iterator{ //嵌套型别定义 typedef T value_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef list_iterator iterator; typedef list_node * link_type; link_type node; //指向list的节点 list_iterator(link_type p = nullptr) :node(p){}//构造函数 reference operator*() const { return node->data; } //重载运算符* pointer operator->() const { return &(operator*()); }//重载运算符-> iterator operator++(){ //前++ node = node->next; return *this; } iterator operator++(int){//后++ iterator temp = *this; ++*this; return temp; } iterator operator--(){//前-- node = node->prev; return *this; } iterator operator--(int){//后-- iterator temp = *this; --*this; return temp; } bool operator==(const iterator& it){ return node == it.node; }//重载运算符== bool operator!=(const iterator& it){ return node != it.node; }//重载运算符!=};//listtemplate class MyList{public: //嵌套型别定义 typedef T value_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef list_iterator iterator; typedef const list_iterator const_iterator; typedef list_node * link_type;protected: link_type node; //一个指针可以表示整个环状双向链表 std::allocator > alloc;//空间分配器public: MyList();//默认构造函数 MyList(size_type n, const T& value);//构造函数 template MyList(InputIterator first, InputIterator last);//构造函数 ~MyList();//析构函数 MyList(MyList& lst);//拷贝构造函数 MyList& operator=(MyList& lst);//拷贝赋值运算符protected: void empty_initialize(){ node = get_node(); node->prev = node; node->next = node; } link_type get_node(){ return alloc.allocate(1); }//配置一个节点 void put_node(link_type p){ alloc.deallocate(p, 1); }//释放一个节点 link_type create_node(const T& value){//产生一个节点 link_type temp = get_node(); new (&temp->data) T(value); //定位new,在指定地址处构造对象 return temp; } void destroy_node(link_type p){ //销毁一个节点 (&p->data)->~T(); put_node(p); }public: iterator begin(){ return node->next; } const_iterator begin() const { return node->next; } iterator end(){ return node; } const_iterator end() const { return node; } size_type size() const { size_type count = 0; link_type p = node->next; while (p != node){ ++count; p = p->next; } return count; } bool empty() const { return node->next == node; } reference front(){ return *begin(); } const_reference front() const { return *begin(); } reference back(){ return *(--end()); } const_reference back() const { return *(--end()); } void push_back(const T& value); void pop_back(); void push_front(const T& value); void pop_front(); iterator insert(iterator position,const T& value); void insert(iterator position, size_type n, const T& value); iterator erase(iterator position); iterator erase(iterator first, iterator last); void remove(const T& value); void clear(); void splice(iterator position, MyList& lst); void splice(iterator position, MyList& lst, iterator it); void splice(iterator position, MyList& lst, iterator first, iterator last); void merge(MyList& lst); void reverse(); void swap(MyList& lst); void sort(); void unique();protected: void transfer(iterator position, iterator first, iterator last);};//默认构造函数template MyList ::MyList(){ empty_initialize();}//构造函数template MyList ::MyList(size_type n, const T& value){ empty_initialize(); for (; n > 0; --n) insert(end(), value);}构造函数template template MyList ::MyList(InputIterator first, InputIterator last){ empty_initialize(); for (InputIterator it = first; it != last; ++it) insert(end(), *it);}//析构函数template MyList ::~MyList(){ clear(); destroy_node(node); node = nullptr;}//拷贝构造函数template MyList ::MyList(MyList& lst){ empty_initialize(); for (iterator it = lst.begin(); it != lst.end(); ++it) insert(end(), *it);}//拷贝赋值运算符template MyList & MyList ::operator=(MyList& lst){ if (lst != *this){ clear(); for (iterator it = lst.begin(); it != lst.end(); ++it) insert(end(), *it); return *this; }}//push_back(const T& value)template void MyList ::push_back(const T& value){ insert(end(), value);}//pop_back()template void MyList ::pop_back(){ iterator temp = end(); erase(--temp);}//push_front(const T& value)template void MyList ::push_front(const T& value){ insert(begin(), value);}//pop_front()template void MyList ::pop_front(){ erase(begin());}//insert(iterator position, const T& value)template typename MyList ::iterator MyList ::insert(iterator position, const T& value){ link_type p = create_node(value); position.node->prev->next = p; p->prev = position.node->prev; position.node->prev = p; p->next = position.node; return p;}//insert(iterator position, size_type n, const T& value)template void MyList ::insert(iterator position, size_type n, const T& value){ while (n > 0){ insert(position, value); --n; }}//erase(iterator position)template typename MyList ::iterator MyList ::erase(iterator position){ link_type prev_node = position.node->prev; link_type next_node = position.node->next; prev_node->next = next_node; next_node->prev = prev_node; destroy_node(position.node); return iterator(next_node);}//erase(iterator first, iterator last)template typename MyList ::iterator MyList ::erase(iterator first, iterator last){ for (iterator it = first; it != last; ++it) erase(it); return last;}//remove(const T& value)template void MyList ::remove(const T& value){ iterator first = begin(); iterator last = end(); while(first!=last){ iterator next = first; ++next; if (*first == value) erase(first); first = next; }}//clear()template void MyList ::clear(){ for (iterator it = begin(); it != end(); ++it){ iterator next = it; ++next; erase(it); it = next; } node->prev = node; node->next = node;}//transfer(iterator position, iterator first, iterator last)template void MyList ::transfer(iterator position, iterator first, iterator last){ link_type first_node = first.node; link_type befor_last_node = last.node->prev; first_node->prev->next = befor_last_node->next; befor_last_node->next->prev = first_node->prev; position.node->prev->next = first_node; first_node->prev = position.node->prev; befor_last_node->next = position.node; position.node->prev = befor_last_node;}//splice(iterator position, MyList& lst)template void MyList ::splice(iterator position, MyList& lst){ if (!lst.empty()) transfer(position, lst.begin(), lst.end());}//splice(iterator position, MyList& lst, iterator it)template void MyList ::splice(iterator position, MyList& lst, iterator it){ iterator it2 = it; ++it2; if (position == it || position == it2) return; transfer(position, it, it2);}//splice(iterator position, MyList& lst, iterator first, iterator last)template void MyList ::splice(iterator position, MyList& lst, iterator first, iterator last){ if (first != last) transfer(position, first, last);}//merge(MyList& lst)template void MyList ::merge(MyList& lst){ iterator begin1 = begin(); iterator end1 = end(); iterator begin2 = lst.begin(); iterator end2 = lst.end(); while (begin1 != end1&&begin2 != end2){ if (*begin2 < *begin1){ iterator next = begin2; ++next; transfer(begin1, begin2, next); begin2 = next; }else ++begin1; } if (begin2 != end2) transfer(end1, begin2, end2);}//reverse()template void MyList ::reverse(){ if (node->next == node || node->next->next == node) return; iterator first = begin(); ++first; while (first != end()){ iterator old = first; ++first; transfer(begin(), old, first); }}//swap(MyList& lst)template void MyList ::swap(MyList& lst){ if (node != lst.node){ link_type temp = lst.node; lst.node = node; node = temp; }}//sort()template void MyList ::sort(){ if (node->next == node || node->next->next == node) return; MyList carry; MyList counter[64]; int fill = 0; while (!empty()){ carry.splice(carry.begin(), *this, begin()); int i = 0; while (i < fill&&!counter[i].empty()){ counter[i].merge(carry); carry.swap(counter[i++]); } carry.swap(counter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) counter[i].merge(counter[i - 1]); swap(counter[fill - 1]);}template void MyList ::unique(){ iterator first = begin(); iterator last = end(); if (first == last) return; iterator next = first; while (++next != last){ if (*first == *next) erase(next); else first = next; next = first; }}#endif
#include "MyList.h"#includeusing namespace std;int main(){ MyList lst; for (int i = 0; i != 5; ++i) lst.push_back(i); //push_back() for (int i = 5; i != 10; ++i) lst.push_front(i); //push_front() MyList ::iterator it; for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " "; //9 8 7 6 5 0 1 2 3 4 cout << endl; cout << "size:" << lst.size() << endl; //10 size() cout << "front:" << lst.front() << endl; //9 front() cout << "back:" << lst.back() << endl; //4 back() lst.pop_back(); //pop_back() lst.pop_front(); //pop_front() for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " "; //8 7 6 5 0 1 2 3 cout << endl; lst.insert(++lst.begin(), 4, 10); //insert() for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " "; //8 10 10 10 10 7 6 5 0 1 2 3 cout << endl; lst.remove(10); //remove() for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " "; //8 7 6 5 0 1 2 3 cout << endl; lst.erase(++lst.begin()); //erase() for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " "; //8 6 5 0 1 2 3 cout << endl; MyList lst2 = lst;//拷贝赋值运算符 lst.splice(--lst.end(), lst2); //splice() for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " "; //8 6 5 0 1 2 8 6 5 0 1 2 3 3 cout << endl; lst.reverse(); //reverse() for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " ";//3 3 2 1 0 5 6 8 2 1 0 5 6 8 cout << endl; for (int i = 0; i != 5; ++i) lst2.push_back(i); //push_back() lst.swap(lst2);//swap() for (it = lst.begin(); it != lst.end(); ++it) //begin(),end() cout << *it << " ";//0 1 2 3 4 cout << endl; for (it = lst2.begin(); it != lst2.end(); ++it) //begin(),end() cout << *it << " ";//3 3 2 1 0 5 6 8 2 1 0 5 6 8 cout << endl; lst2.clear(); //clear() cout << (lst2.empty() ? "list empty" : "list not empty") << endl; //empty() int ia[] = { 21, 45, 1, 22, 52, 22, 58, 30, 22, 59, 0, 58 }; MyList lst3(begin(ia), end(ia)); //构造函数 for (it = lst3.begin(); it != lst3.end(); ++it) //begin(),end() cout << *it << " "; //21 45 1 22 52 22 58 22 22 59 0 58 cout << endl; lst3.sort(); //sort() for (it = lst3.begin(); it != lst3.end(); ++it) //begin(),end() cout << *it << " "; //0 1 21 22 22 22 22 30 45 52 58 58 59 cout << endl; lst3.unique();//unique() for (it = lst3.begin(); it != lst3.end(); ++it) //begin(),end() cout << *it << " "; //0 1 3 21 22 30 45 52 58 59 cout << endl; system("pause"); return 0;}