bosthhe1
commented
1 year ago namespace hxh{
template<class T>
struct listNode
{
listNode<T> *next;
listNode<T> *prev;
T data;
listNode(const T& data)
:next(nullptr)
, prev(nullptr)
, data(data)
{}
};
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef listNode<T> _Node;
typedef __list_iterator<T, Ref, Ptr> Self;
_Node* _node;
__list_iterator(_Node* x)
:_node(x)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return _node->data;
}
bool operator!=(const Self& val)const
{
return _node != val._node;//思考这里为什么用 ‘ .’ ，而不是箭头
}
Self& operator++()
{
_node = _node->next;
return *this;
}
Self operator++(int)
{
Self tmp = (*this);
_node = _node->next;
return tmp;
}
Self& operator--()
{
_node = _node->prev;
return *this;
}
Self operator--(int)
{
Self tmp = (*this);
_node = _node->prev;
return tmp;
}
};
//反向迭代器这里为后期补充，只封装了一些简单的函数调用
template<class Iterator,class Ref, class Ptr>//反向迭代器在这里就是适配器，这里的Ref和Ptr是为了取到正向迭代器的数据
struct reverse__list_iterator
{
typedef reverse__list_iterator<Iterator,Ref,Ptr> Self;
Iterator node;
reverse__list_iterator(Iterator _node)
:node(_node)
{}
Ref operator*()//取正向迭代器数据
{
Iterator tmp = node;
return *--tmp;
}
Ptr operator->()//取正向迭代器数据的地址
{
return &operator*();
}
Self operator++()
{
--node;
return *this;
}
Self operator--()
{
++node;
return *this;
}
bool operator!=(const Self& v)
{
return node != v.node;
}
};
template<class T>
class list
{
public:
typedef listNode<T> _Node;
typedef __list_iterator<T, T&,T*> iterator;
typedef __list_iterator<T, const T&,const T*> const_iterator;
typedef reverse__list_iterator<iterator, T&, T*> reverse_iterator;//反向迭代器是适配器，里面封装了正向迭代器，所以传正向迭代器，如果取数据，需要正向迭代器T的类型，所以会传T&和T*过去
list()
{
_head = new _Node(T());
_head->prev = _head;
_head->next = _head;
}
list(int n, const T& val = T())
{
_head = new _Node(T());
_head->prev = _head;
_head->next = _head;
int i = 0;
while (i < n)
{
push_back(val);
i++;
}
}
//现代写法
template<class Inputiterator>
list(Inputiterator first, Inputiterator last)
{
_head = new _Node(T());
_head->prev = _head;
_head->next = _head;
while (first != last)
{
push_back(first._node->data);
first++;
}
}
list(const list<T>& val)
{
_head = new _Node(T());
_head->prev = _head;
_head->next = _head;
list<T> tmp(val.begin(), val.end());
swap(tmp._head, _head);
}
//传统写法
/*list(const list<T>& val)
{
_head = new _Node(T());
_head->prev = _head;
_head->next = _head;
const_iterator it = val.begin();
while (it != val.end())
{
push_back(it._node->data);
it++;
}
}*/
list<T>& operator=(list<T> val)
{
swap(_head,val._head);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
++it;
this->pop_head();
}
}
void push_back(const T& val)
{
hxh::list<int>::iterator pos = end();
insert(pos,val);
}
void push_front(const T& val)
{
hxh::list<int>::iterator pos = begin();
insert(pos, val);
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
iterator end()
{
return iterator(_head);//注意这里不是强转，这里是构造
}
iterator begin()
{
return iterator(_head->next);
}
const_iterator end()const
{
return const_iterator(_head);
}
const_iterator begin()const
{
return const_iterator(_head->next);
}
void insert(iterator pos, const T& val)
{
_Node* cur = pos._node;
_Node* prev = cur->prev;
_Node* newNode = new _Node(val);
newNode->next = cur;
newNode->prev = prev;
prev->next = newNode;
cur->prev = newNode;
}
void erase(iterator pos)
{
assert(pos != end());
_Node* cur = pos._node;
_Node* prev = cur->prev;
_Node* next = cur->next;
prev->next = next;
next->prev = prev;
delete cur;
}
void pop_head()
{
assert(begin() != _head);
erase(begin());
}
private:
_Node* _head;
};
}
对于迭代器，我们在list之前接触到的迭代器，都是一些原生指针类型的，原生指针类型是天然的迭代器，所以对于前面的迭代器，说和指针一样也不为过，但是对于list来说，由于地址空间的不连续，所以对于list需要重载运算符，才可以使用，从list以后，迭代器就是模仿指针的东西，而并非指针。 我们需要注意的是类型的力量，我从c++入门1个月，在list才算体会到了类型的力量，我们看到我们将迭代器封装成一个迭代器的类，我们对迭代器的加加减减都在这个类里面实现，为了方便我们迭代器的使用，我们将迭代器的类用struct来写(因为struct默认是共有)，这里的迭代器本质就是一个结构体了，迭代器里面放的节点的指针。