本篇通过模拟实现list的构造函数,迭代器,和部分成员函数以帮助大家更加深层的理解list的原理,希望看完这篇文章使得友友们对list有了更加深层的理解.
一、list底层框架
list的底层是一个带头双向循环链表.
(1) 节点类
因为list中节点可能存储各种类型的值,所以这里使用了一个模板参数T.
list <int> list<doubel> …
// List的节点类 template<class T> struct list_node { list_node(const T& val = T()) :_val(val) {} //这里的 T() 表示使用类型 T 的默认构造函数创建一个对象， //它将调用 T 类型的默认构造函数来初始化 val。如果类型 T 没有提供默认构造函数，那么代码将无法编译通过。 list_node<T>* _prev=nullptr; //指向前驱结点 list_node<T>* _next=nullptr; //指向后继结点 T _val; //存储数据 };
(2) 迭代器类
很多小伙伴会疑问,为什么一个迭代器类却使用了三个模板参数,是不是有些多余呢?
其实不然,牛牛依次为大家解释.
1.class T: 是结点类的存储不同数据所需要使用的模板参数.该模板参数表示要处理的元素的类型。它可以是任意类型，例如整数、浮点数、自定义类等等。在模板实例化时，需要提供一个具体的类型。
2.Ref: 该模板参数表示指向元素类型 T 的引用。它定义了对元素的引用类型，在实例化模板时，将使用指定的引用类型来操作元素。
3.Ptr: 该模板参数表示指向元素类型 T 的指针。它定义了指向元素的指针类型，在实例化模板时，将使用指定的指针类型来操作元素。
template<class T, class Ref, class Ptr>
意味着
list_iterator<T, const T&, const T*>;
list的迭代器用来遍历链表中的元素,外部通过迭代器的++和--进行链表的元素访问,这是一种封装,隐藏内部list的实现细节,外部只能通过迭代器的方式访问.
//迭代器类 template<class T, class Ref, class Ptr> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T, Ref, Ptr> self;//self表示自己 list_iterator(Node* node); //构造 list_iterator(const self& list); //拷贝构造 Ref operator*(); Ptr operator->(); //前置++ self& operator++(); //后置++ self operator++(int); //前置-- self& operator--(); //后置-- self& operator--(int); bool operator!=(const self& list) const; bool operator==(const self& list); //成员变量 Node* _node; };
(3) list类
template<class T> class list { typedef list_node<T> Node; public: typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; list()//(无参构造) //n个value构造 list(int n, const T& value = T()); //迭代器区间构造 template <class Iterator> list(Iterator first, Iterator last); //拷贝构造 list(const list<T>& list); //各种成员函数 /... //析构函数 ~list(); iterator begin(); iterator end(); //常属性迭代器 const_iterator begin()const; const_iterator end()const; private: Node* _head; size_t _size; };
二、构造函数
对于带头双向循环链表,它的初始化操作是必须的,因为必须创建一个头指针.
对于list的构造函数,它是很多种方式的,例如:无参构造,n个val构造,迭代器区间构造等.
对于每个构造,必须前进行最初的初始化操作,为了避免代码冗余,我们将这个部分单独写成一个初始化操作的函数.
如下:
void Init_List() { _head = new Node; //创建头指针 _head->_prev = _head; _head->_next = _head; _size = 0; }
(1) 无参构造
调用Init_List();初始化函数即可.
list()//初始化很重要(无参构造) { Init_List(); }
(2) n个value构造
- 进行初始化操作.
- 尾插n个value.
//n个value构造 list(int n, const T& value = T()) { Init_List(); while (n--) { push_back(value); } }
(3) 迭代器区间构造
- 进行初始化操作.
- 利用迭代器的特性,一次将区间中的数据尾插入链表.
//迭代器区间构造 template <class Iterator> list(Iterator first, Iterator last) { Init_List(); while (first != last) { push_back(*first); ++first; } }
(4) 拷贝构造
链表在物理空间上是不连续的,所以,对于参数是另一个链表的拷贝构造,只能遍历链表进行依次插入数据.
//拷贝构造 list(const list<T>& list) { Init_List(); auto it = list.begin(); while (_size!=list._size) { push_back(*it); it++; } }
三、迭代器
迭代器的实现
① 构造
迭代器本质就是一个 Node* _node;结点类的指针.
对于迭代器的构造函数,只需要将结点的地址传过来即可.
list_iterator(Node* node) //默认构造 :_node(node) {} list_iterator(const self& list) //拷贝构造 :_node(list._node){}
② *和->
(1) *
*运算符重载,表示对迭代器进行解引用.
使用场景:
list<int>::iterator it = L1.begin(); int start=*it;
很明显,*运算符是需要获取结点所存储的数据.为了减少拷贝以及对数据进行修改,这里采用传引用(Ref )返回.
Ref operator*() { return _node->_val;//获取该结点的数据 }
(2) ->
上面链表中的数据是简单的类型int
Ptr operator->() { return &_node->_val; // 等价于 return &(_node->_val); }
③ 前置++与后置++
对于链表,迭代器++表示向后访问下一个(后继)结点.学过链表的友友们应该知道.
也就是
_node = _node->_next;
前置++,返回++后的结点的迭代器
后置++,返回++前的结点的迭代器
//前置++ self& operator++() { _node = _node->_next; return *this; } //后置++ self operator++(int) { Node* tmp=_node; //保存++之前的值 _node = _node->_next; return tmp; //返回++之前的值 }
④ 前置–与后置–
同理,返回当前结点迭代器的前驱结点.
也就是:
_node = _node->_prev;
前置–,返回–后的结点的迭代器
后置–,返回–前的结点的迭代器
//前置-- self& operator--(){ _node = _node->_prev; return *this; } //后置-- self& operator--(int){ Node* tmp = _node; //保存 -- 之前的值 _node = _node->_prev; return tmp; //返回 -- 之前的值 }
⑤ 比较运算符
比较迭代器是否相等,实际就是比较迭代器所指向的结点是否相等.
bool operator!=(const self& list) const { return _node != list._node; } bool operator==(const self& list){ return _node == list._node; }
list类中的迭代器
iterator begin(): 返回第一个有效元素位置的迭代器
iterator end(): 返回最后一个有效元素位置的迭代器
typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; iterator begin() { return _head->_next; //也可以强转一下 //return iterator(_head->_next); } iterator end() { return _head; //也可以强转一下 // return iterator(_head); } //常属性迭代器 const_iterator begin()const { return _head->_next; } const_iterator end()const { return _head; }
front和back
T& front() { return _head->_next->_val;//返回值 } const T& front()const { return _head->_next->_val; } T& back() { return _head->_prev->_val; } const T& back()const { return _head->_prev->_val; }
四、Modifiers:
其实带头双向循环链表的增删改查较于单链表,更加简单,我们画图分析还是很容易实现的.
(1) insert()
(图片为博主原创,不得随意截图使用)
特殊情况:这是尾插:
(图片为博主原创,不得随意截图使用)
代码示例
// 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { //pos.node 而不是pos->node Node* newnode = new Node(val); Node* _prev_node = pos._node->_prev; //pos位置结点的 原前置 结点 Node* _cur_node = pos._node; //pos位置的结点 _prev_node->_next = newnode; newnode->_prev = _prev_node; _cur_node->_prev = newnode; newnode->_next = _cur_node; ++_size;//有效数据的个数+1. return newnode; }
(2) erase()
// 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos) { Node* _prev_node = pos._node->_prev; //pos位置结点的 原前置(prev) 结点 Node* _next_node = pos._node->_next; //pos位置结点的 原后置(next) 结点 _next_node->_prev = _prev_node; _prev_node->_next = _next_node; delete pos._node; --_size; return _next_node; }
(3) push_back() 和 push_front()
//尾插 //void push_back(const T& val) //{ // Node* newnode = new Node(val); // Node* _tail_node = _head->_prev; // 原尾结点 // _tail_node->_next = newnode; // newnode->_prev = _tail_node; // _head->_prev = newnode; // newnode->_next = _head; // // ++_size;//有效数据的个数+1. //} //复用insert更加方便 void push_back(const T& val){ insert(end(),val);//在头结点前面插入,即为尾插 } //头插 void push_front(const T& val) { insert(begin(), val); }
(4) pop_back() 和 pop_front()
复用即可,不过多介绍了.
//尾删 void pop_back() { erase(--end()); } //头删 void pop_front() { erase(begin()); }
(5) clear()
clear:清除list中的有效数据
遍历链表进行依次删除结点,并将size置为0.
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } _size = 0; }
(6) swap()
交换两个链表的成员变量即可.
void swap(list<T>& list) { swap(_head, list._head); swap(_size, list._size); }
结语
看完这篇文章,相信大家对list有了更加深层的理解,对于list的迭代器,它并不像前面的string和vector那种原生指针,而是封装成了类,使得链表的迭代器也可以执行++和--等操作,因为迭代器类重载了这些运算符.
今天就分享到这里了,如果觉得有帮助的话,可以给牛牛来一个一键三连吗?谢谢支持!
