嗨喽大家好,时隔许久阿鑫又给大家带来了新的博客,list的模拟实现(一),下面让我们开始今天的学习吧!
list的模拟实现(一)
1.list splice接口的使用
2.list尾插的实现
3.list的迭代器模拟实现
4.const迭代器
5.insert和erase的模拟实现
1.list splice接口的使用
int main()
{std::list<int> mylist1;mylist1.push_back(1);mylist1.push_back(2);mylist1.push_back(3);mylist1.push_back(4);auto it = find(mylist1.begin(), mylist1.end(), 3);mylist1.splice(++mylist1.begin(), mylist1, it);//1324for (auto ch: mylist1){cout << ch << " ";}cout << endl;return 0;
}
2.list尾插的实现
3.list的迭代器模拟实现
原生指针的++是连续的物理空间的++。
因为类能进行运算符重载,我直接对节点进行++达不到我的要求,所以我就将节点指针封装成一个类,这个类的行为就是遍历双向循环列表。
每一个类都有自己需要完成的事情,也可以是几个类互相搭配完成一件事情。
template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _date;ListNode(const T& date = T()):_next(nullptr),_prev(nullptr),_date(date){}};template<class T>class ListIterator{typedef ListNode<T> Node;//此处传T的时候就相当于实例化typedef ListIterator<T> self;public:ListIterator(Node* node)//用一个节点的指针来构造:_node(node){}//++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;
}T& operator*()
{return _node->_date;
}T* operator->()
{return &_node->_date;
}bool operator!=(const self& it)
{return _node != it._node;
}
bool operator==(const self& it)
{return _node == it._node;
}private://成员是一个节点的指针,将指针封装成类来达到我们想要实现的操作Node* _node;};template<class T>class list{public:typedef ListNode<T> Node;typedef ListIterator<T> iterator;//若T为int相当于实例化了一个int类型的iteratoriterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;//head 2 3 tail newnodetail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private:Node* _head;};
iterator类不需要写析构函数,构造函数。节点是由链表管理的。(一般一个类不写析构函数,就不用写拷贝构造和赋值)
在C、C++等语言中,指针访问结构体(struct)或联合体(union)的成员时,我们使用箭头(->)操作符。而当我们**直接访问结构体或联合体的成员(即不通过指针)时,我们使用点(.)**操作符。
注意:对于->操作符,可以得到一个指向节点有效数据的指针(下图pos坐标(中存储的是行和列)类似于节点中的_date),应该如下图注释所进行调用,但是编译器为了可读性,强行省略了一个箭头
struct pos
{int _row;int _col;pos(int row = 0,int col = 0 ):_row(row),_col(col){}};void list_test2()
{list<pos> it1;it1.push_back(pos(100,200));it1.push_back(pos(200,300));it1.push_back(pos(300,400));list<pos>::iterator it = ++it1.begin();while (it != it1.end()){cout << it->_col << ":" << it->_row <<endl;it++;}cout << endl;
}
匿名对象的临时对象可以调用非const的成员函数
4.const迭代器
const迭代器不能是普通迭代器前加const
const迭代器目标本身可以修改,指向的内容不能修改,类似const T* p
注意:不能在模板参数T前加上const
第一种方式:
template<class T>
class ListConstIterator
{typedef ListNode<T> Node;//此处传T的时候就相当于实例化typedef ListConstIterator<T> self;
public:ListConstIterator(Node* node)//用一个节点的指针来构造:_node(node){}//++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;}const T& operator*(){return _node->_date;}const T* operator->(){return &_node->_date;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}private://成员是一个节点的指针,将指针封装成类来达到我们想要实现的操作Node* _node;
};template<class T>
class list
{public:typedef ListNode<T> Node;typedef ListIterator<T> iterator;//若T为int相当于实例化了一个int类型的iteratortypedef ListConstIterator<T> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return iterator(_head->_next);}const_iterator end()const{return iterator(_head);}
第二种方式:不同的模板参数表达的是不同的类,正如vector< int>和vector< double>表达的是两个不同的类
template<class T,class Ref,class Ptr>
class ListIterator
{typedef ListNode<T> Node;//此处传T的时候就相当于实例化typedef ListIterator<T,Ref,Ptr> self;
public:ListIterator(Node* node)//用一个节点的指针来构造:_node(node){}//++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;}Ref operator*(){return _node->_date;}Ptr operator->(){return &_node->_date;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}private://成员是一个节点的指针,将指针封装成类来达到我们想要实现的操作Node* _node;
};
5.insert和erase的模拟实现
链表的insert没有迭代器失效,erase迭代器有失效