367 lines
5.4 KiB
C++
367 lines
5.4 KiB
C++
|
#pragma once
|
|||
|
|
|||
|
|
|||
|
#include <iostream>
|
|||
|
#include <assert.h>
|
|||
|
|
|||
|
using namespace std;
|
|||
|
|
|||
|
namespace Lenyiin
|
|||
|
{
|
|||
|
template <class T>
|
|||
|
struct __list_node
|
|||
|
{
|
|||
|
__list_node<T>* _next; // ָ<><D6B8><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD>ָ<EFBFBD><D6B8>
|
|||
|
__list_node<T>* _prev; // ָ<><D6B8>ǰһ<C7B0><D2BB><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD>ָ<EFBFBD><D6B8>
|
|||
|
T _data; // <20>ڵ<EFBFBD><DAB5>洢<EFBFBD><E6B4A2><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
|||
|
__list_node(const T& data = T())
|
|||
|
: _data(data), _next(nullptr), _prev(nullptr)
|
|||
|
{}
|
|||
|
};
|
|||
|
|
|||
|
template <class T, class Ref, class Ptr>
|
|||
|
struct __list_iterator
|
|||
|
{
|
|||
|
typedef __list_node<T> Node;
|
|||
|
typedef __list_iterator<T, Ref, Ptr> Self;
|
|||
|
|
|||
|
Node* _node;
|
|||
|
|
|||
|
// Ĭ<>Ϲ<EFBFBD><CFB9><EFBFBD>
|
|||
|
__list_iterator(Node* node)
|
|||
|
: _node(node)
|
|||
|
{
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// *it
|
|||
|
Ref operator*()
|
|||
|
{
|
|||
|
return _node->_data;
|
|||
|
}
|
|||
|
|
|||
|
// it ->
|
|||
|
Ptr operator->()
|
|||
|
{
|
|||
|
return &_node->_data;
|
|||
|
}
|
|||
|
|
|||
|
// ++it
|
|||
|
Self& operator++()
|
|||
|
{
|
|||
|
_node = _node->_next;
|
|||
|
return *this;
|
|||
|
}
|
|||
|
|
|||
|
// it++
|
|||
|
Self operator++(int)
|
|||
|
{
|
|||
|
Self tmp(*this);
|
|||
|
++(*this);
|
|||
|
return tmp;
|
|||
|
}
|
|||
|
|
|||
|
// --it
|
|||
|
Self& operator--()
|
|||
|
{
|
|||
|
_node = _node->_prev;
|
|||
|
return *this;
|
|||
|
}
|
|||
|
|
|||
|
// it--
|
|||
|
Self operator--(int)
|
|||
|
{
|
|||
|
Self tmp(*this);
|
|||
|
--(*this);
|
|||
|
return tmp;
|
|||
|
}
|
|||
|
|
|||
|
// it != end()
|
|||
|
bool operator!=(const Self& it)
|
|||
|
{
|
|||
|
return _node != it._node;
|
|||
|
}
|
|||
|
|
|||
|
bool operator==(const Self& it)
|
|||
|
{
|
|||
|
return _node == it._node;
|
|||
|
}
|
|||
|
};
|
|||
|
|
|||
|
template <class T, class Ref, class Ptr>
|
|||
|
struct __list_reverse_iterator
|
|||
|
{
|
|||
|
typedef __list_node<T> Node;
|
|||
|
typedef __list_reverse_iterator<T, Ref, Ptr> Self;
|
|||
|
|
|||
|
Node* _node;
|
|||
|
|
|||
|
// Ĭ<>Ϲ<EFBFBD><CFB9><EFBFBD>
|
|||
|
__list_reverse_iterator(Node* node)
|
|||
|
: _node(node)
|
|||
|
{
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// *it
|
|||
|
Ref operator*()
|
|||
|
{
|
|||
|
return _node->_data;
|
|||
|
}
|
|||
|
|
|||
|
// it ->
|
|||
|
Ptr operator->()
|
|||
|
{
|
|||
|
return &_node->_data;
|
|||
|
}
|
|||
|
|
|||
|
// ++it
|
|||
|
Self& operator++()
|
|||
|
{
|
|||
|
_node = _node->_prev;
|
|||
|
return *this;
|
|||
|
}
|
|||
|
|
|||
|
// it++
|
|||
|
Self operator++(int)
|
|||
|
{
|
|||
|
Self tmp(*this);
|
|||
|
++(*this);
|
|||
|
return tmp;
|
|||
|
}
|
|||
|
|
|||
|
// --it
|
|||
|
Self& operator--()
|
|||
|
{
|
|||
|
_node = _node->_next;
|
|||
|
return *this;
|
|||
|
}
|
|||
|
|
|||
|
// it--
|
|||
|
Self operator--(int)
|
|||
|
{
|
|||
|
Self tmp(*this);
|
|||
|
--(*this);
|
|||
|
return tmp;
|
|||
|
}
|
|||
|
|
|||
|
// it != end()
|
|||
|
bool operator!=(const Self& it)
|
|||
|
{
|
|||
|
return _node != it._node;
|
|||
|
}
|
|||
|
|
|||
|
bool operator==(const Self& it)
|
|||
|
{
|
|||
|
return _node == it._node;
|
|||
|
}
|
|||
|
};
|
|||
|
|
|||
|
template <class T>
|
|||
|
class List
|
|||
|
{
|
|||
|
typedef __list_node<T> Node;
|
|||
|
|
|||
|
public:
|
|||
|
typedef __list_iterator<T, T&, T*> iterator;
|
|||
|
typedef __list_iterator<T, const T&, const T*> const_iterator;
|
|||
|
typedef __list_reverse_iterator<T, T&, T*> reverse_iterator;
|
|||
|
typedef __list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;
|
|||
|
|
|||
|
iterator begin() // <20><><EFBFBD><EFBFBD>ͷ<EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>
|
|||
|
{
|
|||
|
return iterator(_head->_next);
|
|||
|
}
|
|||
|
|
|||
|
iterator end() // <20><><EFBFBD><EFBFBD>ͷ<EFBFBD>ڵ<EFBFBD>
|
|||
|
{
|
|||
|
return iterator(_head);
|
|||
|
}
|
|||
|
|
|||
|
const_iterator begin() const
|
|||
|
{
|
|||
|
return const_iterator(_head->_next);
|
|||
|
}
|
|||
|
|
|||
|
const_iterator end() const
|
|||
|
{
|
|||
|
return const_iterator(_head);
|
|||
|
}
|
|||
|
|
|||
|
reverse_iterator rbegin() // <20><><EFBFBD><EFBFBD>ͷ<EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>
|
|||
|
{
|
|||
|
return reverse_iterator(_head->_prev);
|
|||
|
}
|
|||
|
|
|||
|
reverse_iterator rend() // <20><><EFBFBD><EFBFBD>ͷ<EFBFBD>ڵ<EFBFBD>
|
|||
|
{
|
|||
|
return reverse_iterator(_head);
|
|||
|
}
|
|||
|
|
|||
|
const_reverse_iterator rbegin() const
|
|||
|
{
|
|||
|
return const_reverse_iterator(_head->_prev);
|
|||
|
}
|
|||
|
|
|||
|
const_reverse_iterator rend() const
|
|||
|
{
|
|||
|
return const_reverse_iterator(_head);
|
|||
|
}
|
|||
|
|
|||
|
public:
|
|||
|
// <20><>ͷ˫<CDB7><CBAB>ѭ<EFBFBD><D1AD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// Ĭ<>Ϲ<EFBFBD><CFB9><EFBFBD>
|
|||
|
List()
|
|||
|
{
|
|||
|
_head = new Node;
|
|||
|
_head->_next = _head;
|
|||
|
_head->_prev = _head;
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
List(const List<T>& lt)
|
|||
|
{
|
|||
|
_head = new Node;
|
|||
|
_head->_next = _head;
|
|||
|
_head->_prev = _head;
|
|||
|
|
|||
|
for (const auto& e : lt)
|
|||
|
{
|
|||
|
push_back(e);
|
|||
|
}
|
|||
|
}
|
|||
|
|
|||
|
// <20><>ֵ<EFBFBD><D6B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
//List<T>& operator=(const List<T>& lt)
|
|||
|
//{
|
|||
|
// if (this != <)
|
|||
|
// {
|
|||
|
// clear();
|
|||
|
// for (const auto& e : lt)
|
|||
|
// {
|
|||
|
// push_back(e);
|
|||
|
// }
|
|||
|
// }
|
|||
|
// return *this;
|
|||
|
//}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD>д<EFBFBD><D0B4>
|
|||
|
List<T>& operator=(List<T> lt)
|
|||
|
{
|
|||
|
std::swap(_head, lt._head);
|
|||
|
return *this;
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD>
|
|||
|
void clear()
|
|||
|
{
|
|||
|
iterator it = begin();
|
|||
|
while (it != end())
|
|||
|
{
|
|||
|
erase(it++);
|
|||
|
}
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
~List()
|
|||
|
{
|
|||
|
clear();
|
|||
|
delete _head;
|
|||
|
_head = nullptr;
|
|||
|
}
|
|||
|
|
|||
|
// <20>ṹ<EFBFBD><E1B9B9><EFBFBD>Ƶ<EFBFBD><C6B5><EFBFBD><EFBFBD><EFBFBD>, <20><>û<EFBFBD><C3BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><DFBC><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD>
|
|||
|
//void push_back(const T& data)
|
|||
|
//{
|
|||
|
// Node* tail = _head->_prev;
|
|||
|
// Node* newnode = new Node(data);
|
|||
|
// tail->_next = newnode;
|
|||
|
// newnode->_prev = tail;
|
|||
|
// newnode->_next = _head;
|
|||
|
// _head->_prev = newnode;
|
|||
|
//}
|
|||
|
|
|||
|
//void push_front(const T& data)
|
|||
|
//{
|
|||
|
// Node* cur = _head->_next;
|
|||
|
// Node* newnode = new Node(data);
|
|||
|
|
|||
|
// _head->_next = newnode;
|
|||
|
// newnode->_prev = _head;
|
|||
|
// newnode->_next = cur;
|
|||
|
// cur->_prev = newnode;
|
|||
|
//}
|
|||
|
|
|||
|
void push_back(const T& data)
|
|||
|
{
|
|||
|
insert(end(), data);
|
|||
|
}
|
|||
|
|
|||
|
void push_front(const T& data)
|
|||
|
{
|
|||
|
insert(begin(), data);
|
|||
|
}
|
|||
|
|
|||
|
//void pop_back()
|
|||
|
//{
|
|||
|
// Node* tail = _head->_prev;
|
|||
|
// Node* prev = tail->_prev;
|
|||
|
|
|||
|
// delete tail;
|
|||
|
// prev->_next = _head;
|
|||
|
// _head->_prev = prev;
|
|||
|
//}
|
|||
|
|
|||
|
//void pop_front()
|
|||
|
//{
|
|||
|
// Node* head = _head->_next;
|
|||
|
// Node* next = head->_next;
|
|||
|
|
|||
|
// delete head;
|
|||
|
// _head->_next = next;
|
|||
|
// next->_prev = _head;
|
|||
|
//}
|
|||
|
|
|||
|
void pop_back()
|
|||
|
{
|
|||
|
erase(--end());
|
|||
|
}
|
|||
|
|
|||
|
void pop_front()
|
|||
|
{
|
|||
|
erase(begin());
|
|||
|
}
|
|||
|
|
|||
|
void insert(iterator pos, const T& data)
|
|||
|
{
|
|||
|
Node* cur = pos._node;
|
|||
|
Node* prev = cur->_prev;
|
|||
|
Node* newnode = new Node(data);
|
|||
|
|
|||
|
// prev newnode cur
|
|||
|
prev->_next = newnode;
|
|||
|
newnode->_prev = prev;
|
|||
|
newnode->_next = cur;
|
|||
|
cur->_prev = newnode;
|
|||
|
}
|
|||
|
|
|||
|
iterator erase(iterator pos)
|
|||
|
{
|
|||
|
assert(pos != end());
|
|||
|
|
|||
|
Node* cur = pos._node;
|
|||
|
Node* prev = cur->_prev;
|
|||
|
Node* next = cur->_next;
|
|||
|
delete cur;
|
|||
|
|
|||
|
prev->_next = next;
|
|||
|
next->_prev = prev;
|
|||
|
|
|||
|
return next;
|
|||
|
}
|
|||
|
|
|||
|
private:
|
|||
|
Node* _head;
|
|||
|
};
|
|||
|
}
|