list容器的C++代码实现
- #include <iostream>
- using namespace std;
-
- template <class T>
- class mylist;
-
- template <class T>
- class node
- {
- friend class mylist<T>;
- template <class T1>
- friend ostream& operator <<(ostream & out , node<T1> _node);
- public:
- node(T _data)
- {
- data = _data;
- next = NULL;
- prev = NULL;
- }
-
- private:
- T data;
- node<T> *next;
- node<T> *prev;
- };
-
- template <class T>
- ostream& operator <<(ostream & out , node<T> _node)
- {
- out<<_node.data<<' ';
- return out;
- }
- template<class T>
- class mylist
- {
- public:
- typedef bool (*Unperd)(T value);
- typedef bool (*BinPred)(T value);
- typedef bool (*Comp)(T a,T b);
-
- class iterator
- {
- public:
- iterator()
- {
- ptr = NULL;
- }
- iterator(node<T>* _ptr)
- {
- ptr = _ptr;
- }
-
- void operator =(iterator it)
- {
- this->ptr = it.ptr;
- }
-
- bool operator !=(iterator it)
- {
- return this->ptr != it.ptr;
- }
-
- bool operator == (iterator it)
- {
- return this->ptr == it.ptr;
- }
-
- iterator operator ++(int i)
- {
- iterator tmp;
- tmp = *this;
- this->ptr = this->ptr->next;
- return tmp;
- }
-
- node<T> operator *()
- {
- return *(this->ptr);
- }
-
- private:
- node<T> *ptr;
- };
-
-
- class reserve_iterator
- {
- public:
- reserve_iterator()
- {
- ptr = NULL;
- }
- reserve_iterator(node<T>* _ptr)
- {
- ptr = _ptr;
- }
-
- void operator =(reserve_iterator it)
- {
- this->ptr = it.ptr;
- }
- bool operator !=(reserve_iterator it)
- {
- return this->ptr != it.ptr;
- }
- bool operator == (reserve_iterator it)
- {
- return this->ptr == it.ptr;
- }
- reserve_iterator operator ++(int i)
- {
- reserve_iterator tmp;
- tmp = *this;
- this->ptr = this->ptr->prev;
- return tmp;
- }
- node<T> operator *()
- {
- return *(this->ptr);
- }
- private:
- node<T> *ptr;
- };
-
- mylist()
- {
- head = NULL;
- curr = NULL;
- }
-
- mylist(int num,T value)
- {
- head = new node<T>(value);
- curr = head;
- int i;
- node<T>* newnode = NULL;
- for (i = 0; i < num;i++)
- {
- newnode = new node<T>(value);
- curr->next = newnode;
- newnode->prev = curr;
- curr = newnode;
- newnode = NULL;
- }
- curr->next = head;
- head->prev = curr;
- }
-
- mylist(mylist & list)
- {
- node<T>* point = list.head->next;
- this->head = new node<T>(point->data);
- this->curr = this->head;
- node<T> * newnode = NULL;
- while (point != list.head)
- {
- newnode = new node<T>(point->data);
- this->curr->next = newnode;
- newnode->prev = this->curr;
- this->curr = newnode;
- newnode = NULL;
- point = point->next;
- }
- this->curr->next = this->head;
- this->head->prev = this->curr;
- }
-
-
-
- mylist(iterator start,iterator end)
- {
- iterator point = start;
- head = new node<T>(*point);
- curr = head;
- node<T> * newnode = NULL;
- while (point != end)
- {
- newnode = new node<T>(*point);
- curr->next = newnode;
- newnode->prev = curr;
- curr = newnode;
- newnode = NULL;
- point++;
- }
- curr->next = head;
- head->prev = curr;
- }
-
-
- void assign(iterator start,iterator end)
- {
- iterator point = start;
- if (NULL == head)
- {
- this->head = new node<T>(*point);
- curr = head;
- }
- else
- {
- curr = head->prev;
- }
-
- node<T> * newnode = NULL;
- while (point != end)
- {
- newnode = new node<T>(*point);
- curr->next = newnode;
- newnode->prev = curr;
- curr = newnode;
- newnode = NULL;
- point++;
- }
- curr->next = head;
- head->prev = curr;
- }
-
- void assign(int num,const T & value)
- {
- if (NULL == head)
- {
- head = new node<T>(value);
- curr = head;
- }
- else
- {
- curr = head->prev;
- }
- int i;
- node<T>* newnode = NULL;
- for (i = 0; i < num;i++)
- {
- newnode = new node<T>(value);
- curr->next = newnode;
- newnode->prev = curr;
- curr = newnode;
- newnode = NULL;
- }
- curr->next = head;
- head->prev = curr;
- }
-
- T& back()
- {
- return head->prev->data;
- }
-
- void clear()
- {
- curr = head->next;
- head->next = NULL;
- node<T>* tmp;
- while (curr != head)
- {
- tmp = curr;
- curr = curr->next;
- head->next = curr;
- if (NULL != curr)
- {
- curr->prev = head;
- }
- free(tmp);
- tmp = NULL;
- }
- }
-
- bool empty()
- {
- if (head->next == head)
- return true;
- return false;
- }
-
- iterator begin()
- {
- return iterator(head->next);
- }
-
- iterator end()
- {
- return iterator(head);
- }
-
-
- reserve_iterator rebegin()
- {
- return reserve_iterator(head->prev);
- }
-
-
- reserve_iterator rend()
- {
- return reserve_iterator(head);
- }
-
-
- iterator find(const T &value)
- {
- curr = head->next;
- int flag = 0;
- while (curr != head)
- {
- if (curr->data == value)
- {
- flag = 1;
- return iterator(curr);
- break;
- }
- curr = curr->next;
- }
- if (flag == 0)
- {
- return iterator();
- }
- }
-
-
-
- iterator erase(iterator pos)
- {
- node<T>* tmp = head;
- curr = head->next;
- while (curr != head)
- {
- if (iterator(curr) == pos)
- {
- tmp->next = curr->next;
- curr->next->prev = tmp;
- return iterator(curr->next);
- free(curr);
- curr = NULL;
- break;
- }
- else
- {
- tmp = curr;
- }
- curr = curr->next;
- }
- }
-
- iterator erase(iterator start,iterator end)
- {
- node<T>* tmp = head;
- curr = head->next;
- while (curr != head)
- {
- if (iterator(tmp) == start)
- {
- while (iterator(curr) != end)
- {
- tmp->next = curr->next;
- curr->next->prev = tmp;
- free(curr);
- curr = NULL;
- curr = tmp->next;
- }
- return iterator(curr);
- break;
- }
- else
- {
- tmp = curr;
- }
- curr = curr->next;
- }
- }
-
-
- T & front()
- {
- return head->next->data;
- }
-
-
- iterator insert(iterator pos,const T& value)
- {
- node<T>* newnode = new node<T>(value);
- curr = head->next;
- while (curr != head)
- {
-
- if (iterator(head) == pos)
- {
- head->prev->prev->next = newnode;
- newnode->prev = head->prev->prev;
- head->prev->prev = newnode;
- newnode->next = head->prev;
- return iterator(head->prev);
- break;
- }
- if (iterator(curr) == pos)
- {
- curr->prev->next = newnode;
- newnode->prev = curr->prev;
- curr->prev = newnode;
- newnode->next = curr;
- break;
- }
- curr = curr->next;
- }
- }
-
- void insert(iterator pos,int num,const T &value)
- {
- node<T>* newnode;
- curr = head->next;
- node<T>* tmp = head;
- if (iterator(head) == pos)
- {
- tmp = head->prev->prev;
- curr = head->prev;
- while (0 != num)
- {
- newnode = new node<T>(value);
- tmp->next = newnode;
- newnode->prev = tmp;
- tmp = newnode;
- newnode = NULL;
- num--;
- }
- tmp->next = curr;
- curr->prev = tmp;
- }
- else
- {
- while (curr != head)
- {
- if (iterator(curr) == pos)
- {
- while (0 != num)
- {
- newnode = new node<T>(value);
- tmp->next = newnode;
- newnode->prev = tmp;
- tmp = newnode;
- newnode = NULL;
- num--;
- }
- tmp->next = curr;
- curr->prev = tmp;
- break;
- }
- else
- {
- tmp =curr;
- }
- curr = curr->next;
- }
- }
- }
-
- void pop_back()
- {
- curr = head->prev;
- node<T>* tmp = head->prev->prev;
- tmp->next = head;
- head->prev = tmp;
- free(curr);
- curr = NULL;
- }
-
- void pop_front()
- {
- curr = head->next;
- node<T>* tmp = head->next->next;
- head->next = tmp;
- tmp->prev = head;
- free(curr);
- curr = NULL;
- }
-
- void push_back(const T& value)
- {
- node<T>* newnode = new node<T>(value) ;
- if (head == NULL)
- {
- head = new node<T>(value);
- curr = head;
- }
- else
- {
- curr = head->prev;
- }
- curr->next = newnode;
- newnode->prev = curr;
- curr = newnode;
- newnode = NULL;
- curr->next = head;
- head->prev = curr;
- }
-
- void push_front(const T& value)
- {
- node<T>* newnode = new node<T>(value) ;
- if (head == NULL)
- {
- head = new node<T>(value);
- curr = head;
- curr->next = newnode;
- newnode->next = curr;
- curr = newnode;
- newnode = NULL;
- curr->next = head;
- head->prev = curr;
- }
- else
- {
- curr = head;
- newnode->next = curr->next;
- curr->next = newnode;
- curr = newnode;
- newnode = NULL;
- curr->prev = head;
- curr->next->prev = curr;
- }
- }
-
- void remove(const T & value)
- {
- node<T>* tmp = head;
- curr = head->next;
- while (curr != head)
- {
- if (curr->data == value)
- {
- tmp->next = curr->next;
- curr->next->prev = tmp;
- free(curr);
- curr = NULL;
- curr = tmp;
- }
- else
- {
- tmp = curr;
- }
- curr = curr->next;
- }
- }
-
- void remove_if(Unperd pr)
- {
- node<T>* tmp = head;
- curr = head->next;
- while (curr != head)
- {
- if (pr(curr->data))
- {
- tmp->next = curr->next;
- curr->next->prev = tmp;
- free(curr);
- curr = NULL;
- curr = tmp;
- }
- else
- {
- tmp = curr;
- }
- curr = curr->next;
- }
- }
-
-
- void resize(int num,T value)
- {
- int record = 0;
- curr = head->next;
- iterator point;
- while (curr != head)
- {
- ++record;
- if (record == num)
- {
- point = iterator(curr);
- }
- curr = curr->next;
- }
- if (record < num)
- {
- while (record != num)
- {
- node<T>* newnode = new node<T>(value);
- curr = head->prev;
- curr->next = newnode;
- newnode->prev = curr;
- curr = newnode;
- newnode = NULL;
- curr->next = head;
- head->prev = curr;
- record++;
- }
- }
- if (record > num)
- {
- erase(point,iterator(head));
- }
- }
-
-
- void reverse()
- {
- mylist<T> list(*this);
- node<T>* tmp = list.head->prev;
- this->curr = this->head->next;
- while (this->curr != this->head)
- {
- this->curr->data = tmp->data;
- tmp = tmp->prev;
- this->curr = this->curr->next;
- }
- }
-
-
- int size()
- {
- curr = head->next;
- int num = 0;
- while (curr != head)
- {
- num++;
- curr = curr->next;
- }
- return num;
- }
-
-
- void sort()
- {
- curr = head->next;
- node<T>* tmp;
- tmp = head->next->next;
- int temp = 0;
- int n = size();
- int i = 0;
- int flag = 0;
- while (tmp != head)
- {
- if (curr->data > tmp->data)
- {
- flag = 1;
- temp = tmp->data;
- tmp->data = curr->data;
- curr->data = temp;
- }
- i++;
- curr = curr->next;
- tmp = tmp->next;
- if ((i == n-1)&&(flag == 1))
- {
- flag = 0;
- i = 0;
- curr = head->next;
- tmp = head->next->next;
- }
- }
- }
-
-
- void sort(Comp compfunction)
- {
- curr = head->next;
- node<T>* tmp;
- tmp = head->next->next;
- int temp = 0;
- int n = size();
- int i = 0;
- int flag = 0;
- while (tmp != head)
- {
- if (compfunction(curr->data,tmp->data))
- {
- flag = 1;
- temp = tmp->data;
- tmp->data = curr->data;
- curr->data = temp;
- }
- i++;
- curr = curr->next;
- tmp = tmp->next;
- if ((i == n-1)&&(flag == 1))
- {
- flag = 0;
- i = 0;
- curr = head->next;
- tmp = head->next->next;
- }
- }
- }
-
- void splice(iterator pos,mylist & list)
- {
- this->curr = this->head->next;
- node<T>* tmp = this->head;
- while (this->curr != this->head)
- {
- if (iterator(this->curr) == pos)
- {
- tmp->next = list.head->next;
- list.head->prev->next = this->curr->next;
- this->curr->next->prev = list.head->prev;
- list.head->prev = tmp;
- free(this->curr);
- this->curr = NULL;
- free(list.head);
- list.head = NULL;
- break;
- }
- else
- {
- tmp = this->curr;
- }
- this->curr = this->curr->next;
- }
- }
-
-
- void splice(iterator pos,mylist & list,iterator del)
- {
- this->curr = this->head->next;
- list.curr = list.head->next;
- node<T>* tmp = list.head;
- while (this->curr != this->head)
- {
- if (iterator(this->curr) == pos)
- {
- while (list.curr != list.head)
- {
- if (iterator(list.curr) == del)
- {
- this->curr->data = list.curr->data;
- tmp->next = list.curr->next;
- curr->next->prev = tmp;
- free(list.curr);
- list.curr;
- break;
- }
- else
- {
- tmp = list.curr;
- }
- list.curr = list.curr->next;
- }
- break;
- }
- this->curr = this->curr->next;
- }
- }
-
-
- void splice(iterator pos,mylist & list,iterator start,iterator end)
- {
- list.curr = list.head;
- node<T>* point = list.head;
- node<T>* point1 = list.head;
- iterator it = this->erase(pos);
- while (iterator(list.curr) != start)
- {
- list.curr = list.curr->next;
- }
- point = list.curr->prev;
- while(iterator(list.curr->prev) != end)
- {
- this->insert(it,list.curr->data);
- list.curr = list.curr->next;
- }
- point1 = list.curr;
- list.erase(point,point1);
- }
-
- void swap(mylist & list)
- {
- int flag1 = 0;
- int flag2 = 0;
- mylist<T> tmp(list);
- list.curr = list.head->next;
- this->curr = this->head->next;
- while (this->curr != this->head)
- {
- if (list.curr != list.head)
- {
- list.curr->data = this->curr->data;
- list.curr = list.curr->next;
- }
- else
- {
- flag1 = 1;
- list.push_back(this->curr->data);
- }
- this->curr = this->curr->next;
- }
- if ((list.curr != list.head)&& (flag1 == 0))
- {
- list.erase(iterator(list.curr->prev),iterator(list.head));
- }
- tmp.curr = tmp.head->next;
- this->curr = this->head->next;
- while (tmp.curr != tmp.head)
- {
- if (this->curr != this->head)
- {
- this->curr->data = tmp.curr->data;
- this->curr = this->curr->next;
- }
- else
- {
- flag2 = 1;
- this->push_back(tmp.curr->data);
- }
- tmp.curr = tmp.curr->next;
- }
- if ((this->curr != this->head)&& (flag2 == 0))
- {
- this->erase(iterator(this->curr->prev),iterator(this->head));
- }
- }
-
-
- void unique()
- {
- curr = head->next->next;
- node<T>* tmp = head->next;
- while (curr != head)
- {
- if (tmp->data == curr->data)
- {
- tmp->next = curr->next;
- curr->next->prev = tmp;
- free(curr);
- curr = NULL;
- curr = tmp->next;
- }
- tmp = tmp->next;
- curr = curr->next;
- }
- }
-
- void unique(BinPred pr)
- {
- curr = head->next->next;
- node<T>* tmp = head->next;
- while (curr != head)
- {
- if ((tmp->data == curr->data)&&pr(curr->data))
- {
- tmp->next = curr->next;
- curr->next->prev = tmp;
- free(curr);
- curr = NULL;
- curr = tmp->next;
- }
- tmp = tmp->next;
- curr = curr->next;
- }
- }
- private:
- node<T> *head;
- node<T> *curr;
- };
-
- template <class T>
- bool dis_tinet( T value)
- {
- if (9 == value)
- return true;
- return false;
- }
- template <class T>
- bool sortfunction(T a,T b)
- {
- if (a < b)
- return true;
- return false;
- }
- template <class T>
- bool unique_t( T value)
- {
- if (8 == value)
- return true;
- return false;
- }
原文地址:https://www.cnblogs.com/jdxn/p/6759303.html