什么网站可以做兼职美工,欧美电影免费网站,虚拟主机网站,商河县做网站公司目录
list的介绍
list的使用
list的构造
list iterator的使用
list capacity
list modifiers
list的迭代器失效
list模拟实现 list的介绍 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。 2. list的底层是双向…目录
list的介绍
list的使用
list的构造
list iterator的使用
list capacity
list modifiers
list的迭代器失效
list模拟实现 list的介绍 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3.与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 list的使用
list的构造 1.list(size_t n,const T lt T()) 说明构造的list中包含n个值为val的元素 2.list() 说明构造空的list 3.list(const list x) 说明拷贝构造函数 4.list(InputIterator first,InputIterator last) 说明用[first,last)区间中的元素构造list
list iterator的使用
此时我们暂且将迭代器理解成一个指针该指针指向list中的某个节点。 beginend返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器 rbeginrend返回第一个元素的reverse_iterator即end位置返回最后一个元素下一个位置的reverse_iterator即begin位置 注意
1. begin与end为正向迭代器对迭代器执行操作迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动
list capacity empty检测list是否为空是返回true否则返回false size返回list中有效节点个数 list modifiers push_front在list首元素前插入值为val的元素 pop_front删除list中的第一个元素 push_back在list尾部插入值为val的元素 pop_back删除list中的最后一个元素 insert在pos位置插入值为val的元素 erase删除pos位置的元素 swap交换两个list中的元素 clear清空list中的有效元素 list的迭代器失效
我们将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){//错误示范//erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给
其赋值//l.erase(it);//it;//正确it l.erase(it);}
}
list模拟实现
namespace ghs
{templateclass Tstruct ListNode{ListNode(const T x T()):_next(nullptr),_prev(nullptr),_data(x){}ListNodeT* _next;ListNodeT* _prev;T _data;};templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIterator Self;Node* _node;ListIterator(Node* node):_node(node){}//*it//不能传值返回*it只能传引用返回因为除了读还有写的功能//T operator*()Ref operator*(){return _node-_data;}//itSelf operator(){_node _node-_next;return *this;}//itSelf operator(int){Self tmp(*this);_node _node-_next;return tmp;}//--itSelf operator--(){_node _node-_prev;return *this;}//it--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;}//T* operator-()Ptr operator-(){return _node-_data;}};//templateclass T//struct ListConstIterator//{// typedef ListNodeT Node;// typedef ListConstIterator Self;// Node* _node;// ListConstIterator(Node* node)// :_node(node)// {}// //*it// //不能传值返回*it只能传引用返回因为除了读还有写的功能// const T operator*()// {// return _node-_data;// }// //it// Self operator()// {// _node _node-_next;// return *this;// }// //it// Self operator(int)// {// Self tmp(*this);// _node _node-_next;// return tmp;// }// //--it// Self operator--()// {// _node _node-_prev;// return *this;// }// //it--// 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;// }// const T* operator-()// {// return _node-_data;// }//};templateclass Tclass list{typedef ListNodeT Node;public:/*typedef ListIteratorT iterator;typedef ListConstIteratorT const_iterator;*/typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;//iterator begin()//{// //匿名对象 // return iterator(_head-_next);//}iterator begin(){return _head-_next;}iterator end(){return _head;}//如果返回值类型是const iterator那表示迭代器本身不能被修改而不是迭代器指向的内容不能被修改//我们需要的是迭代器指向的内容不能被修改const iterator不是我们需要的迭代器const_iterator begin()const{return _head-_next;}const_iterator end()const{return _head;}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}list(){empty_init();}//lt2(lt1)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}//需要析构一般就需要自己写深拷贝//不需要析构一般就不需要自己写深拷贝默认浅拷贝就可以void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}listT operator(listT lt)//()里调用了拷贝构造{swap(lt);return *this;}//void push_back(const T x)//{// Node* newnode new Node(x);// Node* tail _head-_prev;// tail-_next newnode;// newnode-_prev tail;// newnode-_next _head;// _head-_prev newnode;//}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());}void insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);//prev newnode cur newnode-_next cur;cur-_prev newnode;prev-_next newnode;newnode-_prev prev;_size;}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_t size()const{return _size;}bool empty(){return _size 0;}//不清除头结点只是把数据清掉void clear(){iterator it begin();while (it ! end()){it erase(it);}}~list(){clear();delete _head;_head nullptr;}private:Node* _head;size_t _size;};
}
