43

STL 算法在 C++ 中非常有用。但让我感到厌烦的一件事是它们似乎缺乏可组合性。

例如，假设我有 avector<pair<int, int>>并且想要将其转换为vector<int>仅包含对的second成员的 a。这很简单：

std::vector<std::pair<int, int>> values = GetValues();
std::vector<int> result;

std::transform(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return p.second; });

或者，也许我只想过滤vector那些first成员为偶数的对。也很简单：

std::vector<std::pair<int, int>> values = GetValues();
std::vector<std::pair<int, int>> result;

std::copy_if(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return (p.first % 2) == 0; });

但是如果我想两者都做呢？没有transform_if算法，并且使用两者transform似乎copy_if需要分配一个临时vector来保存中间结果：

std::vector<std::pair<int, int>> values = GetValues();
std::vector<std::pair<int, int>> temp;
std::vector<int> result;

std::copy_if(values.begin(), values.end(), std::back_inserter(temp),
    [] (std::pair<int, int> p) { return (p.first % 2) == 0; });

std::transform(values.begin(), values.end(), std::back_inserter(result),
    [] (std::pair<int, int> p) { return p.second; });

这对我来说似乎相当浪费。我能想到的避免临时向量的唯一方法是放弃transform并copy_if简单地使用for_each（或常规的 for 循环，以适合您的方式）：

std::vector<std::pair<int, int>> values = GetValues();
std::vector<int> result;

std::for_each(values.begin(), values.end(),
    [&result] (std::pair<int, int> p) 
        { if( (p.first % 2) == 0 ) result.push_back(p.second); });

我在这里错过了什么吗？有没有一种不需要临时存储就可以将两个现有的 STL 算法组合成一个新算法的好方法？

4

5 回答 5

25

你是对的。您可以使用Boost.Range 适配器来实现组合。

于 2011-07-19T06:37:20.563 回答
11

我认为这个问题不幸是结构性的

  1. C++ 使用两个迭代器来表示一个序列
  2. C++ 函数是单值的

所以你不能链接它们，因为一个函数不能返回“一个序列”。

一种选择是使用单对象序列代替（例如 boost 的 range 方法）。这样，您可以将一个处理的结果组合为另一个处理的输入......（一个对象 -> 一个对象）。

相反，在标准 C++ 库中，处理是（两个对象 -> 一个对象），很明显，如果不命名临时对象，就无法将其链接起来。

于 2011-07-19T06:36:42.590 回答
8

早在 2000 年，这个问题就已经被注意到了。Gary Powell 和 Martin Weiser 提出了“视图”概念，并创造了“视图模板库”这个名称。它当时并没有起飞，但这个想法是有道理的。“视图”适配器本质上是应用动态变换。例如，它可以适应value_type.

现在我们有了 C++0x，这个概念可能应该重新解决。自 2000 年以来，我们在泛型编程方面取得了相当大的进展。

例如，让我们使用vector<pair<int, int>> tovector<int>示例。这可能很简单：

std::vector<std::pair<int, int>> values = GetValues();
vtl2::view v (values, [](std::pair<int, int> p) { return p.first }); 
std::vector<int> result(view.begin(), view.end());

或者，使用这些boost::bind技术，甚至更简单：

std::vector<std::pair<int, int>> values = GetValues();
vtl2::view v (values, &std::pair<int, int>::first); 
std::vector<int> result(view.begin(), view.end());
于 2011-07-19T08:13:20.620 回答
2

从C++20开始，您可以std::ranges::copy与范围适配器std::views::filter和Ranges 库std::views::values一起使用，如下所示：

int main() {
    std::vector<std::pair<int, int>> values = { {1,2}, {4,5}, {6,7}, {9,10} };
    std::vector<int> result;

    auto even = [](const auto& p) { return (p.first % 2) == 0; };
    std::ranges::copy(values | std::views::filter(even) | std::views::values,
                      std::back_inserter(result));

    for (int i : result)
        std::cout << i << std::endl;

    return 0;
}

输出：

5
7

在上面的解决方案中，没有为中间结果创建临时向量，因为视图适配器创建不包含元素的范围。这些范围只是输入向量的视图，但具有自定义的迭代行为。

魔杖盒上的代码

于 2021-03-11T15:40:59.417 回答
0

不确定这是否仍然有效，但是...一个新的轻型等待标头仅库，可以满足您的描述。Doc 谈到惰性求值和 com 可组合生成器。

文档片段：

  • 从文件“test.txt”中读取最多 10 个整数。
  • 过滤偶数，将它们平方并求和它们的值。
    int total = lz::read<int>(ifstream("test.txt")) | lz::limit(10) |
                lz::filter([](int i) { return i % 2 == 0; }) |
                lz::map([](int i) { return i *  i; }) | lz::sum();

您可以将该行拆分为多个表达式。

    auto numbers = lz::read<int>(ifstream("test.txt")) | lz::limit(10);
    auto evenFilter = numbers | lz::filter([](int i) { return i % 2 == 0; });
    auto squares = evenFilter | lz::map([](int i) { return i *  i; });
    int total = squares | lz::sum();
  • 尽管这个表达式被拆分为多个变量赋值，但它的效率并没有降低。
  • 每个中间变量简单地描述了一个要执行的代码单元。全部存放在堆栈中。

https://github.com/SaadAttieh/lazyCode

于 2019-02-05T12:47:14.907 回答