沈阳做网站哪家便宜,wordpress智能插件,wordpress连阿里云域名,设计培训网页版1.概述 1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代 2. list 的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向其前一个元素和后一个元素 3. list…1.概述 1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代 2. list 的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素 3. list 与 forward_list 非常相似最主要的不同在于 forward_list 是单链表只能朝前迭代已让其更简单高效 4. 与其他的序列式容器相比 (array vector deque) list 通常在任意位置进行插入、移除元素的执行效率更好 5. 与其他序列式容器相比 list 和 forward_list 最大的缺陷是不支持任意位置的随机访问 list 还需要一些额外的空间以保存每个节点的相关联信息 2.成员函数
2.1 构造函数 list (size_type n, const value_type val value_type()) 构造的 list 中包含 n 个值为 val 的元素 list() 构造空的 list list (const list x) 拷贝构造函数 list (InputIterator first, InputIterator last) 用 [first, last) 区间中的元素构造 list
2.2 iterator 的使用 begin end 返回第一个元素的迭代器 返回最后一个元素下一个位置的迭代器 rbegin rend 返回第一个元素的 reverse_iterator, 即 end 位置 返回最后一个元素下一个位置的 reverse_iterator, 即 begin 位置 反向迭代器的 就是正向迭代器的 -- 反向迭代器的 -- 就是正向迭代器的 因此反向迭代器的实现可以借助正向迭代器即反向迭代器内部可以包含一个正向迭代器对正向迭代器的接口进行 包装即可 1. begin 与 end 为正向迭代器对迭代器执行 操作迭代器向后移动 2. rbegin(end) 与 rend(begin) 为反向迭代器对迭代器执行 操作迭代器向前移动 2.3 list capacity empty 检测 list 是否为空是返回 true 否则返回 false size 返回 list 中有效节点的个数
2.4 list element access front 返回 list 的第一个节点中值的引用 back 返回 list 的最后一个节点中值的引用
2.5 list modifiers push_front 在 list 首元素前插入值为 val 的元素 pop_front 删除list中第一个元素 push_back 在 list 尾部插入值为 val 的元素 pop_back 删除 list 中最后一个元素 insert 在 list position 位置中插入值为 val 的元素 erase 删除 list position 位置的元素 swap 交换两个 list 中的元素 clear 清空 list 中的有效元素 2.6 list的迭代器失效 迭代器暂时理解成类似于指针 迭代器失效即迭代器所指向的节点的无效即该节 点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 因此 在 list 的插入是不会导致 list 的迭代 器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响 3.list和vector的比较 vector list 底 层 结 构 动态顺序表一段连续空间 带头结点的双向循环链表 随 机 访 问 支持随机访问访问某个元素效率 O(1) 不支持随机访问访问某个元素 效率 O(N) 插 入 和 删 除 任意位置插入和删除效率低需要搬移元素时间复杂 度为 O(N) 插入时有可能需要增容增容开辟新空 间拷贝元素释放旧空间导致效率更低 任意位置插入和删除效率高不 需要搬移元素时间复杂度为 O(1) 空 间 利 用 率 底层为连续空间不容易造成内存碎片空间利用率 高缓存利用率高 底层节点动态开辟小节点容易 造成内存碎片空间利用率低 缓存利用率低 迭 代 器 原生态指针 对原生态指针 ( 节点指针 ) 进行封装 迭 代 器 失 效 在插入元素时要给所有的迭代器重新赋值因为插入 元素有可能会导致重新扩容致使原来迭代器失效删 除时当前迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效 删除元素时只会导致当前迭代 器失效其他迭代器不受影响 使 用 场 景 需要高效存储支持随机访问不关心插入删除效率 大量插入和删除操作不关心随 机访问
