网站 aspx 模板,做网站多久才会有收益,wordpress分类目录顺序,北京做网站费用文章目录 一、list链表的使用1、迭代器2、头插、头删3、insert任意位置插入4、erase任意位置删除5、push_back 和 pop_back()6、emplace_back尾插7、swap交换链表8、reverse逆置9、merge归并10、unique去重11、remove删除指定的值12、splice把一个链表的结点转移个另一个链表13… 文章目录 一、list链表的使用1、迭代器2、头插、头删3、insert任意位置插入4、erase任意位置删除5、push_back 和 pop_back()6、emplace_back尾插7、swap交换链表8、reverse逆置9、merge归并10、unique去重11、remove删除指定的值12、splice把一个链表的结点转移个另一个链表13、sore排序 二、operator-三、list常用接口模拟实现 截图内容来源
一、list链表的使用 是一个支持O(1)时间复杂度插入和删除的链表结构迭代器是双向的底层是一个带头双向循环链表。
1、迭代器 双向迭代器 、–
2、头插、头删
头插 头删
3、insert任意位置插入 更具迭代器来完成位置的确定
4、erase任意位置删除 位置用迭代器表示也可以删除一个迭代器区间
5、push_back 和 pop_back()
头插 头删:
6、emplace_back尾插 跟push_back有差异,push_back要插入的类型被固定可以支持隐式类型转换。 emplace_back不支持隐式类型转换但可以直接传要初始的值进行构造。
class pos
{
private:int _row;int _col;
public:pos(int row 0, int col 0):_row(row),_col(col){}};int main()
{listpos lt;pos p1(1, 2);lt.push_back(p1);lt.push_back(pos(2, 3));lt.push_back({ 2,3 });//隐式类型转换lt.emplace_back(p1);lt.emplace_back(pos(2,3));lt.emplace_back(2, 3);//可变模版参数return 0;
}7、swap交换链表 比算法库里的swap更高效底层是交换指向头结点。
8、reverse逆置 插入1到9打印9到1
9、merge归并 合并完后链表x为空
10、unique去重 排成有序的再去重
11、remove删除指定的值 remove_if满足条件再删
12、splice把一个链表的结点转移个另一个链表 可以调整链表里面的顺序把自己的结点转移给自己
13、sore排序 默认排序是升序 如果想降序要使用仿函数 让他大于就交换
int main()
{listint ls({ 1,-2,0,3,8,7 });for (auto c : ls){cout c ;}cout endl;ls.sort();//升序ls.sort(greaterint());//降序for (auto c : ls){cout c ;}return 0;
}list 自己实现的sort是支持双向迭代器的算法库里的sort是传随机迭代器
二、operator-
class pos
{
private:public:pos(int row 0, int col 0):_row(row),_col(col){}int _row;int _col;
};int main()
{listpos lt;pos p1(1, 2);lt.push_back(p1);listpos::iterator i lt.begin();cout i-_row;//这样写省略了一个-//相应于调用 i.operator-()-_row;return 0;
}三、list常用接口模拟实现
#pragma once
#include iostream
#include assert.h
namespace lsh
{//List节点类templateclass Tstruct ListNode{ListNode(const T val T()):_val(val),_pPre(nullptr),_pNext(nullptr){}ListNodeT* _pPre;ListNodeT* _pNext;T _val;};//反向迭代器templateclass Iterator,class Ref,class Ptrstruct Reverse_iterator{Iterator _it;typedef Reverse_iterator Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){return *_it;}Ptr operator-(){return _it.operator-();}Reverse_iterator operator(){--_it;return *this;}Reverse_iterator operator--(){_it;return *this;}Reverse_iterator operator(int){Reverse_iterator tmp *this;--_it;return tmp;}Reverse_iterator operator--(int){Reverse_iterator tmp *this;_it;return tmp;}bool operator!(const Self l){return _it ! l._it;}};//List的迭代器类templateclass T, class Ref, class Ptrclass ListIterator{typedef ListNodeT* PNode;typedef ListIteratorT, Ref, Ptr Self;public:ListIterator(PNode pNode nullptr):_pNode(pNode){}ListIterator(const Self l):_pNode(l._pNode){}Ref operator*(){return _pNode-_val;}Ptr operator-(){return _pNode-_val;}Self operator(){_pNode _pNode-_pNext;return *this;}Self operator--(){_pNode _pNode-_pPre;return *this;}Self operator(int){Self tmp *this;_pNode _pNode-_pNext;return tmp;}Self operator--(int){Self tmp *this;_pNode _pNode-_pPre;return tmp;}bool operator!(const Self l){return _pNode ! l._pNode;}bool operator(const Self l){return !(*this ! l);}PNode Get(){return _pNode;}private:PNode _pNode;};//list类templateclass Tclass list{typedef ListNodeT Node;typedef Node* PNode;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;public://List的构造list(){CreateHead();}list(int n, const T value T()){CreateHead();for (int i 0; i n; i){push_back(value);}_size n;}templateclass Iteratorlist(Iterator first, Iterator last){CreateHead();while (first ! last){push_back(*first);first;}}list(const listT l){CreateHead();for (auto c : l){push_back(c);}}listT operator(listT l){swap(l);return *this;}~list(){clear();delete _pHead;}/////List Iteratoriterator begin(){return (iterator)_pHead-_pNext;}iterator end(){return (iterator)_pHead;}const_iterator begin()const{return (const_iterator)_pHead-_pNext;}const_iterator end()const{return (const_iterator)_pHead;}reverse_iterator rbegin(){return (reverse_iterator)_pHead-_pPre;}reverse_iterator rend(){return (reverse_iterator)_pHead;}const_reverse_iterator rbegin() const{return (const_reverse_iterator)_pHead-_pPre;}const_reverse_iterator rend()const{return (const_reverse_iterator)_pHead;}////List Capacitysize_t size()const{return _size;}bool empty()const{return _size 0;}///List AccessT front(){return *(begin());}const T front()const{return *(begin());}T back(){return *(--end());}const T back()const{return *(--end());}/////List Modifyvoid push_back(const T val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}//在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){PNode tmp pos.Get();PNode newnode new Node(val);newnode-_pNext tmp;newnode-_pPre tmp-_pPre;tmp-_pPre-_pNext newnode;tmp-_pPre newnode;_size;return newnode;}//删除pos位置的节点iterator erase(iterator pos){assert(pos ! _pHead);PNode del pos.Get();PNode next del-_pNext;PNode pre del-_pPre;pre-_pNext next;next-_pPre pre;delete del;_size--;return (iterator)next;}void clear(){while (_size){pop_back();}}void swap(listT l){std::swap(_pHead, l._pHead);}private:void CreateHead(){_pHead new Node();_size 0;_pHead-_pPre _pHead;_pHead-_pNext _pHead;}PNode _pHead;size_t _size;};}
