forward list单链表

特点

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

#include <forward_list>

forward list单链表类似一个行为受限的list双向链表，优点是内存用量较少，行动较快

相比list：

1.forward list 只提供向前迭代器，不支持反向迭代

2.forward list 没有指向尾元素的指针，不提供处理尾部元素的函数，如back()，push_back()，pop_back()

3.forward list 不提供size()函数，需要自行实现

4.forward list 是单链表，插入和删除操作依赖前一个节点，因此它的插入、删除类函数都带有后缀 _after，例如用insert_after()替代insert()

5.forward list 提供了before_begin()函数，返回第一个元素前面的位置。

6.forward list 不提供随机访问，要访问第n个元素，需要从头部依次遍历过去

定义与初始化

初始化	含义
forward_list<T> l1	l1 是一个存放 T 类型数据的空链表
forward_list<T> l2(l1)	利用 l1 构造 l2，l2 包含 l1 的所有数据
forward_list<T> l2 = l1	同上
forward_list<T> l3(n,val)	l3 包含 n 个 val
forward_list<T> l4(n)	l4 包含 n 个默认 T 类型的数据
forward_list<T> l5{a,b,c,...}	l5 包含初始化列表提供的数据
forward_list<T> l5 = {a,b,c,...}	同上
forward_list<T> l6(Iterator First, Iterator Last)	通过两个迭代器创建链表

template<typename T>
void Show(const T& v)
{
    for (const auto& x : v)
        cout << x << " ";
    cout << endl;
}

int main()
{
    forward_list<int> l1; // 创建一个空的单链表
    forward_list<int> l2(2); // 创建一个包含2个默认值的单链表
    forward_list<int> l3(3, 5); // 创建一个包含3个5的单链表
    forward_list<int> l4{ 1,2,3,4 }; // 创建一个包含1,2,3,4的单链表
    forward_list<int> l5(l4); // 创建一个和l4元素相同的单链表
    forward_list<int> l6 = l4; // 同l5，创建一个和l4元素相同的单链表
    forward_list<int> l7(++l4.begin(), l4.end()); // 创建一个不包含l4第一个元素的单链表

    cout << "l1:"; Show(l1);
    cout << "l2:"; Show(l2);
    cout << "l3:"; Show(l3);
    cout << "l4:"; Show(l4);
    cout << "l5:"; Show(l5);
    cout << "l6:"; Show(l6);
    cout << "l7:"; Show(l7);

    return 0;
}

forward list 常用迭代器

forward list 只支持向前迭代器，不支持逆序迭代器和随机迭代器

迭代器	含义
l.begin()	第一个元素的迭代器
l.end()	最后一个元素的下一个位置迭代器
l.cbegin()	第一个元素的常量迭代器
l.cend()	尾后常量迭代器

forward list 常用运算符

运算符	含义
l2 = l1	把 l1 的数据赋值给 l2
l1 == l2	判断是否相等
l1 != l2	判断是否不相等
<, <=, >, >=	判断大小关系，从头到尾依次比较
不支持[]

int main() {
    forward_list<int> l1{ 1, 2, 3, 4, 5 };
    forward_list<int> l2;

    l2 = l1;
    cout << "l1:"; Show(l1);
    cout << "l2:"; Show(l2);

    if (l1 == l2)
        cout << "l1 == l2" << endl;

    l1.front() = 100;
    cout << "l1:"; Show(l1);
    cout << "l2:"; Show(l2);

    if (l1 != l2)
        cout << "l1 != l2" << endl;

    if (l1 > l2)
        cout << "l1 > l2" << endl;
    else
        cout << "l1 <= l2" << endl;

    return 0;
}

forward list 常用成员函数

成员函数	含义
l.empty()	判断是否为空
l.front()	返回第一个元素的引用
l.push_front()	头插
l.pop_front()	头删
l.insert_after()	插入一个或多个元素
l.erase_after()	删除一个或多个元素
l.swap()	交换两个链表的值
l.clear()	清空数据

empty成员函数

判断对象是否为空

int main()
{
    forward_list<int> l1;
    if (l1.empty())
        cout << "l1是空的单链表";
    return 0;
}

front成员函数

获取第一个元素的引用

push_front成员函数

从头部插入数据

pop_front成员函数

从头部删除数据

int main()
{
    forward_list<int> l1;

    for (int i = 0; i < 5; i++)
        l1.push_front(i);//头插

    while (!l1.empty())
    {
        cout << l1.front() << " ";
        l1.pop_front(); // 删除第一个数据
    }

    return 0;
}

insert_after成员函数

在指定位置后面插入一个或多个元素

int main() {
    forward_list<int> l1{ 1,2,3,4,5 };
    forward_list<int>::iterator it = l1.begin();
    it++; // 移动到第二个元素

    // 插入一个值
    l1.insert_after(it, 10);
    cout << "l1:"; Show(l1);

    // 插入多个值（一个列表）
    l1.insert_after(it, { 100,200,300 });
    cout << "l1:"; Show(l1);

    // 插入多个值（一个迭代器区间）
    forward_list<int> l2{ 50,60,70 };
    l1.insert_after(l1.before_begin(), l2.begin(), l2.end());
    cout << "l1:"; Show(l1);

    return 0;
}

erase_after成员函数

删除迭代器后面一个或多个元素

int main() {
    forward_list<int> l1{ 1,2,3,4,5,6,7,8,9,10 };
    cout << "l1:"; Show(l1);

    // 删除一个值
    l1.erase_after(l1.begin());
    cout << "l1:"; Show(l1);

    // 删除迭代器区间的值（多个值）
    l1.erase_after(l1.before_begin(), l1.end());
    cout << "l1:"; Show(l1);

    return 0;
}

forward list 特有成员函数

成员函数	含义
l.merge()	链表合并
l.remove(val)	删除所有和val相同的元素
l.remove_if()	删除符合条件的元素
l.reverse()	反转链表中的元素
l.sort()	排序（默认为升序）
l.splice_after()	链表连结
l.unique()	删除重复元素

merge成员函数

把两个链表的元素进行合并。

合并的前提：是原本两个链表必须按照合并的方法有序。

默认升序合并。

int main() {
    forward_list<int> l1{ 2,4,6,8 };
    forward_list<int> l2{ 1,2,3,5,7,9 };
    cout << "l1:"; Show(l1);
    cout << "l2:"; Show(l2);

    l1.merge(l2); // 把l2合并到l1中
    cout << "把l2合并到l1中后" << endl;
    cout << "l1:"; Show(l1);
    cout << "l2:"; Show(l2);

    return 0;
}

remove成员函数

删除所有和_vel相同的值

int main() {
    forward_list<char> l1{ 'a','b','c','a','b','c','d','a','b','c','d','e' };
    cout << "l1:"; Show(l1);

    l1.remove('a'); // 删除'a'
    cout << "l1删除a后" << endl;
    cout << "l1:"; Show(l1);

    return 0;
}

remove_if成员函数

删除符合条件的元素

class vowel {
public:
    bool operator() (char c)
    {
        string s = "aoeiu"; // 5个元音字母
        return s.find(c) != string::npos;
    }
}; // 元音字母函数对象

int main() {
    forward_list<char> l1{ 'a','b','c','a','b','c','d','a','b','c','d','e' };
    cout << "l1:"; Show(l1);

    l1.remove_if(vowel()); // 删除使vowel()函数为true的字符
    cout << "l1删除元音字母后" << endl;
    cout << "l1:"; Show(l1);

    return 0;
}

reserse成员函数

将所有元素反序

int main() {
    forward_list<int> l1{1,2,3,4,5,6,7};
    cout << "l1:"; Show(l1);

    l1.reverse();
    cout << "数据反序后" << endl;
    cout << "l1:"; Show(l1);

    return 0;
}

sort成员函数

默认升序排序，可以提供排序依据

int main() {
    forward_list<int> l1{ 1,2,3,4,5,6,7 };
    cout << "l1:"; Show(l1);

    l1.reverse();
    cout << "数据反序后" << endl;
    cout << "l1:"; Show(l1);

    return 0;
}

unique成员函数

删除相邻且重复的值，只保留一个

重复的值如果不相邻，不会删除

int main() {
    forward_list <int> l1{ 8, 2, 4, 1, 10, 3, 7, 9, 5, 6 };

    cout << "原始数据， l1:"; Show(l1);

    l1.sort();
    cout << "默认排序后，";
    cout << "l1:"; Show(l1);

    l1.sort(greater<int>()); // 降序
    cout << "降序排序后，";
    cout << "l1:"; Show(l1);

    return 0;
}