文章目录
链表的知识回顾
链表是有一个个节点链接起来的.每一个节点里面存有数据val,下一个节点的地址next,双向循环链表还会有上一个节点的地址.
双向带头循环链表比双向循环链表多了一个头节点.又称哨兵位.在很多时候,多一个头节点能帮我们解决很多事.
下面模拟实现的就是双向带头循环链表,跟c++容器库list里面一样
前期工作
写一个自己的命名空间,防止跟库里面函数冲突.我们后面所写的函数都在中国命名空间里面.
namespace shh
{
}
构造节点
因为节点里面要存储很多值,所以我们写一个类把它封装起来.
同时,因为节点里面存储的数据val类型不清楚,写一个模板,让编译器自己根据类型去生成.
//把节点封装成一个类
template<class T>
struct ListNode
{
ListNode<T>* prev = nullptr;
ListNode<T>* next = nullptr;
T val = T();
ListNode(const T& tmp = T())
:prev(nullptr)
, next(nullptr)
, val(tmp)
{
}
};
这里写一个构造,为我们后面可以直接用值tmp去生成节点,不用自己写.
迭代器
vector和string里面的迭代器都是原生指针,因为他们存储的物理空间连续.
例如: iterator(int) ,iterator++ 会跳到下一个数字.iterator可以访问数据.
但是链表没有办法做到这一点.所以,我们将链表节点的指针封装成一个类,然后用上运算符重载,自己控制运算符,就能实现vector中T*的功能.
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef ListNode<T> Node;
typedef list_iterator<T,Ref,Ptr> iterator;
//节点指针
Node* _node;
};
这个类里面封装的是节点的指针,所以它唯一的成员变量就是Node.*
注意
这里的模板有三个参数,为什么呢?
首先T是节点数据的类型,这个没问题.
但是其他两个呢?
Ref是引用,Ptr是指针.这样子写是为了能生成多种引用T&,和T.*
当我们需要修改这个数据是我们直接传T&.如果我们不允许别人修改数据时,传const T&,让别人只能读.不能修改.
其实还有另一种解决方法,copy这个类,把这个类改成const版本的.但是这样会造成代码冗余.
构造迭代器
//
list_iterator(Node* node)
:_node(node)
{
}
写了这个,我们就可以传一个节点的指针来构造迭代器
解引用*迭代器
Ref operator*()
{
return _node->val;
}
Ref是T& / const T&
我们这里要模拟的是vector中T*的功能,解引用取得数据,所以返回节点中的数据
迭代器->
Ptr operator->()
{
return &_node->val;
}
Ptr是T / const T
我们这里要模拟的是指针中->的功能,所以要传数据T的地址.
在调用上,我们假设有一个类A,里面有两个值a1和a2,我们用这个类来充当节点中的数据val
it->是调用it.operator->(),返回的是一个T.
it.operator->() ->a1 才能取到a1
为了美观,编译器会帮我们减少一个箭头 变成 it->_a1
struct A
{
int _a1, _a2;
A(int a1 = 0, int a2 = 0)
:_a1(a1),
_a2(a2)
{}
};
void TestList2()
{
list<A> lt;
A a = { 3,3 };
lt.push_back(a);
lt.push_back(A{2,2});
lt.push_back({1,1});
list<A>::iterator it = lt.begin();
while (it != lt.end())
{
/*cout << *it << " ";*/
cout << it->_a1 << " "<< it->_a2;
cout << endl;
//it.operator->() ->a1
//val* --> T*
it++;
}
cout << endl;
}
迭代器++
//前置++ ++i;
iterator& operator++()
{
_node = _node->next;
return *this;
}
//后置++ i++;
iterator operator++(int)
{
iterator tmp(_node);
_node = _node->next;
return tmp;
}
迭代器- -
//--i
iterator& operator--()
{
_node = _node->prev;
return *this;
}
//i--
iterator operator--(int)
{
iterator tmp(_node);
_node = _node->prev;
return tmp;
}
判断两个迭代器是否相等
bool operator==(const iterator& it)
{
return _node == it._node;
}
bool operator!=(const iterator& it)
{
return _node != it._node;
}
链表
template<class T>
class list
{
public:
//调用可读可写的迭代器
typedef list_iterator<T,T&,T*> iterator;
//调用只能读,不能修改的迭代器
typedef list_iterator<T, const T&,const T*> const_iterator;
typedef ListNode<T> Node;
private:
Node* _head;
size_t _size;
};
链表里面有两个成员变量,一个作为头节点,一个计算节点的个数
empty_init
这个函数的功能和构造函数一样,写出来是为了后面进行复用.
void empty_init()
{
_head = new Node;
_head->next = _head;
_head->prev = _head;
_size = 0;
}
构造
复用empty_init
list()
{
empty_init();
}
拷贝构造
list T2(T1)
初始化T2,然后把T1的值都塞到后面
list(const list<T>& T1)
{
empty_init();
for (auto& e : T1)
{
push_back(e);
}
}
swap
T2.swap(T1)
交换两个链表
void swap(const list<T>& T1)
{
std::swap(_head, T1._haed);
std::swap(_size, T1._size);
}
operator=
这里运用了一个很巧妙的写法,把传过来的值拷贝构造list T1,然后将T1和*this交换
直接白嫖编译器的成果(拷贝构造),纯纯资本家
const list<T>& operator=(list<T> T1)
{
swap(T1);
return *this;
}
begin和end
begin返回头节点的下一个,end返回头节点.因为容器底层实现,遍历等都是左闭右开[ )
const_iterator begin() const
{
return _head->next;
}
const_iterator end() const
{
return _head;
}
iterator begin()
{
return _head->next;
}
iterator end()
{
return _head;
}
insert
注意:在链表中,我们的节点都需要自己new出来,因为链表不是一个连续的空间,没有办法直接开好.要一个个自己搞
pos里面存储的节点指针才是我们需要的
// prev tmp next
void insert(iterator pos, const T& val)
{
//new一个用数据val开辟出来的节点
Node* tmp = new Node(val);
Node* prev = pos._node->prev;
Node* next = pos._node;
prev->next = tmp;
tmp->prev = prev;
tmp->next = next;
next->prev = tmp;
_size++;
}
push_back
复用insert尾插
void push_back(const T& val)
{
insert(end(), val);
}
push_front
复用insert头插
void push_front(const T& val)
{
insert(begin(), val);
}
erase
注意:delete要删除自定义类型要调用析构函数,我们这里要删除的是节点(指针),而不是迭代器
不能delete pos,迭代器只有访问节点的功能,不能管理节点
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = pos._node->prev;
Node* next = pos._node->next;
prev->next = next;
next->prev = prev;
//
delete cur;
_size--;
return next;
}
pop_back
复用erase,注意要删除的不是头节点,而是头节点的前一个,也就是存储有效数据的最后一个
所以–end(),改好使用我们之前写的迭代器–.
void pop_back()
{
erase(--end());
}
pop_front
void pop_front()
{
erase(begin());
}
size
size_t size()
{
return _size;
}
empty
bool empty()
{
return _size == 0;
}
clear
删除掉除头节点之外的其他节点
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
析构
在clear的前提下删除头节点
~list()
{
clear();
delete _head;
_head = nullptr;
}