突破编程_C++_C++11新特性（forward_list）

1 std::forward_list 的概述

1.1 什么是 std::forward_list？

std::forward_list 是 C++ 标准模板库（STL）中的一个容器，它表示一个单向链表。相比于 std::list，std::forward_list 在存储和操作上更加简洁，从而减小了空间开销。单向链表意味着它只支持从前往后的遍历，即只有前向迭代器，而不支持从后往前的遍历。

std::forward_list 的基本特性如下：

• 单向性：forward_list 中的迭代器只支持向前移动，不支持向后移动，因此不能从尾部向前遍历链表。
• 插入和删除操作：由于forward_list 是链表结构，因此在链表头部插入和删除元素的时间复杂度是常数。但需要注意的是，由于它只支持前向迭代，所以插入和删除操作在链表的其他位置可能会相对复杂一些。
• 空间效率：相比于 std::list（双向链表），std::forward_list 节省了用于存储指向下一个和上一个节点的指针的空间，因此其空间开销较小。

使用 std::forward_list 时，需要包含头文件<forward_list>。下面是一个简单的使用示例：

#include <iostream>  
#include <forward_list>  
  
int main() 
{  
    // 创建一个空的forward_list  
    std::forward_list<int> flst;  
  
    // 向forward_list的头部插入元素  
    flst.push_front(1);  
    flst.push_front(2);  
    flst.push_front(3);  
  
    // 移除forward_list的一个元素  
    flst.pop_front(); 
	
    // 遍历forward_list并打印元素  
    for (auto it = flst.begin(); it != flst.end(); ++it) {  
        std::cout << *it << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面代码的输出为：

2 1
1

在访问 forward_list 的第一个元素时，也可以使用 before_begin() 方法，这个方法返回的是第一个元素的前一个元素（也就是一个虚设的元素），不能直接解引用。但是，可以通过加 1 操作（ std::advance(it, 1) ）来访问第一个元素。

总体而言，std::forward_list 是一个单向链表容器，适用于那些只需要单向遍历数据结构的场景，它可以有效地节省空间，并提供常数时间的头部插入和删除操作。

1.2 std::forward_list 的使用场景

以下是std::forward_list的主要使用场景：

（1）内存空间有限： 当内存使用非常紧张，且每个字节都显得宝贵时，std::forward_list 是一个很好的选择。由于它只存储单个指针，相比双向链表（如 std::list）或动态数组（如 std::vector），它占用的空间更少。因此，在需要节省内存的场景中，std::forward_list 是理想的容器。

（2）频繁在头部插入或删除元素： 如果你的应用场景需要频繁在列表的头部插入或删除元素，std::forward_list 是一个很好的选择。由于单向链表的结构特性，它在头部插入或删除元素的时间复杂度几乎是常数时间，不依赖于容器的大小。因此，对于需要频繁进行此类操作的场景，std::forward_list 比其他类型的容器更加高效。

（3）不需要双向遍历： 如果应用场景不需要双向遍历元素，那么 std::forward_list 比 std::list 更加高效。单向链表只支持从前往后的遍历，这意味着它不需要存储额外的指针来实现双向遍历，从而节省了空间。在只需要单向遍历的场景中，使用 std::forward_list 可以避免不必要的空间开销。

2 声明与初始化

2.1 声明

首先，需要包含 <forward_list> 头文件，然后声明一个 std::forward_list 变量，并指定类型。

#include <forward_list>  
  
std::forward_list<Type> listName;
1
2
3

其中 Type 是元素的类型，listName 是 unordered_set 变量的名称。

2.2 初始化

std::forward_list 可以通过多种方式初始化。以下是一些常见的初始化方法：

（1）默认初始化

创建一个空的 forward_list：

std::forward_list<int> emptyList;
1

（2）使用列表初始化
使用花括号 {} 初始化 forward_list，其中可以包含多个元素：

std::forward_list<int> list = {1, 2, 3, 4, 5};
1

（3）使用迭代器范围初始化

如果有一个已存在的容器或数组，并希望使用它的元素来初始化 forward_list，可以使用迭代器范围：

std::vector<int> vec = {1, 2, 3, 4, 5};  
std::forward_list<int> list(vec.begin(), vec.end());
1
2

（4）使用 assign 方法初始化

可以先创建一个空的 forward_list，然后使用 assign 方法分配一组值给它：

std::forward_list<int> list;  
list.assign({10, 20, 30, 40, 50}); // 分配一组值给 list
1
2

（5）使用拷贝构造函数或赋值运算符

可以从一个已存在的 forward_list 创建另一个 forward_list，或者使用赋值运算符将一个 forward_list 的内容复制到另一个：

std::forward_list<int> list1 = {1, 2, 3, 4, 5}; 
std::forward_list<int> list2(list1);   // 使用拷贝构造函数 
std::forward_list<int> list3 = list1; // 使用赋值运算符
1
2
3

3 添加元素

3.1 使用 push_front 方法

push_front 是 std::forward_list 中最常用的添加元素的方法，它将元素添加到链表的头部：

std::forward_list<int> myList;  
myList.push_front(1);  
myList.push_front(2);  
myList.push_front(3);

// myList : 3 2 1
1
2
3
4
5
6

3.2 使用 emplace_front 方法

emplace_front 类似于 push_front，但它直接在容器中构造元素，避免了拷贝或移动操作，提高了效率：

std::forward_list<std::string> myStringList;  
myStringList.emplace_front("Hello");  
myStringList.emplace_front("World");

// myList : World Hello
1
2
3
4
5

3.3 使用 insert_after 方法

虽然 std::forward_list 主要用于在头部添加元素，但 insert_after 方法允许在指定的迭代器位置之后插入新元素。这通常用于在链表的特定位置插入元素：

std::forward_list<int> myList = {1, 2, 4};  
auto it = myList.before_begin(); // 获取头部之前的迭代器  
std::advance(it, 1); // 前进到第二个元素之前  
myList.insert_after(it, 3); // 在第二个元素之后插入3

// myList : 1 3 2 4 
1
2
3
4
5
6

3.4 使用 emplace_after 方法

与 insert_after 类似，但 emplace_after 直接在容器中构造元素（避免了拷贝或移动操作，效率更高）：

std::forward_list<std::string> myStringList = {"apple", "banana"};  
auto it = myStringList.before_begin();  
std::advance(it, 1);  
myStringList.emplace_after(it, "orange"); // 在"banana"之后构造并插入"orange"

// myList : apple orange banana
1
2
3
4
5
6

4 访问元素

4.1 迭代器遍历

迭代器是访问 std::forward_list 中元素的主要方式。由于 forward_list 是单向的，所以只能使用前向迭代器从头部开始向前遍历整个链表。

（1）基本迭代

std::forward_list<int> myList = {1, 2, 3, 4, 5};  
for (auto it = myList.begin(); it != myList.end(); ++it) {  
    std::cout << *it << ' '; // 访问当前元素的值  
}
1
2
3
4

（2）常量迭代器

如果只需要读取元素而不需要修改它们时，可以使用常量迭代器。

for (auto it = myList.cbegin(); it != myList.cend(); ++it) {  
    std::cout << *it << ' '; // 读取当前元素的值  
}
1
2
3

（3）基于的for循环

C++11 引入了范围基于的for循环，它使得遍历容器更加简洁。

for (const auto& element : myList) {  
    std::cout << element << ' '; // 读取当前元素的值  
}
1
2
3

4.2 访问第一个元素

由于 forward_list 是单向的，所以可以直接访问其第一个元素，但不能直接访问其他位置的元素。

if (!myList.empty()) {  
    std::cout << "First element: " << myList.front() << std::endl;  
}
1
2
3

4.3 使用算法库中的算法

C++ 标准库中的算法可以与容器一起使用，以执行各种操作，包括访问元素。

（1）使用 std::for_each

std::for_each(myList.begin(), myList.end(), [](int value) {  
    std::cout << value << ' '; // 访问并打印当前元素的值  
});
1
2
3

（2）使用 std::copy 将元素复制到另一个容器或输出流

std::vector<int> myList = { 1, 2, 3, 4, 5 };
std::vector<int> vec;  
std::copy(myList.begin(), myList.end(), std::back_inserter(vec));  
// 现在 vec 包含了 myList 的所有元素
1
2
3
4

5 删除元素

5.1 使用 erase_after 方法删除元素

std::forward_list 提供了 erase_after 方法来删除元素。该方法删除传入迭代器的下一个元素。

（1）删除单个元素

#include <iostream>  
#include <forward_list>  

int main() {

	std::forward_list<int> myList = { 1, 2, 3, 4, 5 };
	auto it = std::find(myList.begin(), myList.end(), 3); // 查找值为3的元素  
	if (it != myList.end()) {
		it = myList.erase_after(it); // 删除下一个元素（4）并返回下下个元素（5）的迭代器  
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

注意：在调用 erase_after 后，返回的迭代器指向被删除元素之后的元素。如果这是链表的最后一个元素，返回的迭代器将是 end()。

（2）删除一系列元素

虽然 forward_list 是单向的，但可以通过传入两个迭代器来删除一系列元素。

#include <iostream>  
#include <forward_list>  

int main() {

	std::forward_list<int> myList = { 1, 2, 3, 4, 5 };
	auto it = std::find(myList.begin(), myList.end(), 2); // 查找起始删除位置  
	if (it != myList.end()) {
		auto endIt = std::find(it, myList.end(), 5); // 查找结束删除位置（不包括此元素）  
		if (endIt != myList.end()) {
			it = myList.erase_after(it, endIt); // 删除一系列元素：3 4
		}
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.2 使用 remove 和 remove_if 方法删除元素

除了 erase，forward_list 还提供了 remove 和 remove_if 方法来删除满足特定条件的元素。

（1）使用 remove 删除特定值的元素

#include <iostream>  
#include <forward_list>  
#include <algorithm>

int main() {

	std::forward_list<int> myList = { 1, 2, 3, 3, 4, 5 };
	myList.remove(3); // 删除所有值为3的元素

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

（2）使用 remove_if 删除满足条件的元素

#include <iostream>  
#include <forward_list>  
#include <algorithm>

int main() {

	std::forward_list<int> myList = { 1, 2, 3, 4, 5, 6 };
	myList.remove_if([](int n) { return n % 2 == 0; }); // 删除所有偶数

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

remove_if 方法接受一个谓词（即返回布尔值的函数或可调用对象），并删除所有使谓词返回 true 的元素。

5.3 使用 partition 和 stable_partition 删除元素

std::partition 或 std::stable_partition 可以根据谓词将元素分为两组，但不保证组内元素的相对顺序。之后，就可以使用 erase 方法删除不需要的那一组元素。

#include <iostream>  
#include <forward_list>  
#include <algorithm>

int main() {

	std::forward_list<int> myList = { 1, 2, 3, 4, 5 };
	auto it = std::partition(myList.begin(), myList.end(), [](int n) { return n < 3; });
	myList.erase_after(it, myList.end()); // 删除所有不小于3的元素

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

在这个例子中，std::partition 将所有小于 3 的元素移动到链表的前面，然后就可以使用 erase_after 删除剩余的元素。

5.4 遍历删除

一个安全的方法是使用迭代器遍历 std::forward_list，并在删除元素后更新迭代器。

#include <iostream>  
#include <forward_list>  

int main() {

	std::forward_list<int> myList = { 1, 2, 3, 4, 5 };

	auto itPre = myList.before_begin();
	size_t offset = 0;
	for (auto it = myList.begin(); it != myList.end(); ) {
		// 检查是否需要删除当前元素  
		if (*it % 2 == 0) {
			it = myList.erase_after(itPre);
			itPre = myList.before_begin();
			std::advance(itPre, offset);
		}
		else {
			// 否则，继续到下一个元素  
			++it;
			++itPre;
			++offset;
		}
	}

	return 0;
}
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