list模仿实现
目录前言
具体实现
节点
迭代器
list迭代器的基本内容
成员变量和typedef
构造函数
对 ++ 和 -- 运算符的重写
对 运算符* 和 运算符->的重写
对运算符== 和 运算符！=的重写
迭代器完整代码
List的具体实现
基本成员和typedef
构造函数
front 和 back
insert和erase
push_back和push_front
pop_back和push_back
empty和size
begin和end
clear和swap
析构函数
总结
前言
list底层是一个带头双向循环链表。list的重点是对其节点的封装(即迭代器的封装)。盼望可以通过对list的模仿实现使各位更明白封装的意义。
具体实现
节点
节点内容很常规，一个_val存储数据，一个prev指针指向节点的前一个数据，一个next指针指向节点的后一个数据。(画图较丑，大致就是这样的图)
https://i-blog.csdnimg.cn/direct/0ed7fc19e7094975b1b4e936850bc5df.png
节点代码
template<class T>
struct ListNode
{
T _val = T();
ListNode<T>* prev = nullptr;
ListNode<T>* next = nullptr;
ListNode(const T& x)
: _val(x)
, prev(nullptr)
, next(nullptr)
{}
}; 迭代器
list迭代器的基本内容
list的迭代器实质上是对 节点 即 Node 的封装，使得迭代器能实现 ++ 和 -- 等一系列迭代器所需的基本运算操作(由于list的存储空间不连续，所以Node无法直接举行迭代器所需的基本运算，因此对其举行封装)。 值得一提的是list的迭代器不是随机迭代器，不支持 + 和 - ，其主要原因是由于 + 和 - 的操作太过斲丧性能了。
成员变量和typedef
由于是对 节点Node的封装，因此成员变量只有 _node。
typedef ListIterator<T, Ref, Ptr> Self;
typedef ListNode<T> Node;
public:
Node* _node = nullptr; 构造函数
ListIterator() = default;
ListIterator(Node* x)
{
_node = x;
} 对 ++ 和 -- 运算符的重写
Self operator++(int) 是对后置++的重写， Self& operator++() 是对前置++的重写。
Self& operator++()
{
_node = _node->next;
return *this;
}
Self operator++(int)
{
Self ret(_node);
_node = _node->next;
return ret;
}
Self& operator--()
{
_node = _node->prev;
return *this;
}
Self operator--(int)
{
Self ret(_node);
_node = _node->prev;
return ret;
} 对 运算符* 和 运算符->的重写
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &*this->_node;
} 对运算符== 和 运算符！=的重写
bool operator==(const Self& x)
{
return _node == x._node;
}
bool operator!=(const Self& x)
{
return _node != x._node;
} 迭代器完整代码
template<class T , class Ref , class Ptr> struct ListIterator { typedef ListIterator<T, Ref, Ptr> Self;
typedef ListNode<T> Node;
public:
Node* _node = nullptr; public: ListIterator() = default;
ListIterator(Node* x)
{
_node = x;
} Self& operator++() { _node = _node->next; return *this; } Self operator++(int) { Self ret(_node); _node = _node->next; return ret; } Self& operator--() { _node = _node->prev; return *this; } Self operator--(int) { Self ret(_node); _node = _node->prev; return ret; } Ref operator*() { return _node->_val; } Ptr operator->() { return &*this->_node; } bool operator==(const Self& x)
{
return _node == x._node;
}
bool operator!=(const Self& x)
{
return _node != x._node;
} }; List的具体实现
基本成员和typedef
typedef ListNode<T> Node;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
private:
Node* _head = nullptr; 构造函数
list()
{
_head = new Node(T());
_head->next = _head->prev = _head;
}
list(int n , const T& x = T())
{
_head = new Node(T());
_head->next = _head->prev = _head;
while (n--) push_back(x);
}
template<class InputIterator>
list(InputIterator l, InputIterator r)
{
_head = new Node(T());
_head->next = _head->prev = _head;
while (l != r)
{
push_back(*l);
l++;
}
}
list(initializer_list<T> il)
{
_head = new Node(T());
_head->next = _head->prev = _head;
for (const auto& x : il)
{
push_back(x);
}
} front 和 back
T& front()
{
return _head->next->_val;
}
T& back()
{
return _head->prev->_val;
} insert和erase
erase返回删除节点的后一个节点，避免迭代器失效题目。 insert此处也返回迭代器是为了工整，实际上list的insert不会导致迭代器失效
iterator insert(iterator pos, const T& x)
{
Node* dest = new Node(x);
dest->prev = pos._node->prev;
dest->next = pos._node;
pos._node->prev->next = dest;
pos._node->prev = dest;
return dest;
}
iterator erase(iterator pos)
{
Node* dest = pos._node->next;
dest->prev = pos._node->prev;
pos._node->prev->next = dest;
delete pos._node;
return dest;
} push_back和push_front
除下面写法外，也可以思量对insert举行复用
void push_back(const T& x)
{
Node* dest = new Node(x);
dest->prev = _head->prev;
dest->next = _head;
_head->prev->next = dest;
_head->prev = dest;
}
void push_front(const T& x)
{
Node* dest = new Node(x);
dest->prev = _head;
dest->next = _head->next;
_head->next->prev = dest;
_head->next = dest;
} pop_back和push_back
除下面写法外，也可以思量对erase的复用
void pop_front()
{
if (!empty())
{
Node* dest = _head->next;
dest->next->prev = _head;
_head->next = dest->next;
delete dest;
}
}
void pop_back()
{
if (!empty())
{
Node* dest = _head->prev;
_head->prev = dest->prev;
dest->prev->next = _head;
delete dest;
}
} empty和size
bool empty()
{
return _head->next == _head->prev;
}
size_t size() const
{
size_t n = 0;
iterator b = _head->next;
iterator e = _head;
while (b != e)
{
n++;
++b;
}
return n;
} begin和end
const_iterator begin() const
{
return const_iterator(_head->next);
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator begin()
{
return _head->next;
}
iterator end()
{
return _head;
} clear和swap
void clear()
{
iterator b = _head->next;
iterator e = _head;
while (b != e)
{
b = erase(b);
}
}
void swap(list<T>& l)
{
Node* m = l._head;
l._head = _head;
_head = m;
} 析构函数
~list()
{
iterator b = _head->next, e = _head;
while (b != e)
{
b = erase(b);
}
delete _head;
} 总结
难点在于对迭代器的封装，同时不要忽略list类中erase迭代器通过返回值来防止因删除节点而导致的迭代器失效题目
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]