跳转至

list类

约 2716 个字 634 行代码 5 张图片 预计阅读时间 17 分钟

list类介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list类定义

C++
1
template < class T, class Alloc = allocator<T> > class list;

list类为类模板，所以在使用时需要带上类型表示一个具体的类，例如数据类型为int类型的list使用时需要写为list<int>

list类常见构造

构造函数 函数原型
无参构造函数 explicit list ();
指定个数个类型值进行构造 explicit list (size_type n, const value_type& val = value_type())
使用类对象迭代器区间进行构造 template <class InputIterator>`` list (InputIterator first, InputIterator last);
拷贝构造函数 list (const list& x);

Note

上面表格中的前三个构造函数均含有自定义空间配置器并带有缺省值，目前只使用默认的空间配置器即可

Note

使用list类需要包含头文件<list>

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
#include <list>
using namespace std;

int main()
{
    //无参构造函数
    list<int> ls;
    cout << ls.size() << endl;

    return 0;
}
输出结果：
0

对于list类来说，因为是带头双向循环链表，所以不存在容量capacity，但是默认会有一个头节点，因为没有有效数据节点，所以当前头节点的头尾指针均指向自己

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls(10, 5);

    cout << ls.size() << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
10
5 5 5 5 5 5 5 5 5 5

//使用类对象迭代器区间进行构造
#include <iostream>
#include <list>
#include <vector>
using namespace std;

int main()
{
    list<int> ls(5, 10);
    list<int> ls1(ls.begin(), ls.end());

    for (auto num : ls)
    {
        cout << num << " ";
    }

    cout << endl;

    for (auto num : ls1)
    {
        cout << num << " ";
    }
    cout << endl;

    //也可使用其他类对象迭代器区间进行构造
    vector<int> v(5, 10);
    list<int> ls2(v.begin(), v.end());
    for (auto num : ls2)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10

//拷贝构造函数
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls(5, 10);
    list<int> ls1(ls);

    for (auto num : ls)
    {
        cout << num << " ";
    }

    cout << endl;

    for (auto num : ls1)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
10 10 10 10 10
10 10 10 10 10

list类的有效元素个数操作

函数 功能
size() 获取当前链表中的有效数据个数
max_size() 获取调用对象空间可以存储的有效数据最大个数

size()函数

使用size()函数可以获取到当前链表中的有效元素个数

Note

前面已经演示过使用方法，此处不再演示

list遍历操作

在list中，只有迭代器遍历的方式

迭代器 功能
begin()+end() begin获取第一个数据的迭代器 + end获取最后一个数据下一个位置的迭代器（默认包含const类型的迭代器，也可以使用cbegin()+cend()）
rbegin()+rend() rbegin获取最后一个数据的迭代器 + rend获取第一个数据上一个位置的迭代器（默认包含const类型的迭代器，也可以使用rcbegin()+rcend()）
cbegin()+cend() const类型的begin()和end()的迭代器，针对const对象
crbegin()+crend() const类型的rbegin()和rend()的迭代器，针对const对象

list元素修改操作

函数 功能
assign() 为调用对象空间重新分配内容为指定内容
push_front() 在第一个节点位置前插入一个新的数据节点
push_back() 在最后一个节点位置后插入一个新的数据节点
pop_front() 删除调用对象链表中的第一个有效数据节点
pop_back() 删除调用对象链表中的最后一个有效数据节点
insert() 在调用对象链表指定位置插入一个数据节点
erase() 删除调用对象链表指定位置的数据节点
swap() 交换两个链表对象中的内容
resize() 修改调用对象链表的有效数据节点个数
clear() 清空调用对象链表的有效数据节点

assign()函数

使用assign()函数可以为调用对象链表重新分配内容，如果原始链表中有数据，那么将覆盖原始内容

函数原型
template <class InputIterator> void assign (InputIterator first, InputIterator last);（使用指定对象的迭代器区间为调用对象重新分配内容）
void assign (size_type n, const value_type& val);（使用n个val值为调用对象重新分配内容）
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls(5, 10);
    list<int> ls1{ 1,2,3,4,5 };

    for (auto num : ls)
    {
        cout << num << " ";
    }
    ls.assign(ls1.begin(), ls1.end());
    cout << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
10 10 10 10 10
1 2 3 4 5

push_front()函数

使用push_front()函数可以在调用对象的第一个有效数据节点前插入一个新的有效数据节点

Note

如果调用对象链表当前没有有效数据节点，则实现效果与push_back()类似

函数 函数原型
push_front() void push_front (const value_type& val);
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_front(1);
    ls.push_front(2);
    ls.push_front(3);
    ls.push_front(4);

    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
4 3 2 1

push_back()函数

使用push_back()函数可以在调用对象的最后一个有效数据节点后插入一个新的有效数据节点

函数 函数原型
push_back() void push_back (const value_type& val);
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);

    for (auto num : ls)
    {
        cout << num << " ";
    }
    return 0;
}
输出结果：
1 2 3 4 5

pop_front()函数

使用pop_front()函数可以删除调用对象的第一个有效数据节点

Note

如果当前链表中没有有效数据节点，则函数将会断言报错

如果当前链表中只有一个有效数据节点，则函数实现效果与pop_back()类似

函数 函数原型
pop_front() void pop_front();
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls{ 1,2,3,4,5 };    
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    ls.pop_front();
    for (auto num : ls)
    {
        cout << num << " ";
    }
    return 0;
}
输出结果：
1 2 3 4 5
2 3 4 5

pop_back()函数

使用pop_front()函数可以删除调用对象的最后一个有效数据节点

Note

如果当前链表中没有有效数据节点，则函数将会断言报错

函数 函数原型
pop_back() void pop_back();
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);

    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    ls.pop_back();

    for (auto num : ls)
    {
        cout << num << " ";
    }
    return 0;
}
输出结果：
1 2 3 4 5
1 2 3 4

insert()函数

使用insert()函数可以在调用对象链表中的指定位置插入一个有效数据节点

函数原型
iterator insert (iterator position, const value_type& val);（在迭代器位置前插入数据val）
void insert (iterator position, size_type n, const value_type& val);（在迭代器位置前插入n个数据val）
template <class InputIterator>``void insert (iterator position, InputIterator first, InputIterator last);（在迭代器位置前插入指定对象迭代器区间中的数据）

Note

对于insert()函数来说，基本不存在迭代器失效问题，因为list不存在扩容问题并且空间基本不是连续的，所以position位置在插入数据后可能并没有改变

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);

    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;

    list<int>::iterator it =  find(ls.begin(), ls.end(), 2);
    ls.insert(it, 6);
    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
1 2 3 4 5
1 6 2 3 4 5

erase()函数

使用erase()函数可以删除调用对象链表指定位置的有效数据节点

函数原型
iterator erase (iterator position);（删除position位置的有效数据节点）
iterator erase (iterator first, iterator last);（删除迭代器区间中的有效数据节点）

Note

对于erase()函数来说，删除当前position位置节点会导致当前position位置失效，所以存在迭代器失效问题，针对这个问题，erase()函数提供返回值返回当前被删除节点的下一个节点的位置

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);

    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;

    list<int>::iterator it =  find(ls.begin(), ls.end(), 2);
    it = ls.erase(it);
    for (auto num : ls)
    {
        cout << num << " ";
    }

    cout << endl << *it << endl;

    return 0;
}
输出结果：
1 2 3 4 5
1 3 4 5
3

swap()函数

使用swap()函数可以交换调用对象和指定对象的链表

函数 函数原型
swap() void swap (list& x);
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls(10, 5);
    list<int> ls1(5, 10);
    cout << "交换前：" << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }    
    cout << endl;
    for (auto num : ls1)
    {
        cout << num << " ";
    }
    cout << endl;

    ls1.swap(ls);

    cout << "交换后：" << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    for (auto num : ls1)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
交换前：
5 5 5 5 5 5 5 5 5 5
10 10 10 10 10
交换后：
10 10 10 10 10
5 5 5 5 5 5 5 5 5 5

resize()函数

使用resize()函数可以修改调用对象链表中的有效数据节点的个数

函数 函数原型
resize() void resize (size_type n, value_type val = value_type());

Note

当n小于当前链表的size，则实现删除效果，否则初始化为指定类型的数据（默认为对应类型的默认值）

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);

    //只保留三个数据
    ls.resize(3);
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    //插入三个int类型数据并初始化为4
    ls.resize(6, 4);
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    //插入4个int类型数据默认初始化为0
    ls.resize(10);
    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
1 2 3
1 2 3 4 4 4
1 2 3 4 4 4 0 0 0 0

clear()函数

使用clear()函数可以清空调用对象链表当前所有的有效数据节点

Note

注意，当链表中没有有效数据节点时clear()函数不会有任何效果，并且使用clear()函数不会删除头节点

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);

    cout << "清空前：" << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;

    ls.clear();

    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << "清空后：" << endl;

    return 0;
}
输出结果：
清空前：
1 2 3 4 5
清空后：

清空有效数据节点不会删除头节点

list类数据操作

函数 功能
splice() 将指定对象中的数据转移到调用对象链表中的指定位置
sort() 为调用对象链表排序
unique() 去除调用对象中重复的有效数据节点
merge() 合并指定对象和调用对象的链表中的所有有效数据节点到调用对象链表中
reverse() 反转调用对象链表

splice()函数

使用splice()函数可以将指定对象中的内容拼接到调用对象的链表中的指定位置后

函数原型
void splice (iterator position, list& x);（将对象x中的所有内容拼接到调用对象position位置之前开始的位置）
void splice (iterator position, list& x, iterator i);（将对象x中的i位置的内容拼接到调用对象position位置之前开始的位置）
void splice (iterator position, list& x, iterator first, iterator last);（将对象x中指定区间的内容拼接到调用对象position位置之前开始的位置）

Note

使用splice()函数拼接后，指定对象的链表将不会存在被拼接至调用对象的有效数据节点

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls{ 1,2,3,4,5 };
    list<int> ls1(3, 6);

    cout << "拼接前：" << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }

    cout << endl;

    for (auto num : ls1)
    {
        cout << num << " ";
    }

    cout << endl;
    list<int>::iterator it = find(ls.begin(), ls.end(), 2);
    ls.splice(it, ls1);
    cout << "拼接后：" << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }

    cout << endl;

    for (auto num : ls1)
    {
        cout << num << " ";
    }

    cout << endl;
    return 0;
}
输出结果：
拼接前：
1 2 3 4 5
6 6 6
拼接后：
1 6 6 6 2 3 4 5

Note

注意，splice()函数中的迭代器为双向迭代器(bidirectional iterator)，传递的迭代器也必须为双向迭代器或者单向迭代器(forward iterator)，不可以随机迭代器(random iterator)

随机访问迭代器是特殊的双向迭代器，双向迭代器和随机访问迭代器是特殊的单向迭代器

随机访问迭代器支持以下操作：

双向迭代器支持以下操作：

单向迭代器支持以下操作：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <list>
#include <vector>
using namespace std;

int main()
{
    list<int> ls{ 1,2,3,4,5 };
    vector<int> v1(3, 6);

    cout << "拼接前：" << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }

    cout << endl;

    for (auto num : v1)
    {
        cout << num << " ";
    }

    cout << endl;
    list<int>::iterator it = find(ls.begin(), ls.end(), 2);
    ls.splice(it, v1);
    cout << "拼接后：" << endl;
    for (auto num : ls)
    {
        cout << num << " ";
    }

    cout << endl;

    for (auto num : v1)
    {
        cout << num << " ";
    }

    cout << endl;
    return 0;
}
报错信息：
“std::list<int,std::allocator<int>>::splice”: 没有重载函数可以转换所有参数类型

因为vector的迭代器为随机访问迭代器，所以当传入双向迭代器时会报错

sort()函数

使用sort()函数可以为调用对象的链表进行排序，底层是归并排序

Note

默认是升序排序，可以通过仿函数改变为降序

函数原型
void sort();
template <class Compare>``void sort (Compare comp);

Note

不同于算法库中sort()函数，因为算法库中的sort()函数为随机访问迭代器，双向迭代器不再适用

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <list>
using namespace std;

int main()
{
    //升序
    list<int> ls{ 2,34,53,9,12,66,32 };
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    ls.sort();
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    //降序
    ls.sort(greater<int>());
    for (auto num : ls)
    {
        cout << num << " ";
    }
    return 0;
}
输出结果：
2 34 53 9 12 66 32
2 9 12 32 34 53 66
66 53 34 32 12 9 2

在实际使用中，如果数据量比较大时，list排序会比可以随机访问的vector类排序慢，所以一般可以考虑将list类的数据拷贝到vector类中排序，排完序后再拷贝会list中，这段过程中虽然涉及到拷贝数据的消耗，但是总体时间消耗比单独使用list中sort()函数小

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
#include <list>
#include <ctime>
#include <algorithm>
using namespace std;

int main()
{
    srand(time(NULL));
    const int N = 10000000;//一千万个数据

    list<int> ls;
    list<int> ls1;

    //向两个链表中插入数据
    for (int i = 0; i < N; ++i)
    {
        auto e = rand();
        ls.push_back(e);
        ls1.push_back(e);
    }

    //直接使用sort()排序
    size_t begin = clock();
    ls.sort();
    size_t end = clock();

    //拷贝到vector类中排序
    size_t begin1 = clock();
    vector<int> v(ls1.begin(), ls1.end());
    sort(v.begin(), v.end());
    ls1.assign(v.begin(), v.end());
    size_t end1 = clock();

    cout << "直接排序：" << end - begin << "ms" << endl;
    cout << "拷贝后排序再拷贝：" << end1 - begin1 << "ms" << endl;

    return 0;
}
输出结果：
直接排序：14069ms
拷贝后排序再拷贝：4257ms

unique()函数

使用unique()函数可以为调用对象链表去除重复数据的有效数据节点

函数 函数原型
unique() void unique();

Note

使用unique()函数之前必须确保链表有序

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls{ 1,2,2,1,3,2,4,5,6,6 };
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    //先进行排序
    ls.sort();
    ls.unique();
    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
1 2 2 1 3 2 4 5 6 6
1 2 3 4 5 6

merge()函数

使用merge()函数可以将调用对象和指定对象的链表进行合并

函数 函数原型
merge() void merge (list& x);

Note

默认按照从小到大进行合并，也可通过仿函数更改为降序

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls{ 1,2,9,5,4 };
    list<int> ls1{ 3,2,4,8,1 };
    ls.sort();
    ls1.sort();

    ls.merge(ls1);
    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
1 1 2 2 3 4 4 5 8 9

reverse()函数

使用reverse()函数可以逆置调用对象链表

函数 函数原型
reverse() void reverse();
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ls{ 1,2,4,5,9 };
    for (auto num : ls)
    {
        cout << num << " ";
    }
    cout << endl;
    ls.reverse();
    for (auto num : ls)
    {
        cout << num << " ";
    }

    return 0;
}
输出结果：
1 2 4 5 9
9 5 4 2 1