基本概念
list
- 底层数据结构为双向链表，支持快速增删
- 缺点是无法通过位置来直接访问序列中的元素，也就是说，不能索引元素。为了访问 list 内部的一个元素，必须一个一个地遍历元素，通常从第一个元素或最后一个元素开始遍历。
- 节点对象维护了两个指针，一个指向前一个节点，另一个指向下一个节点。
- 第一个元素的前向指针总是为 null,因为它前面没有元素，尾部元素的后向指针也总为 null。
头文件
模板
1
| template < class T, class Alloc = allocator<T> > class list;
|
list初始化方法
1
2
3
4
5
| list<int>q;
list<int>p(5); 创建拥有5个成员的List
list<int>s(5,1); 创建拥有5个成员，且初始值为1的List
list<int>s2(s); 创建s2，并拷贝s元素给s2
list<int>s3(s.begin(),s.end()); 创建s3，拷贝s.begin()至s.end()中元素给s3
|
交换
swap(list<T>& other)：和参数的元素进行交换，所包含对象的类型必须相同。：将当前 map 中的元素和参数 map 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。
1
2
3
| void swap(list<T> &x) 重载1：x.swap(y)
void swap (list<T>& x, list<T>& y) 重载2: swap(x, y)
q.swap(p)
|
常用操作
插入
1
2
3
4
5
| q.push_front(num) 返回值空 在list的头部添加一个元素
q.push_back(num) 返回值空 在list末尾增加一个元素。
q.insert(iter,num) 在iter位置插入元素num。
q.insert(iter,n,num) 在iter位置插入n个元素num。
q.insert(iter,beg,end) 在iter位置插入区间为[beg,end)的元素。
|
大小与是否为空
1
2
3
4
5
| q.empty() 如果list是空的则返回true
q.max_size() 返回list能容纳的最大元素数量
q.size() 返回list中的元素个数
q.resize(n) 从新定义链表的长度,超出原始长度部分用0代替,小于原始部分删除。
q.resize(n,num)从新定义链表的长度,超出原始长度部分用num代替。
|
删除与清空
1
2
3
4
5
6
| q.clear() 返回值空，删除所有元素
q.pop_back() 返回值空 删除最后一个元素
q.pop_front() 返回值空 删除第一个元素
q.erase(iter) 删除一个元素，并且返回下一个位置的迭代器
q.remove(value) 从list删除元素 void remove ( const T& value );
q.remove_if(MATCH) 按指定条件删除元素 返回值为空void list::remove_if( MATCH )
|
1
2
| iterator erase ( iterator position );
iterator erase ( iterator first, iterator last );
|
list中remove和erase都是删除一个元素，其中remove参数类型和数据类型一致，而erase参数类型是迭代器。
remove（aim）是删除链表中的aim元素，若有多个aim，都会删除，而
erase（it）是删除迭代器指定位置的元素，并且返回下一个位置的迭代器来看例子。
查找
1
2
| q.back() 返回最后一个元素 reference back ( );
q.front() 返回第一个元素 reference front ( );
|
迭代器
1
2
3
4
| q.begin()
q.end()
q.rbegin()
q.rend()
|
查找迭代器
反转list
1
| q.reverse() //把list的元素倒转 void reverse ( );
|
合并两个list
STL list容器由于采用了双向迭代器，不支持随机访问，所以标准库的merge(), sort()等功能函数都不适用，list单独实现了merge()，sort()等函数。
splice与merge
- 最大的不同:不用排序，也不要求原始链表有序。
- 相同点:被合并的链表或元素将消失。
1
2
3
| q.merge(p); 合并2个有序的链表并使之有序,从新放到q中,释放p。
q.merge(p,comp); 合并2个有序的链表并使之按照自定义规则排序之后从新放到q中,释放p。
q.splice() //合并两个list
|
1
2
| list1.merge(list2)
在使用merge前，必须使list1和list2已经排好顺序。并且，合并之后list1仍然是有序的
|
splice是剪切，粘贴。用splice时当B与A合并后，B就为空。但是要记住：迭代器仍然指向原来的位置，即使原来的元素不存在了。
1
2
3
4
5
6
7
8
| 将list2中的所有元素拷贝到list1中。在list1中的起始位置是it1.复制结束后，list2将为空。
list1.splice(it1, list2);
将list2中的元素，从it2开始，剪切到list1的it1起始的地方。
list1.splice(it1, list2, it2);
将链表list2从开始到结束都合并到it1开始的位置。
list1.splice(it1, list2, it2begin, it2end);
|
排序sort()
一个自定义的类，那么如果想为这个类所生成的对象排序的话，因为list.sort()默认排序需要重载 < 操作符。所以我们必须在类对象里重载这个操作符
删除list中重复的元素unique()
1
| q.unique() 删除list中重复的元素 返回值为空
|
输出
1
| copy(q.begin(),q.end(),ostream_iterator<int>(cout,""));
|
参考资料
STL 如何使用list::remove_if
容器链表中splice()、merge()、insert()方法的区别
c++ list 合并list
STL 中list的sort()方法使用总结(运算符重载)
C++ list.merge()使用方法
stl list中erase和remove区别
std::list::sort()排序分析
C++ list(STL list)使用、创建和初始化
C++标准库容器类概述
本文许可证
本文遵循 CC BY-NC-SA 4.0（署名 - 非商业性使用 - 相同方式共享） 协议，转载请注明出处，不得用于商业目的。
