建设厅证书查询网站,浙江网站建设哪家好,免费注册126邮箱,建设网上银行怎么开通文章目录 list的介绍list的使用list的构造list iterator的使用list capacitylist元素访问list modifierslist的迭代器失效 list与vector的对比 list的介绍 list是可以在常数范围内的任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代#xff1b; … 文章目录 list的介绍list的使用list的构造list iterator的使用list capacitylist元素访问list modifierslist的迭代器失效 list与vector的对比 list的介绍 list是可以在常数范围内的任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代 list的底层是双向链表结构双向链表中每个元素存储在不互相关的独立节点中在节点中通过指针指向前一个与后一个元素 list与forward_list非常相似forward_list是单链表只能向前迭代 与其他的序列式容器相比list通常在任意位置进行插入、移动元素的执行效率更好。但是list和forward_list最大的缺陷是不支持任意位置的随机访问如果要访问某一位置必须要从已知的位置开始迭代到对应位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间用来保存每个节点的相关信息。
list的使用
list的构造
构造函数constructor接口说明list(size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list()构造空的listlist(const list x)拷贝构造函数list(InputIterator first, InputIterator last)用[first, last]区间中的元素构造list
int main()
{listint first;listint second(4, 100);listint third(second.begin(), second.end());listint fourth(third);int myints[] { 1, 2, 3, 4 };listint fifth(myints, myints sizeof(myints) / sizeof(int));cout The contents of fifth are:;for (listint::iterator it fifth.begin(); it ! fifth.end(); it)cout *it ;cout endl;return 0;
}list iterator的使用
函数声明接口说明beginend返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbeginrend返回第一个元素的reverse_iterator即end位置返回最后一个元素下一个位置的reverse_iterator即begin位置cbegincend返回第一个元素的const_iterator返回最后一个元素下一个位置的const_iteratorcrbegincrend返回第一个元素的const_reverse_iterator即end位置返回最后一个元素下一个位置的const_reverse_iterator即begin位置 begin与end是正向迭代器对迭代器执行操作迭代器向后移动 rbegin与rend作为反向迭代器对迭代器执行操作迭代器向前移动 cbegincend与crbegincrend是C11引入的。
int main()
{int myints[] { 1, 2, 3, 4, 5 };listint mylist(myints, myints 5);cout myints contains:;for (listint::iterator it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;cout myints backwards:;for (listint::reverse_iterator rit mylist.rbegin(); rit ! mylist.rend(); rit)cout *rit;cout endl;return 0;
}list capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数max_size返回最大节点的个数
int main()
{listint mylist;int sum(0);cout max_size: mylist.max_size() endl;cout 1.size: mylist.size() endl;for (int i 1; i 10; i)mylist.push_back(i);cout 2.size: mylist.size() endl;while (!mylist.empty()){sum mylist.front();mylist.pop_front();}cout total: sum endl;return 0;
}list元素访问
函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用
int main()
{listint mylist;mylist.push_back(77);mylist.push_back(33);mylist.push_back(22);cout front: mylist.front() endl;cout back: mylist.back() endl;mylist.front() - 10;cout front: mylist.front() endl;mylist.back() 20;cout back: mylist.back() endl;return 0;
}list modifiers
函数声明接口说明push_front在list首元素前插入元素pop_front删除list中第一个元素push_back在list尾部插入元素pop_back删除list中最后一个元素insert在list的任意位置插入元素erase删除list任意位置的元素swap交换两个list中的元素clear清空list中的有效元素
int main()
{listint mylist(4, 0);listint::iterator it mylist.begin();cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;mylist.push_front(1);mylist.push_back(9);cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;mylist.pop_front();mylist.pop_back();cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;it mylist.begin();mylist.insert(it, 10);it;mylist.insert(it, 3, 5);cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;it mylist.begin();it;mylist.erase(it);cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;listint::iterator it1 mylist.begin();listint::iterator it2 mylist.begin();it1;advance(it2, 5); // 迭代器移动三位mylist.erase(it1, it2);cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;return 0;
}int main()
{listint mylist1(4, 1);listint mylist2(4, 2);cout mylist1:;for (listint::iterator it mylist1.begin(); it ! mylist1.end(); it)cout *it;cout endl;cout mylist2:;for (listint::iterator it mylist2.begin(); it ! mylist2.end(); it)cout *it;cout endl;mylist1.swap(mylist2);cout mylist1:;for (listint::iterator it mylist1.begin(); it ! mylist1.end(); it)cout *it;cout endl;cout mylist2:;for (listint::iterator it mylist2.begin(); it ! mylist2.end(); it)cout *it;cout endl;mylist1.clear();mylist1.push_back(9);mylist1.push_back(9);mylist1.push_back(9);cout mylist1:;for (listint::iterator it mylist1.begin(); it ! mylist1.end(); it)cout *it;cout endl;return 0;
}list的迭代器失效 迭代器失效即迭代器所指向的节点无效也就是对应节点被删除了。因为list的底层结构为带头节点的双向循环链表因为在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向删除节点的迭代器其他迭代器不会受到影响。
int main()
{listint mylist(4, 0);listint::iterator it mylist.begin();it mylist.begin();it;mylist.erase(it); // 这里it已经失效如要使用需重新赋值cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;listint::iterator it1 mylist.begin();listint::iterator it2 mylist.begin();it1;advance(it2, 5); // 迭代器移动三位mylist.erase(it1, it2);cout mylist:;for (it mylist.begin(); it ! mylist.end(); it)cout *it;cout endl;return 0;
}list与vector的对比
vectorlist底层结构动态顺序表一段连续的空间带头结点的双向循环链表随机访问支持随机访问访问某个元素的效率为O(1)不支持随机访问访问某个元素的效率为O(N)插入和删除任意位置插入和删除效率低需要移动元素O(N)插入时需要增容开辟新空间释放旧空间任意位置插入和删除效率高不需要移动元素空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低迭代器原生态指针对原生态指针节点指针进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容导致原来的迭代器失效删除时当前迭代器需要重新赋值否知会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使用场景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问
