模拟实现list的类的基本功能(增删等操作)要建立在迭代器类和节点类均已实现好的情况下才得以完成。
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
迭代器有两种实现方式,具体应根据容器底层数据结构实现:
1. 原生态指针,比如:vector
2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法:
template<class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T,Ref,Ptr> Self;
//内置类型 指针
Node* _node;
}
ListIterator(Node* node)
:_node(node)
{}
迭代器指向所传节点
//*it 解引用
//T& operator*()
Ref operator*()
{
return _node->_data;
}
//it->
//T* operator->()
Ptr operator->()
{
return &_node->_data;
}
//前置++
Self& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp; // tmp 是一个局部变量,它在函数返回后将不再存在,所以不能返回引用
}
//前置--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;// tmp 是一个局部变量,它在函数返回后将不再存在,所以不能返回引用
}
注:
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
template<class T>
class list
{
typedef ListNode<T> Node;
public :
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T,const T&,const T*> const_iterator;
private:
Node* _head;
size_t _size;
}
const_iterator
只能读取它所指向的元素,不能修改。//带头双向循环链表的构造函数
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
iterator begin()
{
return _head->_next;//也可以直接这么写,进行隐式类型转换(单参数的构造函数支持隐式类型转换)
}
iterator end()
{
return iterator(_head);//匿名对象,局部变量 不能返回引用
}
//const迭代器需要的是迭代器指向的内容不能修改
//const iterator 是迭代器本身不能修改
const_iterator begin() const
{
return _head->_next;
}
const_iterator end()const
{
return const_iterator(_head);
}
//lt2(lt)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
iterator erase(iterator pos)
{
//prev cur next
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
_size--;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);//匿名对象,局部变量 不能返回引用
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
//不清除头节点
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
_size++;
//prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
template<class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T,Ref,Ptr> Self;
//内置类型 指针
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
//*it 解引用
//T& operator*()
Ref operator*()
{
return _node->_data;
}
//it->
//T* operator->()
Ptr operator->()
{
return &_node->_data;
}
//前置++
Self& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp; // tmp 是一个局部变量,它在函数返回后将不再存在,所以不能返回引用
}
//前置--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;// tmp 是一个局部变量,它在函数返回后将不再存在,所以不能返回引用
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
public :
//typedef ListIterator<T> iterator;
//typedef ListConstIterator<T> const_iterator;//重新写一个ListConstIterator类(这个方法比较冗余)
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T,const T&,const T*> const_iterator;//写成模板,让编译器生成两个类,而不是我们自己写
/*iterator begin()
{
return iterator(_head->_next);
}*/
iterator begin()
{
return _head->_next;//也可以直接这么写,进行隐式类型转换(单参数的构造函数支持隐式类型转换)
}
iterator end()
{
return iterator(_head);//匿名对象,局部变量 不能返回引用
}
//const迭代器需要的是迭代器指向的内容不能修改
//const iterator 是迭代器本身不能修改
const_iterator begin() const
{
return _head->_next;
}
const_iterator end()const
{
return const_iterator(_head);
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
//this->empty_init();
empty_init();
}
//lt2(lt)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//需要析构,一般就需要自己写深拷贝
void swap(list<T>& lt)
{
//lt是局部变量
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//lt1 = lt3
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
//不清除头节点
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
/*void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}*/
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
_size++;
//prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
_size--;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);//匿名对象,局部变量 不能返回引用
}
size_t size()const
{
return _size;
}
bool empty()
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
____________________
⭐感谢你的阅读,希望本文能够对你有所帮助。如果你喜欢我的内容,记得点赞关注收藏我的博客,我会继续分享更多的内容。⭐