目录
概念:
list的基本结构:
list的迭代器⭐❤:
自定义类型的完善:
const的迭代器:
insert
erase:
size
empty
push_back 、push_front 、pop_back、pop_front
swap 、operator=
析构函数、clear()
概念:
- list是序列容器,允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作,并在两个方向进行迭代。
- list容器使用双链表实现;双链表将每个元素存储在不同的位置,每个节点通过next,prev指针链接成顺序表。
- list与其他标准序列容器(array,vector和deque)相比,list通常可以在容器内的任何位置插入、提取和移动元素。
- list与其他标准序列容器(array,vector和deque)相比,list和forward_list(单链表实现)的主要缺点是他们不能通过位置直接访问元素;例如,要访问列表中的第五个元素,必须从已知位置(开始或结束)迭代到该位置,需要哦线性时间开销。
- 存储密度低,list要使用一些额外的内容空间(next,prev)来保持与每个元素相关联(前后续的线性)的链接信息,从而导致存储小元素类型(如char,short,int等)的列表的存储密度低。
list的基本结构:
#include<iostream>
#include<assert.h>
using namespace std;
namespace bit {template <class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};template<class T>class list {typedef ListNode<T> Node;public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}private:Node* _head;size_t _size;};
}
通过list的概念我们可以得知,list在本质上就是一种带头的双向链表结构,所以在创建list类之前,我们首先要构建一个节点的结构体,其次在list的构造函数中,为了让list遵循它本质上的数据结构,以及通过之后的插入删除等等操作,利用带头双向链表结构的特点,我们将成员变量特地设置为头节点以及长度。
list的迭代器⭐❤:
list的迭代器特殊之处:
- 迭代器的本质就是不管是什么类型的数据都可以进行访问!所以该如何使用迭代器遍历链表内的数据呢?是否能使用前驱、后继指针充当迭代器?答案是不能!
- 如果使用前驱后继指针充当迭代器,那么就需要遇到一个问题,链表的各个节点是不同位置不同地址的!
- 所以如果使用指针+1的方式并不能正确的遍历链表!
- 其次,如果使用前驱后继指针当迭代器,那么解引用能得到节点内的数据吗?不能!因为Node * 解引用后上一个Node 是一个strcut结构体
所以对于list的迭代器,正确的解决方案是另外在设置一个类对迭代器进行分装操作!
template<class T>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> self;Node* _node;ListIterator(Node*node):_node(node){}};
在原先的原身指针 prev和next下,并不能解决迭代器遍历操作,以及解引用操作,因为节点的空间问题并不能使用指针+1的操作,以及解引用prev和next并不能直接获取到节点内部存储的数值元素,所以我们需要在这个封装操作中进行。
至于这个封装为什么是结构体呢?
在C++中,struct和class是非常相似的,唯一的区别是默认的访问权限不同。在struct中,成员默认是公共的(public),而在class中,默认是私有的(private)。因此,在C++中,struct内部是可以定义函数的。
在这个结构体的内部我们需要解决迭代器的遍历、解引用、遍历修改、不等于 等运算符重载问题!
//*T& operator*(){return _node->_data;}//前置++ 因为这里是链表所以++应该是指向下一个节点!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;}slef& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return _node != it._node;}
我们定义这些重载运算符的意义就在于为了之后我们在定义begin时,可以直接使用封装的重载运算符!
typedef ListIterator<T> iteator;iterator begin(){iterator it(_head->_next);return it;}iterator end(){iterator it(_head);return it;}
自定义类型的完善:
自定义类型的完善 ,因为我们写的是一个自定义类型,所以读取*it后解决完后还是一个自定义类型的数据结构,所以需要在使用数据结构的写法,表明其中内部的数据即可!
T* operator->(){return &_node->_data;}
it->是需要进行拆解的,可以变成it.operator()->,这里其实是编译器的一种隐藏操作,之前的it++也是一种隐藏操作,可以变化为it.operator++()
而it->_a1这里隐藏的是另一个-> ,也就是图中第二个->,第一个->是属于it的重载运算符标识!
const的迭代器:
首先要记住const不能调用非const的成员函数!但是非const可以调用const的成员函数
为了让const修饰的类型能够使用迭代器,我们需要根据const不能修改内容的特点进行另外设置一共专门让const使用的迭代器封装,但是由于只是需要变动operator*()和operator->所以我们可以使用模板类解决这类问题!
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;}// ++itSelf& 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;}};
insert
有了迭代器之后了,可以利用迭代器的操作进行insert的底层实现
void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode cur;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}
erase:
操作和insert一样都是对指针的方向的修改!但是pos会在后面失效,也就是迭代器会失效,所以需要改变类型!然后进行返回!这里的返回变成了的pos节点的后面一个节点的迭代器。
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);}
size
size_t size() const{return _size;}
empty
bool empty(){return _size == 0;}
push_back 、push_front 、pop_back、pop_front
void push_back(const T& x)//尾插{insert(end(), x);}void push_front(const T& x)//头插{insert(begin(), x);}void pop_back()//尾删{erase(--end());}void pop_front()//头删{erase(begin());}
swap 、operator=
void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}
析构函数、clear()
void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}