C++ STL 算法 transform 的数据过滤功能
C++ STL 算法 transform 的数据过滤功能
1. 理解 C++ STL 中的 transform 算法
在 C++ 标准模板库（STL）中，transform 是一个非常强大且实用的算法。它定义在 <algorithm> 头文件中，主要功能是将一个范围内的元素，通过指定的操作，转换并存储到另一个范围中。transform 算法有两种重载形式：
1.1 第一种重载形式
template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first,
UnaryOperation unary_op);
这种形式的 transform 算法将 [first1, last1) 范围内的每个元素 *i 应用一元操作 unary_op(*i)，并将结果存储到从 d_first 开始的输出范围中。返回值是指向输出范围中最后一个被写入元素之后位置的迭代器。
1.2 第二种重载形式
template<class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2,
OutputIt d_first, BinaryOperation binary_op);
此重载形式中，transform 算法对 [first1, last1) 范围内的每个元素 *i 和 [first2, first2 + (last1 - first1)) 范围内对应的元素 *(first2 + (i - first1)) 应用二元操作 binary_op(*i, *(first2 + (i - first1)))，并将结果存储到从 d_first 开始的输出范围。同样，返回值是指向输出范围中最后一个被写入元素之后位置的迭代器。
2. 数据过滤的概念及在 transform 中的应用
数据过滤是指从一组数据中筛选出符合特定条件的数据子集的过程。在 C++ 中，借助 transform 算法，我们可以巧妙地实现数据过滤功能。
2.1 利用一元函数对象实现数据过滤
我们可以定义一个一元函数对象（或 lambda 表达式），在函数对象的 operator() 中实现数据过滤的逻辑。当 transform 算法调用这个一元函数对象时，只有满足过滤条件的元素才会被“转换”并存储到输出范围。
#include <iostream>
#include <algorithm>
#include <vector>
// 定义一元函数对象用于过滤偶数
struct FilterEven {
bool operator()(int num) const {
return num % 2 != 0;
}
};
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> filteredNumbers;
filteredNumbers.resize(numbers.size());
auto endIt = std::transform(numbers.begin(), numbers.end(), filteredNumbers.begin(), FilterEven());
// 调整 filteredNumbers 的大小以匹配实际过滤后的元素数量
filteredNumbers.resize(std::distance(filteredNumbers.begin(), endIt));
for (int num : filteredNumbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在上述代码中，FilterEven 是一个一元函数对象，它的 operator() 函数判断一个整数是否为奇数。transform 算法将 numbers 向量中的每个元素传递给 FilterEven 对象，只有奇数元素对应的返回值为 true，这些元素被“转换”（实际是保持不变）并存储到 filteredNumbers 向量中。最后，我们调整 filteredNumbers 的大小以匹配实际过滤后的元素数量并输出。
2.2 利用 lambda 表达式实现数据过滤
使用 lambda 表达式可以更简洁地实现数据过滤功能。
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> filteredNumbers;
filteredNumbers.resize(numbers.size());
auto endIt = std::transform(numbers.begin(), numbers.end(), filteredNumbers.begin(),
[](int num) { return num % 2 != 0; });
filteredNumbers.resize(std::distance(filteredNumbers.begin(), endIt));
for (int num : filteredNumbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
这里的 lambda 表达式 [](int num) { return num % 2 != 0; } 与前面的 FilterEven 函数对象功能相同，都是判断一个整数是否为奇数。transform 算法同样将 numbers 向量中的元素传递给这个 lambda 表达式进行过滤。
3. 数据过滤时的一些注意事项
3.1 输出范围的大小
在使用 transform 进行数据过滤时，我们需要注意输出范围的大小。如前面的代码示例，我们预先将 filteredNumbers 向量的大小调整为与输入向量 numbers 相同。这是因为 transform 算法会按照输入范围的大小进行操作并向输出范围写入数据。但实际过滤后的数据数量可能小于输入数据数量，所以我们需要在 transform 调用后，根据返回的迭代器调整输出范围的实际大小，如使用 std::distance 计算实际写入的元素数量并调整向量大小。
3.2 函数对象或 lambda 表达式的副作用
当定义用于数据过滤的函数对象或 lambda 表达式时，要尽量避免引入副作用。例如，不要在函数对象的 operator() 或 lambda 表达式中修改全局变量。因为 transform 算法的调用顺序和线程安全性等问题，带有副作用的函数对象或 lambda 表达式可能导致不可预测的结果。
#include <iostream>
#include <algorithm>
#include <vector>
int globalCount = 0;
// 带有副作用的函数对象
struct SideEffectFilter {
bool operator()(int num) {
globalCount++;
return num > 5;
}
};
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> filteredNumbers;
filteredNumbers.resize(numbers.size());
auto endIt = std::transform(numbers.begin(), numbers.end(), filteredNumbers.begin(), SideEffectFilter());
filteredNumbers.resize(std::distance(filteredNumbers.begin(), endIt));
std::cout << "Global count: " << globalCount << std::endl;
for (int num : filteredNumbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在上述代码中，SideEffectFilter 函数对象在判断元素是否大于 5 的同时，会增加全局变量 globalCount。在单线程环境下，globalCount 的值可能符合预期，但在多线程环境下，由于 transform 算法的并行实现可能性（在某些 STL 实现中），globalCount 的值可能不准确，导致程序出现难以调试的错误。
4. 更复杂的数据过滤场景
4.1 结合多个过滤条件
有时候，我们需要根据多个条件对数据进行过滤。可以在函数对象或 lambda 表达式中组合多个条件。
#include <iostream>
#include <algorithm>
#include <vector>
// 定义函数对象结合多个过滤条件
struct ComplexFilter {
bool operator()(int num) const {
return num > 3 && num < 8 && num % 2 == 0;
}
};
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> filteredNumbers;
filteredNumbers.resize(numbers.size());
auto endIt = std::transform(numbers.begin(), numbers.end(), filteredNumbers.begin(), ComplexFilter());
filteredNumbers.resize(std::distance(filteredNumbers.begin(), endIt));
for (int num : filteredNumbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在 ComplexFilter 函数对象中，我们定义了三个过滤条件：元素大于 3、小于 8 且为偶数。transform 算法会根据这个复合条件对 numbers 向量中的元素进行过滤。
4.2 对自定义类型的数据进行过滤
当处理自定义类型的数据时，同样可以使用 transform 算法进行数据过滤。我们需要为自定义类型定义合适的过滤逻辑。
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
// 自定义结构体
struct Person {
std::string name;
int age;
};
// 定义函数对象过滤年龄大于 30 的人
struct FilterByAge {
bool operator()(const Person& person) const {
return person.age > 30;
}
};
int main() {
std::vector<Person> people = {{"Alice", 25}, {"Bob", 35}, {"Charlie", 40}, {"David", 28}};
std::vector<Person> filteredPeople;
filteredPeople.resize(people.size());
auto endIt = std::transform(people.begin(), people.end(), filteredPeople.begin(), FilterByAge());
filteredPeople.resize(std::distance(filteredPeople.begin(), endIt));
for (const Person& person : filteredPeople) {
std::cout << person.name << " : " << person.age << std::endl;
}
return 0;
}
在上述代码中，我们定义了 Person 结构体表示人，包含姓名和年龄。FilterByAge 函数对象用于过滤年龄大于 30 的人。transform 算法将 people 向量中的每个 Person 对象传递给 FilterByAge 函数对象进行过滤。
5. 与其他 STL 算法结合实现更强大的数据过滤
5.1 与 remove_if 结合
remove_if 算法也是 STL 中用于数据过滤的重要算法。它会移除范围内满足特定条件的元素，但不会真正从容器中删除元素，而是将不满足条件的元素向前移动，返回一个指向新的逻辑“结尾”的迭代器。我们可以将 transform 与 remove_if 结合使用，以实现更灵活的数据过滤。
#include <iostream>
#include <algorithm>
#include <vector>
// 定义函数对象过滤偶数
struct FilterEven {
bool operator()(int num) const {
return num % 2 == 0;
}
};
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// 使用 remove_if 移除偶数
auto newEnd = std::remove_if(numbers.begin(), numbers.end(), FilterEven());
// 使用 transform 对剩余元素进行平方操作
std::transform(numbers.begin(), newEnd, numbers.begin(), [](int num) { return num * num; });
numbers.resize(std::distance(numbers.begin(), newEnd));
for (int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在上述代码中，首先使用 remove_if 算法移除 numbers 向量中的偶数，得到新的逻辑结尾 newEnd。然后，使用 transform 算法对剩余的奇数元素进行平方操作。最后，调整向量大小并输出结果。
5.2 与 accumulate 结合
accumulate 算法用于对范围内的元素进行累加（或其他自定义的二元操作）。我们可以结合 transform 和 accumulate 实现先过滤数据再进行累加操作。
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
// 定义函数对象过滤大于 5 的数
struct FilterGreaterThanFive {
bool operator()(int num) const {
return num > 5;
}
};
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> filteredNumbers;
filteredNumbers.resize(numbers.size());
auto endIt = std::transform(numbers.begin(), numbers.end(), filteredNumbers.begin(), FilterGreaterThanFive());
filteredNumbers.resize(std::distance(filteredNumbers.begin(), endIt));
int sum = std::accumulate(filteredNumbers.begin(), filteredNumbers.end(), 0);
std::cout << "Sum of filtered numbers: " << sum << std::endl;
return 0;
}
这里先使用 transform 算法过滤出大于 5 的数，存储到 filteredNumbers 向量中。然后使用 accumulate 算法对过滤后的数字进行累加，并输出累加结果。
6. 性能考虑
在使用 transform 进行数据过滤时，性能是一个需要考虑的因素。
6.1 算法复杂度
transform 算法的时间复杂度为线性，即 O(n)，其中 n 是输入范围中的元素数量。这意味着对于较大规模的数据，其运行时间会随着数据量的增加而线性增长。在设计算法和选择数据结构时，需要考虑到这一点，如果数据量非常大，可能需要寻找更高效的过滤方式，如并行算法或更优化的数据结构。
6.2 缓存局部性
在编写用于数据过滤的函数对象或 lambda 表达式时，尽量保证缓存局部性。例如，避免频繁访问内存中不连续的数据。如果函数对象或 lambda 表达式需要访问其他数据结构，尽量确保这些数据结构与输入范围的数据在内存布局上具有良好的局部性，这样可以提高缓存命中率，从而提升程序的性能。
#include <iostream>
#include <algorithm>
#include <vector>
// 定义一个与输入向量相关的辅助向量
std::vector<int>辅助向量 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
// 定义函数对象结合辅助向量进行过滤
struct ComplexFilterWithAux {
bool operator()(int num, int auxNum) const {
return num + auxNum > 50;
}
};
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> filteredNumbers;
filteredNumbers.resize(numbers.size());
auto endIt = std::transform(numbers.begin(), numbers.end(), 辅助向量.begin(), filteredNumbers.begin(), ComplexFilterWithAux());
filteredNumbers.resize(std::distance(filteredNumbers.begin(), endIt));
for (int num : filteredNumbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在上述代码中，ComplexFilterWithAux 函数对象使用了与输入向量 numbers 相对应位置的 辅助向量 中的元素进行过滤条件判断。由于 numbers 和 辅助向量 在内存中是连续存储的，并且 transform 算法按顺序访问元素，这样的设计有助于提高缓存局部性。
6.3 并行执行
在 C++17 及更高版本中，transform 算法支持并行执行策略。通过使用并行执行策略，可以充分利用多核处理器的优势，提高大规模数据过滤的性能。
#include <iostream>
#include <algorithm>
#include <execution>
#include <vector>
// 定义函数对象过滤偶数
struct FilterEven {
bool operator()(int num) const {
return num % 2 != 0;
}
};
int main() {
std::vector<int> numbers(1000000);
for (size_t i = 0; i < numbers.size(); ++i) {
numbers[i] = i + 1;
}
std::vector<int> filteredNumbers;
filteredNumbers.resize(numbers.size());
auto endIt = std::transform(std::execution::par, numbers.begin(), numbers.end(), filteredNumbers.begin(), FilterEven());
filteredNumbers.resize(std::distance(filteredNumbers.begin(), endIt));
std::cout << "Filtered numbers size: " << filteredNumbers.size() << std::endl;
return 0;
}
在上述代码中，通过 std::execution::par 指定了并行执行策略。这使得 transform 算法在多核处理器上并行处理 numbers 向量中的元素，从而加快数据过滤的速度。但需要注意的是，并行执行可能会带来一些额外的开销，如线程创建和同步开销，对于小规模数据，并行执行可能不会带来性能提升，甚至会降低性能。因此，在实际应用中，需要根据数据规模和硬件环境进行测试和优化。
通过深入理解 transform 算法的特性、注意事项以及与其他 STL 算法的结合使用，并充分考虑性能因素，我们可以在 C++ 编程中高效地利用 transform 算法实现各种数据过滤功能，满足不同场景下的需求。无论是处理简单的整数数据，还是复杂的自定义类型数据，transform 算法都为我们提供了一种灵活且强大的数据处理方式。