MyList.h
#ifndef MY_LIST_H
#define MY_LIST_H
#include<cstddef>
#include<memory>
//list的节点结构
template<typename T>
struct list_node{
typedef list_node<T>* pointer;
pointer prev;
pointer next;
T data;
};
//list的iterator
template<typename T>
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<T> iterator;
typedef list_node<T>* 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; }//重载运算符!=
};
//list
template<typename T>
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<T> iterator;
typedef const list_iterator<T> const_iterator;
typedef list_node<T>* link_type;
protected:
link_type node; //一个指针可以表示整个环状双向链表
std::allocator<list_node<T>> alloc;//空间分配器
public:
MyList();//默认构造函数
MyList(size_type n, const T& value);//构造函数
template<typename InputIterator>
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<typename T>
MyList<T>::MyList(){
empty_initialize();
}
//构造函数
template<typename T>
MyList<T>::MyList(size_type n, const T& value){
empty_initialize();
for (; n > 0; --n)
insert(end(), value);
}
////构造函数
template<typename T>
template<typename InputIterator>
MyList<T>::MyList(InputIterator first, InputIterator last){
empty_initialize();
for (InputIterator it = first; it != last; ++it)
insert(end(), *it);
}
//析构函数
template<typename T>
MyList<T>::~MyList(){
clear();
destroy_node(node);
node = nullptr;
}
//拷贝构造函数
template<typename T>
MyList<T>::MyList(MyList& lst){
empty_initialize();
for (iterator it = lst.begin(); it != lst.end(); ++it)
insert(end(), *it);
}
//拷贝赋值运算符
template<typename T>
MyList<T>& MyList<T>::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<typename T>
void MyList<T>::push_back(const T& value){
insert(end(), value);
}
//pop_back()
template<typename T>
void MyList<T>::pop_back(){
iterator temp = end();
erase(--temp);
}
//push_front(const T& value)
template<typename T>
void MyList<T>::push_front(const T& value){
insert(begin(), value);
}
//pop_front()
template<typename T>
void MyList<T>::pop_front(){
erase(begin());
}
//insert(iterator position, const T& value)
template<typename T>
typename MyList<T>::iterator MyList<T>::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<typename T>
void MyList<T>::insert(iterator position, size_type n, const T& value){
while (n > 0){
insert(position, value);
--n;
}
}
//erase(iterator position)
template<typename T>
typename MyList<T>::iterator MyList<T>::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 T>
typename MyList<T>::iterator MyList<T>::erase(iterator first, iterator last){
for (iterator it = first; it != last; ++it)
erase(it);
return last;
}
//remove(const T& value)
template<typename T>
void MyList<T>::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<typename T>
void MyList<T>::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<typename T>
void MyList<T>::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<typename T>
void MyList<T>::splice(iterator position, MyList& lst){
if (!lst.empty())
transfer(position, lst.begin(), lst.end());
}
//splice(iterator position, MyList& lst, iterator it)
template<typename T>
void MyList<T>::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<typename T>
void MyList<T>::splice(iterator position, MyList& lst, iterator first, iterator last){
if (first != last)
transfer(position, first, last);
}
//merge(MyList& lst)
template<typename T>
void MyList<T>::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<typename T>
void MyList<T>::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<typename T>
void MyList<T>::swap(MyList& lst){
if (node != lst.node){
link_type temp = lst.node;
lst.node = node;
node = temp;
}
}
//sort()
template<typename T>
void MyList<T>::sort(){
if (node->next == node || node->next->next == node)
return;
MyList<T> carry;
MyList<T> 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<typename T>
void MyList<T>::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"
#include<iostream>
using namespace std;
int main(){
MyList<int> 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<int>::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<int> 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<int> 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;
}