网站开发的实施方案,做响应网站的素材网站,网页网站建设的ppt,android直播app开发list 1. 简单了解list2. list的常见接口3. 简单实现list4. vector和list比较 1. 简单了解list
list的底层是带头双向循环列表。因此list支持任意位置的插入和删除#xff0c;且效率较高。但其缺陷也很明显#xff0c;由于各节点在物理空间是不连续的#xff0c;所以不支持对… list 1. 简单了解list2. list的常见接口3. 简单实现list4. vector和list比较 1. 简单了解list
list的底层是带头双向循环列表。因此list支持任意位置的插入和删除且效率较高。但其缺陷也很明显由于各节点在物理空间是不连续的所以不支持对任意位置的访问效率低。list的迭代器底层不仅仅是指针这么简单因为其迭代器支持前后双向迭代而其空间又不连续所以其底层是对指针的封装。后面讲
2. list的常见接口
构造 例子
普通迭代器 与其他容器的迭代器一样只不过list的底层实现更加复杂现在暂且将其看成指针。 例子
//迭代器
void test3()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;
}
//运行结果
//1 2 3 4头插头删和尾插尾删
例子
void test2()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();lt.push_front(4);lt.push_front(3);lt.push_front(2);lt.push_front(1);for (auto e : lt){cout e ;}cout endl;
}
//运行结果
//1 2 3 4
//1 2 3 4插入 例子
void test3()
{listint lt;lt.push_back(1);lt.push_back(3);lt.push_back(4);//想在第二个位置插入2怎么做//lt.insert(lt.begin()1,2);//错误的list的iterator没有重载。这个等下讲原因。auto it lt.begin();it;lt.insert(it, 2);for (auto e : lt){cout e ;}cout endl;
}
//运行结果
//1 2 3 4这样确定插入位置太麻烦了可以用find查找。
auto it find(lt.begin(),lt.end(),3);
if (it ! lt.end())
{lt.insert(it,2);
}删除 例子 //删除偶数//删除后迭代器还指向被删除空间存在迭代器失效问题//所以要重新赋值it lt.begin();while (it ! lt.end()){if (*it % 2 0){it lt.erase(it);}else{it;}}front和back 例子
逆置和排序 例子
void test5()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.reverse();for (auto e : lt){cout e ;}cout endl;lt.sort();for (auto e : lt){cout e ;}cout endl;
}
//运行结果
//4 3 2 1
//1 2 3 4拓展 1库里也有sort为什么还要在list再写一个C库的sort不能用。 2这涉及到迭代器的分类。从功能上由容器底层结构决定迭代器有单项迭代器、双向迭代器和随机迭代器。单项迭代器只能向后迭代例如forward_list/unordered_xxx的迭代器双向迭代器能/–例如list/map/set随机迭代器能/-//–例如string/vector/deque。 3有随机迭代器的容器能用随机的、双向的、单向的迭代器的库函数有双向迭代器的容器能用双向的、单向的迭代器的库函数。 4list的迭代器类型是双向的库函数sort的迭代器类型是随机的所以list的数据排序不能用库函数sort。
归并 例子
void test6()
{listint lt1;lt1.push_back(1);lt1.push_back(3);lt1.push_back(5);lt1.push_back(7);listintlt2;lt2.push_back(2);lt2.push_back(4);lt2.push_back(6);lt2.push_back(8);lt1.merge(lt2);for (auto e : lt1){cout e ;}cout endl;cout lt1的大小为 lt1.size() endl;cout lt2是否变为空 lt2.empty() endl;
}unique 例子 listint lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(2);lt1.push_back(2);lt1.unique();cout lt1的大小 lt1.size() endl;for (auto e : lt1){cout e ;}cout endl;remove listint lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(2);lt1.push_back(2);lt1.remove(1);//相当于finderasecout lt1的大小 lt1.size() endl;for (auto e : lt1){cout e ;}cout endl;remove不像erase它的参数是值而不是迭代器且remove如果要移除的值不存在不会报错。
splice listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint lt2;lt2.push_back(5);lt2.push_back(6);lt2.push_back(7);lt2.push_back(8);lt1.splice(lt1.begin(), lt2);//将lt2的所有节点全部转移到lt1之前lt1.splice(lt1.begin(), lt2,--lt2.end());//将lt2的最后一个元素转移到lt1之前lt1.splice(lt1.begin(), lt2, lt2.begin(), lt2.end());//将迭代器区间的节点转移到lt1之前lt1.splice(lt1.begin(), lt1, lt1.begin(), lt1.end());//将lt1第一个节点后面的节点转移到lt1之前for (auto e : lt1){cout e ;}cout endl;3. 简单实现list
#includeiostream
using namespace std;namespace zn
{//节点templateclass Tstruct ListNode{ListNodeT* _prev;ListNodeT* _next;T _val;ListNode(const T val T()):_prev(nullptr), _next(nullptr), _val(val){}};//迭代器双向迭代器//迭代器底层都是指针但有些指针需要封装例如节点的指针不然不能满足/--等操作templateclass T, class Ref, class Ptr//T T, Ref T/const T, Ptr T*/const T*struct __list_iterator{typedef ListNodeT* iterator;typedef __list_iteratorT, Ref, Ptr This;iterator _node;//构造__list_iterator(iterator node):_node(node){}//*重载Ref operator*(){return _node-_val;}//-重载//如果T恰好是结构体类型而迭代器又被看成指针那么-就可以派上用场Ptr operator-(){return (_node-_val);}//重载This operator(){_node _node-_next;return *this;}This operator(int){This tmp(_node);_node _node-_next;return tmp;}//--重载This operator--(){_node _node-_prev;return *this;}This operator--(int){This tmp(_node);_node _node-_prev;return tmp;}//重载和!重载bool operator(__list_iterator lit)const{return _node lit._node;}bool operator!(__list_iterator lit)const{return !(_node lit._node);}};//反向迭代器//对正向迭代器的封装从而得到我们想要的操作templateclass T,class Ref,class Ptrclass ReverseIterator{typedef __list_iteratorT, Ref, Ptr iterator;typedef ReverseIteratorT, Ref, Ptr reverse_iterator;iterator _it;ReverseIterator(iterator it):_it(it){}public:Ref operator*(){iterator tmp _it;return *(--tmp);}Ptr operator-(){return (operator*());}reverse_iterator operator(){--_it;return *this;}reverse_iterator operator(int){reverse_iterator tmp *this;--_it;return tmp;}reverse_iterator operator--(){_it;return *this;}reverse_iterator operator--(int){reverse_iterator tmp *this;_it;return tmp;}bool operator!(const reverse_iterator rit){return _it ! rit._it;}bool operator(const reverse_iterator rit){return _it rit._it;}};//listtemplateclass Tclass list{typedef ListNodeT Node;typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;typedef ReverseIteratorT, T, T* reverse_iterator;typedef ReverseIteratorT, const T, const T* const_reverse_iterator;public://构造list(){_head new Node;_head-_prev _head;_head-_next _head;_size 0;}//拷贝构造list(const listT lt)//list(const list lt){_head new Node;_head-_prev _head;_head-_next _head;_size 0;for (auto e : lt){push_back(e);}_size lt._size;}//交换void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//重载listT operator(listT lt){swap(lt);return *this;}//析构~list(){Node* cur _head-_prev;while (cur ! _head){Node* tmp cur-_next;delete cur;cur tmp;}delete _head;_head nullptr;}//迭代器iterator begin(){return _head-_next;}const_iterator begin()const{return _head-_next;}iterator end(){return _head;}const_iterator end()const{return _head;}reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend()const{return const_reverse_iterator(begin());}//插入默认在pos前插入iterator insert(iterator pos, const T val){Node* newnode new Node(val);Node* cur pos._node;Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;cur-_prev newnode;newnode-_next cur;_size;//隐式类型转换//返回指针类型然后用类类型接收会调用构造return newnode;}//删除iterator earse(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;--_size;return next;}//尾插和尾删void 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());}//大小size_t size(){return _size;}//清理void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}private://指向头节点Node* _head;size_t _size;};void test_iterator(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}
}4. vector和list比较
vectorlist底层顺序表可扩容双向循环链表带头节点效率具有连续的空间空间利用率高访问元素效率高支持随机访问插入和删除元素效率低需要挪动元素时间复杂度为O(N)底层开辟节点空间利用率低访问元素效率低不支持随机访问 插入和删除元素效率高时间复杂度为O(1)迭代器是原生态指针是随机迭代器支持/-等操作无论是插入还是删除都会导致迭代器失效插入需要扩容扩容后原来的迭代器失效是对原生态指针的封装是双向迭代器不支持/-等操作 删除会导致迭代器失效应用适用于插入和删除操作少访问多的情况适用于插入和删除操作多访问少的情况
