专栏首页Visual CodexSTL学习笔记(8)常用容器 list

STL学习笔记(8)常用容器 list

list 容器基本概念

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相较于 vector 的连续线性空间,list 就显得负责许多,它的好处是每次插入或者删除一个元素,就是配置或者释放一个元素的空间。因此,list 对于空间的运用有绝对的精准,一点也不浪费。而且,对于任何位置的元素插入或元素的移除,list 永远是常数时间。

list 和 vector 是两个最常被使用的容器。

  • list 容器是一个双向链表。
  • 采用动态存储分配,不会造成内存浪费和溢出。
  • 链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素。
  • 链表灵活,但是空间和时间额外耗费较大

list 容器的迭代器

List 容器不能像 vector 一样以普通指针作为迭代器,因为其节点不能保证在同一块连续的内存空间上。list 迭代器必须有能力指向 list 的节点,并有能力进行正确的递增、递减、取值、成员存取操作。所谓“list 正确的递增,递减、 取值、成员取用”是指:递增时指向下一个节点,递减时指向上一个节点,取值时取的是节点的数据值,成员取用时取的是节点的成员。 由于 list 是一个双向链表,迭代器必须能够具备前移、后移的能力,所以 list 容器提供的是 Bidirectional Iterators. List 有一个重要的性质,插入操作和删除操作都不会造成原有 list 迭代器的失效。这在 vector 是不成立的,因为 vector 的插入操作可能造成记忆体重新配置,导致原有的迭代器全部失效,甚至 List 元素的删除,也只有被删除的那个元素的迭代器失效,其他迭代器不受任何影响。

list 常用操作

1. list 构造函数
list<T> lstT;//list 采用采用模板类实现,对象的默认构造形式: 
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。 
list(n,elem);//构造函数将 n 个 elem 拷贝给本身。 
list(const list &lst);//拷贝构造函数。
2. list 数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素 
pop_back();//删除容器中最后一个元素 
push_front(elem);//在容器开头插入一个元素 
pop_front();//从容器开头移除第一个元素 
insert(pos,elem);//在 pos 位置插 elem 元素的拷贝,返回新数据的位置。 
insert(pos,n,elem);//在 pos 位置插入 n 个 elem 数据,无返回值。 
insert(pos,beg,end);//在 pos 位置插入[beg,end)区间的数据,无返回值。 
clear();//移除容器的所有数据 
erase(beg,end);//删除[beg,end)区间的数据,返回下一个数据的位置。 
erase(pos);//删除 pos 位置的数据,返回下一个数据的位置。 
remove(elem);//删除容器中所有与 elem 值匹配的元素。
3. list 大小操作
size();//返回容器中元素的个数 
empty();//判断容器是否为空 
resize(num);//重新指定容器的长度为 num, 若容器变长,则以默认值填充新位置。 如果容器变短,则末尾超出容器长度的元素被删除。 
resize(num, elem);//重新指定容器的长度为 num, 若容器变长,则以 elem 值填充新位置。 如果容器变短,则末尾超出容器长度的元素被删除。 
4. list 赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。 
assign(n, elem);//将 n 个 elem 拷贝赋值给本身。 
list& operator=(const list &lst);//重载等号操作符 
swap(lst);//将 lst 与本身的元素互换。 
5. list 数据的存取
front();//返回第一个元素。 
back();//返回最后一个元素。 
6. list 反转排序
reverse();//反转链表,比如 lst 包含 1,3,5 元素,运行此方法后,lst 就包含 5,3,1 元素。 
sort(); //list 排序

参考《千锋教育》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++中STL学习笔记——容器之list

    C++中的容器大致分为两类:顺序容器和关联容器。以后会逐一讲解。本文主要讲解顺序容器中的list。

    啤酒单恋小龙虾
  • STL学习笔记(6)常用容器 stack

    stack 是一种先进后出(First In Last Out, FILO)的数据结构,它只有一个出口,形式如图所示。stack 容器允许新增元素, 移除元素,...

    轻舞飞扬SR
  • STL学习笔记(5)常用容器 deque

    Vector 容器是单向开口的连续内存空间,deque 则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,v...

    轻舞飞扬SR
  • STL学习笔记(10)常用容器 pair

    对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用 pair 的两个公有属性 first 和 second 访问。

    轻舞飞扬SR
  • STL学习笔记(9)常用容器 set/multiset

    Set 的特性是:所有元素都会根据元素的键值自动被排序。Set 的元素不像 map 那样可以同时拥有实值和键值,set 的元素即是键值又是实值。Set 不允许两...

    轻舞飞扬SR
  • STL学习笔记(7)常用容器 queue

    Queue 是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口,queue 容器允许从一端新增元素,从另 一端移除元素。 ...

    轻舞飞扬SR
  • STL学习笔记(11)常用容器 map/multimap

    Map 的特性是,所有元素都会根据元素的键值自动排序。Map 所有的元素都是 pair,同时拥有实值和键值,pair 的 第一元素被视为键值,第二元素被视为实值...

    轻舞飞扬SR
  • STL学习笔记(4)常用容器 vector

    vector 的数据安排以及操作方式,与 array 非常相似,两者的唯一差别在于空间的运用的灵活性。Array 是静态空间, 一旦配置了就不能改变,要换大一点...

    轻舞飞扬SR
  • STL学习笔记(3)常用容器 string

    C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握,不适合大程序的开发,所以C++标准库定义了一种string 类,定义在头文件。

    轻舞飞扬SR

扫码关注云+社区

领取腾讯云代金券