list

list容器介绍

链表(list)是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针连接实现的

链表的组成:链表有一系列结点组成

结点的组成:一个是存储数据元素的数据域,另一个是存储下一个节点地址的指针域

优点:

• 快速插入删除
• 执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
• 采用动态存储分配，不会造成内存浪费溢出
• 不会造成原有的迭代器失效，这在vector不成立

缺点:

• 遍历速度没有数组快,占用更多空间
• 空间,时间消耗比较大

STL中的链表是一个双向(一个结点有指向前结点的指针指向后结点指针)循环(前连后)链表

Note

list图解

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

10

20

30

0x01

0x02

0x03

0x02

0x03

…

数据域

指针域

结点

指向原始笔记的链接

list和vector是stl最常用的两容器

list构造函数

• list<T>ls; //默认构造
• list(beg, end); //迭代器构造
• list(n, elem); //重复元素构造
• list(const list& ls); //拷贝构造

list赋值交换

• list& operator=(const list& ls); //拷贝赋值
• assign(beg, end); //拷贝赋值
• assign(n, elem); //重复元素赋值
• swap(ls);

list容量大小

• size(); 元素量
• empty(); 是否为空
• resize(int num); 重新指定大小，如果是扩容，多余的元素用默认值填充，如果是变短，则删除多余元素
• resize(int num, elem); 如果是扩容，多余的元素用elem填充，如果是变短，则删除多余元素

list插入删除操作

• push_back(elem); //尾部插入元素
• pop_back(); //删除最后的元素
• push_front(elem); //开头插入元素
• pop_front(); //移除开头元素
• int insert(const_iterator pos, ele); //ele从pos位置插入(从0开始)，返回新的数据位置
• insert(iterator pos, int count, ele); //ele从pos位置插入count次(从0开始)
• insert(const_iterator pos, const_iterator beg, const_iterator end); //在pos位置插入[beg, end)区间的数据
• erase(iterator pos); //删除pos位元素(从0开始)o
• erase(iterator start, iterator end); //删除pos位元素[beg, end)
• clear(); //全清
• remove(elem); //删除与elem值匹配的元素

list数据存取

• front(); //获取首位元素
• back(); //获取末位元素

list反转和排序

• reverse();
• sort();

待补充 下一节 set