MyList.h
#ifndef MY_LIST_H
#define MY_LIST_H
#include<memory>
//list的node结构
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{
//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;
list_node<T>* node;//指向list的节点
list_iterator(list_node<T>* 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 tmp = *this;
++*this;
return tmp;
}
iterator& operator--(){ //前--
node = node->prev;
return *this;
}
iterator operator--(int){ //后--
iterator tmp = *this;
--*this;
return tmp;
}
bool operator==(const iterator& x) const { return node == x.node; } //重载运算符==
bool operator!=(const iterator& x) const { return node != x.node; } //重载运算符!=
};
//list
template<typename T>
class MyList{
public:
//list的嵌套型别定义
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef list_iterator<T> iterator;
typedef const list_iterator<T> const_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
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<T>(const MyList& lst);
MyList<T>& operator=(const MyList& lst);
protected:
void empty_initialize();
link_type get_node(){ return alloc.allocate(1); }//配置一个节点
void put_node(link_type p){ alloc.deallocate(p, 1); } //释放一个节点
link_type create_node(const T& t){ //产生一个节点
link_type p = get_node();
new (&p->data) T(t); //定位new,在指定地址处构造对象
return p;
}
void destroy_node(link_type p){ //销毁一个节点
(&p->data)->~T();
put_node(p);
}
public:
iterator begin(){ return iterator(node->next); }
const_iterator begin() const { return iterator(node->next); }
iterator end(){ return iterator(node); }
const_iterator end() const { return iterator(node); }
size_type size() const {
size_type result = 0;
link_type p = node->next;
while (p != node){
++result;
p = p->next;
}
return result;
}
bool empty() const { return node->next == node; }
reference front(){ return node->next->data; }
reference back(){ return node->prev->data; }
void push_back(const T& t);
void pop_back();
void push_front(const T& t);
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& x);
void splice(iterator position, MyList&, iterator i);
void splice(iterator position, MyList&, iterator first, iterator last);
void merge(MyList& x);
void reverse();
void swap(MyList& x);
void sort();
protected:
void transfer(iterator position, iterator first, iterator last);
};
template<typename T>
void MyList<T>::empty_initialize(){
node = get_node();
node->next = node->prev = node;
}
//默认构造函数
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(begin(), 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(const MyList& lst){
empty_initialize();
for (iterator it = lst.begin(); it != lst.end(); ++it)
insert(end(), *it);
}
//拷贝赋值运算符
template<typename T>
MyList<T>& MyList<T>::operator=(const MyList& lst){
if (this != &lst){
clear();
for (iterator it = lst.begin(); it != lst.end(); ++it)
insert(end(), *it);
return *this;
}
}
//push_back(const T& t)
template<typename T>
void MyList<T>::push_back(const T& t){
insert(end(), t);
}
//pop_back()
template<typename T>
void MyList<T>::pop_back(){
iterator temp = end();
erase(--temp);
}
//push_front(const T& t)
template<typename T>
void MyList<T>::push_front(const T& t){
insert(begin(), t);
}
//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);
p->next = position.node;
p->prev = position.node->prev;
position.node->prev->next = p;
position.node->prev = p;
return iterator(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 next_node = position.node->next;
link_type pre_node = position.node->prev;
pre_node->next = next_node;
next_node->prev = pre_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){
while (first != last)
erase(first++);
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(){
//link_type cur = (link_type)node->next; //STL源码版本
//while (cur != node){
// link_type temp = cur;
// cur = (link_type)cur->next;
// destroy_node(temp);
//}
//node->next = node; //恢复原始状态
//node->prev = node;
iterator first = begin(); //我觉得用erase()也可完成clear()函数
iterator last = end();
while (first != last){
iterator next = first;
++next;
erase(first);
first = next;
}
}
//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 before_last_node = last.node->prev;
first_node->prev->next = last.node;
last.node->prev = first_node->prev;
position.node->prev->next = first_node;
first_node->prev = position.node->prev;
before_last_node->next = position.node;
position.node->prev = before_last_node;
}
//splice(iterator position, MyList<T>& x)
template<typename T>
void MyList<T>::splice(iterator position, MyList& x){
if (!x.empty())
transfer(position, x.begin(), x.end());
}
//splice(iterator position, MyList<T>& x, iterator i)
template<typename T>
void MyList<T>::splice(iterator position, MyList&, iterator i){
iterator j = i;
++j;
if (position == i || position == j) return;
transfer(position, i, j);
}
//splice(iterator position, MyList& x, iterator first, iterator last)
template<typename T>
void MyList<T>::splice(iterator position, MyList&, iterator first, iterator last){
if (first != last)
transfer(position, firs, last);
}
//merge(MyList<T>& x)
template<typename T>
void MyList<T>::merge(MyList& x){
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
while (first1 != last1 && first2 != last2){
if (*first2 < *first1){
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
}
else
++first1;
}
if (first2 != last2)
transfer(last1, first2, last2);
}
//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;
transfer(begin(), old, ++first);
}
}
//swap(MyList& x)
template<typename T>
void MyList<T>::swap(MyList& x){
if (node != x.node){
link_type temp = node;
node = x.node;
x.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]);
}
#endif#ifndef MY_Queue_H
#define MY_Queue_H
#include"MyList.h"
template<typename T, typename Sequence = MyList<T>>
class MyQueue{
private:
Sequence lst;
public:
bool empty()const{ return lst.empty(); }
int size()const{ return lst.size(); }
T front(){ return lst.front(); }
T back(){ return lst.back(); }
void push(const T& t){
lst.push_back(t);
}
void pop(){
lst.pop_front();
}
};
#endif
#include"MyQueue.h"
#include<iostream>
using namespace std;
int main(){
MyQueue<int> que;
cout << (que.empty() ? "empty" : "not empty") << endl; //empty
for (int i = 0; i != 5; ++i)
que.push(i);
cout << "front:" << que.front() << endl; //0
cout << "back:" << que.back() << endl;//4
cout << "size:" << que.size() << endl;//5
que.pop();
cout << "front:" << que.front() << endl;//1
cout << "back:" << que.back() << endl;//4
cout << "size:" << que.size() << endl;//4
system("pause");
return 0;
}