🌈个人主页:羽晨同学
💫个人格言:“成为自己未来的主人~”
构造函数生成
template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& data = T()):_next(nullptr),_prev(nullptr),_data(data){}};
在这个构造函数当中,有几个特别优秀的点需要注意:
- const &的使用的好处:
- 使得代码更加高效,具体解释为:如果我们使用&,那么我们可以直接使用传递的值,而不需要再进行构造,生成副本,提高了效率。
- T()这个隐式类型对象的使用,如果我们什么都不传的时候,代码会默认使用T(),如果这个时候是值传递,那么我们需要生成一个构造,然后再传递给data,而&的时候,我们可以直接调用。
- T()的使用
- 适用于所有类型,因为传入的数据类型不确定,所以我们只能使用T()
迭代器部分代码
template<class T, class Ref , class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;
在链表中实现迭代器和vector,string中实现迭代器的代码实现不同,这是由于二者之间的底层逻辑不同,无论是string还是vector,它的底层都是连续的,而list不是这样的,所以我们之前使用的那样子就不可以了。
前置++和前置--
Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}
我们先对它进行修改,然后返回修改后的值。
后置++和后置--
Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}
因为是先使用后++,所以我们先将节点放在一个变量当中。
*和->的实现
Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
!=和==功能的实现
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;public:typedef ListIterator<T, T&, T*>iterator;typedef ListIterator<T, const T&, const T*>const_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){retrun iterator(_head);}const_iterator end() const{return const_iterator(_head);}
哨兵位节点构造
list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}
插入删除功能实现
void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}
insert和erase功能实现
iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}
打印功能
void Func(const list<int><){list<int>::const_iterator it = lt.begin();while (it !=lt.end()){cout << *it << " ";++it;}cout << endl;}
测试代码1
void test_list1(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);Func(lt1);list<int>::iterator it = lt1.begin();while (it != lt1.end()){*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt1){cout << e << " ";}cout << endl;}
测试代码2
struct Pos{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}};void test_list2(){list<Pos> lt1;lt1.push_back(Pos(100, 100));lt1.push_back(Pos(200, 200));lt1.push_back(Pos(300, 300));list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;}