引入

transform是 C++ 中对应函数式编程 Map 操作的标准库函数。

提供两种调用方式:

  1. 第一形式有 4 个参数,把源区间的元素转换到目标区间。也就是说,复制和修改元素一气呵成;
  2. 第二形式有 5 个参数,将前两个源序列中的元素合并,并将结果写入目标区间。

下面分别介绍一下两种形式的用法。

1. 用法一

transform(sourceBeg, sourceEnd, destBeg, opfunction)

参数解释

  • transform 会针对区间 [sourceBeg, sourceEnd) 中的每一个元素均调用一次 opfunction,并将返回结果写到以destBeg为起始地址的目标区间内;
  • 每对一个元素进行操作后,destBeg会后移一位,最终 transform会返回目标区间内 最后一个被转换元素的下一个位置;
  • sourceBegdestBeg可以相同,所以可以使用 opfunction对当前区间的元素进行变换;
  • 如果想用某个值替换符合某个条件的元素,应该用 replace()函数替代;
  • 时间复杂度:区间长度nn,opfunction时间复杂度为Θ(m)\Theta(m),则总时间复杂度为Θ(nm)\Theta(n * m)

具体用法

Leetcode819. 最常见的单词

这里的 cbegin()cend() 表示这是一个 const iterator ,这个是 C++11 中新增的内容;

首先我们使用 transform 对原来的字符串统一处理成小写并将非字母元素替换为空格;

然后使用 stringstream 来分割字符串;

最后我们利用 max_element 来取到哈希表中最大的值对应的key 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
string mostCommonWord(string paragraph, vector<string>& banned) {
transform(paragraph.cbegin(), paragraph.cend(), paragraph.begin(),
[](auto& c) {return isalpha(c) ? tolower(c): ' ';});
stringstream ss(paragraph);
unordered_set ban(banned.begin(), banned.end());
unordered_map<string, size_t> dict;

for(string tmp; ss >> tmp; ban.count(tmp) ? 0 : dict[tmp]++);

return max_element(dict.begin(), dict.end(),
[](auto& a, auto& b) {return a.second < b.second;})->first;
}
};

用法二

transform(source1Beg, source1End, source2Beg, destBeg, opfunction)

大体内容同上,这里补充一下不同的地方:

  • opfunction会针对第一区间 [source1Beg, source1End) 中的每一个元素e1e_1,和第二区间中的每一个元素e2e_2调用opfunction(e1, e2),并将返回值插入到以destBeg起始的区间中;
  • 调用者必须保证 第二区间 有足够的空间,至少要和第一区间大小相同;
  • 调用者必须保证 目标区间 有足够的空间,否则必须使用插入形迭代器;
  • source1Beg,source2Beg,destBeg可以相同,所以可以让元素自己和自己结合,然后覆盖到某个区间中。

用法举例1

这里我们生成了一个[0,9][0, 9] 的序列,然后让他自身相乘,最后覆盖原序列的内容。

所以输出为:0 1 4 9 16 25 36 49 64 81

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main()
{
vector<int> vec1;
for(int i = 0; i < 10; ++i) vec1.push_back(i);

transform(vec1.begin(), vec1.end(), vec1.begin(), vec1.begin(), multiplies<int>());

for(auto e: vec1) cout << e << " ";
cout << endl;
return 0;
}

用法举例2

这里我们生成了一个正序和一个倒序的[0,9][0, 9] 序列,然后让对应位置上的元素进行相加,最后覆盖第一个序列的元素。

所以输出为:9 9 9 9 9 9 9 9 9 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main()
{
vector<int> vec1, vec2;
for(int i = 0; i < 10; ++i) {
vec1.push_back(i);
vec2.push_back(9 - i);
}

transform(vec1.begin(), vec1.end(), vec2.begin(), vec1.begin(), [](auto& e1, auto& e2) { return e1 + e2; });
for(auto e: vec1) cout << e << " ";
cout << endl;
return 0;
}