目录
学习完vector，让我们接着来学习有关链表的相关知识
list的接口与前两个容器差不多，有了前面的铺垫，学习list也就能事半功倍。
一常用接口
1头插尾插
void push_front (const value_type& val) 在list的头部插入一个新节点 void push_back (const value_type& val) 在list的尾部插入一个新节点
在前面学习数据结构中，如果你有在链表部分用c语言来模拟实现链表的常见接口，这两个你一定不陌生：实现起来细节多，一个不注意程序直接就崩溃了，非常的恶心！
2头删尾删
void pop_front() 删除list头部的一个节点
void pop_back() 删除list尾部的一个节点
3任意位置插入与删除
iterator insert (iterator position, const value_type& val) 在pos前插入一个新节点
iterator erase (iterator position) 删除pos位置的节点
注意：这里的pos的类型是传入的是迭代器
二链表的模拟实现
1构造
实现链表的方式我们用双链表带头节点来实现；所以在构造只需要创建出一个头节点来让他自己指向自己就可以了
而在写构造函数之前，我们要写一个函数来对链表的初始化：这里我们选择用结构体来实现：这样我们才能让list内部的成员都能访问到;为了能兼容多类型，实现时把它写成一个模板
template <class T>
struct ListNode
{
typedef ListNode<T> Node;
Node* _prev;
Node* _next;
T _date;
//初始化
ListNode(const T& x = T())
:_prev(nullptr)
, _next(nullptr)
, _date(x)
{}
};void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}2尾插
链表的next与prev的连接更新
void push_back(const T& val)
{
Node* NewNode = new Node(val);
//_head tail NewNode
Node* tail = _head->_prev;
tail->_next = NewNode;
NewNode->_prev = tail;
NewNode->_next = _head;
_head->_prev = NewNode;
}3迭代器
当我们实现出来了尾插，我们想打印一下看看效果是否是我们所料想的那样；这就要用到迭代器来帮助我们来实现。但是链表的打印可不像vector，它的物理空间是不连续的，导致我们遍历是it++后的下一个空间不一定就是我们链表的下一个节点。怎么办呢？？
面对这这种情况我们选择来自己封装一个迭代器把它所要用到的操作符自己实现出来：自己来解决问题！！
template <class T>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T> Slef;
//it指向的节点
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
//++i
Slef& operator++()
{
_node = _node->_next;
return *this;
}
//i++
Slef operator++(int)
{
//浅拷贝
Slef tmp(*this);
_node = _node->_next;
return tmp;
}
//--i
Slef& operator--()
{
_node = _node->_prev;
return *this;
}
//i--
Slef operator--(int)
{
Slef tmp(*this);
_node = _node->_prev;
return tmp;
}
//*i
T& operator*()
{
return _node->_date;
}
bool operator!=(const Slef& node)
{
return _node != node._node;
}
};这样我们就能用迭代器来进行打印工作了
4list类型时自定义类型成员的访问
我们要访问自定义类型成员访问方式有两种：
struct A
{
int _a1;
int _a2;
A(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{}
};
A* ptr = &aa1;
第1种 (*ptr)._a1;
第2种 ptr->_a1;
int main()
{
list<A> lt;
A aa1(1, 1);
A aa2 = { 1, 1 };
lt.push_back(aa1);
lt.push_back(aa2);
lt.push_back(A(2, 2));
lt.push_back({ 3, 3 });
lt.push_back({ 4, 4 });
}将A进行初始化后尾插进类型为A的list；最后我们想用迭代器来访问每个节点的A的成员的值并打印出来，怎么办？
第一种：节点的解引用(前面实现了重载)后.找出每个成员：(*it)._a1 (*it)._a2
第二种：按照上面用->的方式：让迭代器it去模仿T*的行为，进行A中成员的访问；这就要我们自己来实现重载->函数从而来实现它：
T* operator->()
{
return &_node->_date;
}注意：不是去取node节点的地址！！
而在实现迭代器的打印中编译器为了简便，把重载的->给删去了，值留下一个->
list<A>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->_a1 << ":" << it->_a2 << endl;
//cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;
++it;
}
cout << endl;
5在pos位置前插入删除
有了上面迭代器的实现也就间接解决pos要传迭代器的问题了
void insert(iterator pos, const T& val)
{
Node* NewNode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;
// prev NewNode cur
prev->_next = NewNode;
NewNode->_prev = prev;
NewNode->_next = cur;
cur->_prev = NewNode;
}在实现erase的时候，要注意返回新的pos的位置，解决迭代器失效的问题
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
//prev pos next
prev->_next = next;
next->_prev = prev;
delete cur;
//防止迭代器失效
return iterator(next);
}其它接口的实现在下面的源代码中，实现起来很简单这里就不展开讲了！
三完善迭代器
1问题
在我们实现迭代器中，通常会有两个版本：const与非const来让我们在不同场景中实现所要的需求；而在这里，我们要如何来进行实现它呢？？
2方法
首先我们要明白：const与非const的差异在与迭代器it所指向的内容能不能修改的问题->
在封装迭代器的使用中对操作符重载->与*的实现进行修改：const版本中加上const，非const不用加来实现
如果是这样，就得在写一个与迭代器相同的类中来更改对应的位置，其它位置保持不变；虽然可以来解决问题，但这会让我们的代码看上去冗余。有什么别的方法呢？？
我们可以来通过向类模板中传参来实现：(这有时类模板语法的优势)
只用写一份迭代器，让编译器来自己推演生成我们说要的迭代器的版本：
template <class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Slef;
//it指向的节点
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
//T* operator->()
Ptr operator->()
{
return &_node->_date;
}
//T& operator->()
Ref operator*()
{
return _node->_date;
}
...
}
template <class T>
class list
{
public:
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
|
V
//typedef ListIterator<T> iterator;
//typedef ListConstIterator<T> const_iterator;
...
}
四list与vector的对比
源代码
#pragma once
#include<assert.h>
namespace bit
{
//创建节点的初始化
template <class T>
struct ListNode
{
typedef ListNode<T> Node;
Node* _prev;
Node* _next;
T _date;
//初始化
ListNode(const T& x = T())
:_prev(nullptr)
, _next(nullptr)
, _date(x)
{}
};
//本质是两个类的使用：
// Ref->T& Ptr->T*
//封装迭代器
template <class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Slef;
//it指向的节点
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
//it->
//it模拟:
//T* operator->()
Ptr operator->()
{
return &_node->_date;
}
//*i 支持更改要传引用
//T& operator*()
Ref operator*()
{
return _node->_date;
}
//++i
Slef& operator++()
{
_node = _node->_next;
return *this;
}
//i++
Slef operator++(int)
{
//浅拷贝
Slef tmp(*this);
_node = _node->_next;
return tmp;
}
//--i
Slef& operator--()
{
_node = _node->_prev;
return *this;
}
//i--
Slef operator--(int)
{
Slef tmp(*this);
_node = _node->_prev;
return tmp;
}
//!=
bool operator!=(const Slef& node)
{
return _node != node._node;
}
};
template <class T>
class list
{
public:
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
//typedef ListIterator<T> iterator;
//typedef ListConstIterator<T> const_iterator;
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
//it2(it1)
list(const list<T>& it)
{
empty_init();
//string等类型会浅拷贝，传引用
for (auto& ch : it)
{
push_back(ch);
}
}
//it2=it1
//传值传参不改变实参
list<T>& operator=(const list<T> it)
{
/*for (auto& ch : x)
{
push_back(ch);
}*/
swap(it);
return *this;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
void clear()
{
iterator it = begin();
while (it != end())
{
//delete it._node;
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
iterator begin()
{
//构造
//return iterator(_head->_next);
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& val)
{
//Node* NewNode = new Node(val);
_head tail NewNode
//Node* tail = _head->_prev;
//tail->_next = NewNode;
//NewNode->_prev = tail;
//NewNode->_next = _head;
//_head->_prev = NewNode;
insert(end(), val);
}
void push_fron(const T& val)
{
insert(begin(), val);
}
void pop_back()
{
erase(--end());
}
void pop_fron()
{
erase(begin());
}
size_t size()
{
return _size;
}
void insert(iterator pos, const T& val)
{
Node* NewNode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;
// prev NewNode cur
prev->_next = NewNode;
NewNode->_prev = prev;
NewNode->_next = cur;
cur->_prev = NewNode;
_size++;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
//prev pos next
prev->_next = next;
next->_prev = prev;
delete cur;
//迭代器失效
return iterator(next);
_size--;
}
private:
Node* _head;
size_t _size;
};
}以上便是我在list学习到的相关知识点，有错误欢迎在评论区里指出☞
感谢您的观看，我们在下一篇文章中再见！