STL算法的可组合性

Question

STL算法在C++中非常有用.但有一点令我烦恼的是,他们似乎缺乏可组合性.

例如,假设我有一个vector<pair<int, int>>并且想要将其转换为vector<int>仅包含second该对的成员.这很简单:

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; });

这对我来说似乎相当浪费.我能想到的唯一的方式,以避免临时vector是放弃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算法组合成一个新的算法,而无需临时存储？

Answer 1

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

Answer 2

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

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

所以你不能链接它们,因为函数不能返回"序列".

一个选项可能是使用单对象序列(如boost的范围方法).这样你就可以把一个处理的结果作为另一个处理的输入...(一个对象 - >一个对象).

在标准C++库中,处理是(两个对象 - >一个对象),很明显,如果不命名临时对象,则无法链接.

Answer 3

早在2000年,问题就已经出现了.Gary Powell和Martin Weiser提出了一个"视图"概念,并创造了"查看模板库"的名称.它没有起飞,但这个想法是有道理的."视图"适配器基本上应用了即时转换.例如,它可以适应value_type.

现在我们有了C++ 0x,这个概念可能应该重新阅读.自2000年以来,我们在通用编程方面取得了一些进展.

例如,让我们使用vector<pair<int, int>> 到vector<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());

Answer 4

从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

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

Wandbox 上的代码