list底层实现细节
一、部分代码展示
#pragma once
#include<cassert>
namespace bit
{
template<class T>
struct ListNode
{
ListNode<T>* _prev;
ListNode<T>* _next;
T _data;
ListNode(const T& val = T())
:_prev(nullptr)
, _next(nullptr)
, _data(val)
{
}
};
// 迭代器
// 添加Ref Ptr是为了const迭代器能复用配普通迭代器代码
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;
}
// ++it
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;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
// const迭代器
//template<class T>
//struct ListConstIterator
//{
//typedef ListNode<T> Node;
//typedef ListConstIterator<T> Self;
//Node* _node;
//ListConstIterator(Node* node)
//:_node(node)
//{}
//// *it
//const T& operator*()
//{
//return _node->_data;
//}
//// it->
//const T* operator->()
//{
//return &_node->_data;
//}
//// ++it
//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;
//}
//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;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
public:
void emptyinit()
{
_size = 0;
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
emptyinit();
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
list(const list<T>& l)
{
emptyinit();
for (auto& e : l)
{
push_back(e);
}
}
void swap(list<T>& l)
{
std::swap(_head, l._head);
std::swap(_size, l._size);
}
list<T>& operator=(list<T> l)
{
swap(l);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
// 匿名构造
return iterator(_head);
}
// const iterator代表迭代器不能被修改，无法++ -- T* const p1
// 后面加const代表迭代器指向的内容不能修改 const T* p2
const_iterator begin() const
{
return iterator(_head->_next);
}
const_iterator end() const
{
// 匿名构造
return iterator(_head);
}
void insert(iterator pos, const T& val)
{
Node* newnode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
prev->_next = newnode;
_size++;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return iterator(next);
}
void push_front(const T& val)
{
insert(begin(), val);
}
void push_back(const T& val)
{
insert(end(), val);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
size_t size() const
{
return _size;
}
bool empty()
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
}二、细节
1、成员变量
实现的是带头双向循环的链表，所以节点的定义是有前后指针和数据的。链表里面包含了头节点。
2、迭代器
链表的迭代器是非常重要的，因为与 string 和 vector 不同的是链表的存储空间是不连续的，所以迭代器不再是指针，而是一个节点。需要单独写一个迭代器的类。
我们对于迭代器的成员函数其实很熟悉，无非是重载 ++ -- * == !=
所以重点是如何实现普通迭代器和 const 迭代器。
const 迭代器是指向的内容不能改变，即成员函数的返回值是 const，那就一定要写两个类吗？
其实不用，类模板就可以定义两个不同的返回值
template<class T, class Ref, class Ptr>Ref 是引用，即返回迭代器指向数据的引用。
Ptr 是指针，即返回迭代器指向数据的指针。
这样 const 迭代器就可以复用普通迭代器的代码。
而且迭代器的类不能写析构，迭代器只是用来遍历的，不是用来操作数据的
三、list 迭代器失效问题
1、插入
插入不会迭代器失效，因为地址依然存在，没有对迭代器和迭代器的内容改变。
2、删除
删除依然会失效，因为迭代器指向的数据和空间都没了，解决办法就是返回一个新的迭代器，是删除节点的下一个节点的迭代器。
原文地址：https://blog.csdn.net/qhy850716/article/details/145288934
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！