list的模拟实现
目录
1.结构
list底层是一个带头双向循环链表
2.用3个类实现list
1.链表中的单个节点
2.迭代器
3.list
由于链表中的迭代器已经不是原生指针，所以将迭代器单独封装成一个类。
list的迭代器是双向迭代器，不能够像string和vector那样的随机迭代器那样可以+3 -3，只能够++和--
3.单个节点的定义
template<class T>
class listnode
{
public:
T _data;
listnode<T>* _prev;
listnode<T>* _next;
listnode(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};4.迭代器的定义
//Ref是T的引用但不知道是不是const迭代器,所以写成模版的形式
//Ptr是T的指针但不知道是不是const迭代器,所以写成模版的形式
//这样就不用单独写一个const迭代器了
template<class T, class Ref, class Ptr>
class list_iterator
{
public:
typedef listnode<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
//这里的构造函数是为了一会方便提供list类里的begin和end的接口
//begin和end接口写在list类里是因为：在List类里才有真正的链表结构
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};5.list类的实现
template<class T>
class List
{
typedef listnode<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
//构造哨兵位头结点
List()
{
_head = new Node;
_head->prev = _head;
_head->next = _head;
_size = 0;
}
iterator begin()
{
//隐式类型转换，利用迭代器类里的构造函数
return _head->next;
}
iterator end()
{
//隐式类型转换
return _head;
}
const_iterator begin() const
{
//隐式类型转换
return _head->next;
}
const_iterator end() const
{
//隐式类型转换
return _head;
}
void push_back(const T& x)
{
/*Node* newnode = new Node(x);
Node* prev = _head->_prev;
Node* cur = _head;
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;*/
insert(end(), x);
}
void insert(iterator pos, const T& x)
{
Node* prev = pos->_prev;
Node* cur = pos;
Node* newnode = new Node(x);
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;
_size++;
}
//返回被删除元素的下一个元素的迭代器，防止迭代器失效
iterator erase(iterator pos)
{
Node* prev = pos->_prev;
Node* next = pos->_next;
prev->_next = next;
next->_prev = prev;
delete pos;
_size--;
return next;
}
//拷贝构造
List(const List<T>& s1)
{
_head = new Node;
_head->prev = _head;
_head->next = _head;
_size = 0;
for (auto s : s1)
{
push_back(s);
}
}
void swap(List<T> sl)
{
std::swap(_head, sl._head);
std::swap(_size, sl._size);
}
List<T>& operator=(List<T> s1)
{
swap(s1);
return *this;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~List()
{
clear();
delete _head;
_head = nullptr;
}
int size() const
{
return _size;
}
bool empty() const
{
return _size == 0;
}
private:
Node* _head;
int _size;
};6.vector与list的区别
vector中没有支持头插和头删的接口，但是可以调用insert接口间接头插头删
list中有支持头插头删的接口
原文地址：https://blog.csdn.net/GGbond665/article/details/142676458
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！