STL forward_list 单向链表

什么是链表？
链表是由一些列节点组成的，每一个阶段包含数据域、指针域，每个节点的内存都是独立，使用的是非连续的内存。链表分为：单向链表、双向链表、循环链表
单向链表的开销最低，空间只需要一个指针即可，从操作角度：单向链表添加或者删除元素时候只需要维护一个指针，而双向链表需要维护两个。

链表优缺点
链表优点是：添加或者删除链表中的元素，不需要移动其他的元素。
链表缺点是：不支持下标，根据位置查找元素的话效率低。

链表的迭代器
链表添加和删除元素都不会导致空间重新配置，所以，指向原来数据的迭代器不会因为添加或者删除元素而失效。除非删除的是迭代器指向的元素。

forward_list 属于单向链表，不支持反向遍历的。没有 reverse 迭代器。

下面示例代码主要从以下几个方面来讲解 forward_list 容器：

创建和大小
添加元素
删除元素
拼接元素
排序操作
内建函数对象
合并有序链表

// 1. 创建和大小
void test01()
{
	// forward list 叫做前向的单向链表
	forward_list<int> fl = { 10, 20, 30, 40 };
	cout << fl.max_size() << endl;
	// forward_list 不提供 size 函数
	// 为什么 forward_list 不提供 size 函数？
	// 认为 size 函数会影响效率。
	// 1. 类内部维护一个变量 size, 每次添加和删除元素的时候都需要维护该变量。
	// 2. 类内部不维护用于记录大小的变量，每次调用 size 函数时，从头到尾数一遍即可。

	// 如果我要想知道链表中元素的个数，应该怎么办？
	// 1. 自己遍历下链表，数一数节点的个数。
	// 2. distance 函数计算下链表中元素的个数
	cout << distance(fl.begin(), fl.end()) << endl;
}

// 2. 添加元素
class Person
{
public:
	Person(string name, int age)
	{
		m_name = name;
		m_age = age;
	}

	bool operator<(const Person& person) const
	{
		return m_age < person.m_age;
	}

public:
	string m_name;
	int m_age;
};

void test02()
{
	forward_list<Person> fp;

	// insert_after(位置，元素) 在指定位置的后面添加一个元素
	// begin 返回的是第一个元素的位置
	// before_begin 返回的是第一个元素前面的位置（虚拟位置）
	fp.insert_after(fp.before_begin(), Person("Smith", 20));

	// push_front， 没有 push_back， 在链表头部添加元素
	fp.push_front(Person("Polly", 30));

	// emplace_front  在链表的头部添加元素
	// emplace_front 使用传递的参数构建一个 Person 对象，然后存储到指定位置。
	fp.emplace_front("Obama", 40);

	// emplace_after  在指定的位置后面添加元素
	fp.emplace_after(fp.begin(), "Edward", 50);


	for (forward_list<Person>::iterator it = fp.begin(); it != fp.end(); ++it)
	{
		cout << it->m_name << " " << it->m_age << endl;
	}
}


// 3. 删除元素
void test03()
{
	forward_list<int> fl = { 10, 20, 30, 30, 40, 50 };
	// erase_after 删除某个位置之后的元素
	// 删除指定位置后面的元素
	// fl.erase_after(fl.begin());
	// fl.pop_front();
	// fl.erase_after(fl.before_begin());

	// 删除指定区间的元素，第一个位置不包括
	// fl.erase_after(fl.before_begin(), fl.end());

	// 按值删除 : 删除容器中所有该值的元素。
	// fl.remove(30);
	// 删除满足某些条件的元素，条件是包含一个参数的，返回值为布尔类型的普通函数、函数对象、匿名函数对象。
	// fl.remove_if([](int val) { return val >= 30; });

	// 删除所有的元素
	fl.clear();

	for (forward_list<int>::iterator it = fl.begin(); it != fl.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

}

// 4. 拼接元素
void test04()
{
	// 拼接：将一个链表元素添加到另外一个链表中
	forward_list<int> f1 = { 10, 20, 30 };
	forward_list<int> f2 = { 100, 200, 300 };

	// 在指定位置的后面拼接新的数据
	// f1.splice_after(f1.begin(), f2);
	// f1.splice_after(f1.before_begin(), f2);

	// splice_after 将 f2 中指定位置后面的元素添加到 f1 中
	// f1.splice_after(f1.before_begin(), f2, f2.before_begin());

	// 区间不包含两侧元素的。也就是将指定区间之间的所有元素拼接到 f1 指定位置的后面
	f1.splice_after(f1.before_begin(), f2, f2.begin(), f2.end());

	for (forward_list<int>::iterator it = f1.begin(); it != f1.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}


// 5. 排序操作
void test05()
{
	forward_list<int> f = { 80, 50, 40, 70, 60, 20, 30 };
	// 使用 sort 函数排序
	// 默认进行升序排列。
	// 要使用 sort 排序，存储的元素必须支持 operator< 比较。
	// f.sort();

	// 指定降序排序（从大到小）
	// f.sort([](int v1, int v2) { return v1 > v2; });
	f.sort(greater<int>());

	for (forward_list<int>::iterator it = f.begin(); it != f.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test06()
{
	forward_list<Person> f = { Person("aaa", 60), Person("aaa", 20) , Person("aaa", 70), Person("aaa", 50) };
	// 升序排列
	// f.sort();
	// 降序排列
	f.sort([](Person &v1, Person &v2) { return v1.m_age > v2.m_age; });

	for (forward_list<Person>::iterator it = f.begin(); it != f.end(); ++it)
	{
		cout << it->m_name << " " << it->m_age << endl;
	}
}

// 6. 内建函数对象
// C++ 标准库提供了很多常用的函数对象，算术运算类、比较运算类、逻辑运算类

void test07()
{
	// 算术运算类
	cout << plus<int>()(10, 20) << endl;
	cout << minus<int>()(10, 20) << endl;
	cout << divides<int>()(10, 20) << endl;
	cout << multiplies<int>()(10, 20) << endl;

	// 比较运算类
	cout << less<int>()(10, 20) << endl;
	cout << less_equal<int>()(10, 20) << endl;
	cout << equal_to<int>()(10, 20) << endl;
	cout << not_equal_to<int>()(10, 20) << endl;
	cout << greater<int>()(10, 20) << endl;
	cout << greater_equal<int>()(10, 20) << endl;

	// 逻辑运算类
	cout << logical_and<int>()(10 > 20, 20 > 30) << endl;
	cout << logical_or<int>()(10 > 20, 20 > 30) << endl;
	cout << logical_not<int>()(10 > 20) << endl;
}

// 7. 合并有序链表
void test08()
{
	forward_list<int> f1 = { 80, 50, 40, 70, 60, 20, 30 };
	forward_list<int> f2 = { 30, 40, 20, 90 };

	f1.sort(greater<int>());
	f2.sort(greater<int>());
	// 合并两个有序链表，最终合并的结果依然保持有序
	// 如果合并的两个有序序列并不是升序的。
	f1.merge(f2, greater<int>());

	for (forward_list<int>::iterator it = f1.begin(); it != f1.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
}

STL forward_list 单向链表

取消回复