C++的“select”算法

Question

在 std::algorithm 中，我似乎找不到一个我认为最基本的功能之一：选择集合的子集（例如，返回所有奇数、所有状态为'employed'的员工、所有价格低于20美元的商品）。

因此，假设有一个像这样的整数列表：

vector<int> ints {1, 9, 3, 27, 5, 19, 3, 8, 2, 12};

vector<int> evens = ?
vector<int> greaterThan7 = ?

如何找到那些偶数并且大于7的数字？

- pistacchio

---

std::copy_if 不适用于您吗？ - NathanOliver

顺便说一下... std::algorithm 这个东西是不存在的。你可能想要写的是 <algorithm>。 - Christian Hackl

Answer 1

如果您想要更多功能，可以查看boost range库。具体而言，请查看filtered：

for (int i : ints | filtered([](int i){return i > 7;}))
{
    ...
}

这为您提供了一种懒惰视图，而无需构建新容器。

---

您可以从Eric Niebler的range-v3中获得相同的结果:

for (int i : view::filter(ints, [](int i){return i > 7;})
{
    ...
}

有一个好处是你也可以将其分配给向量（所以你可以选择是惰性或急切的，这是Boost.Range不允许的）。

std::vector<int> greaterThan7 = view::filter(ints, [](int i){return i > 7;});
std::vector<int> sameThing    = ints | view::filter([](int i){return i > 7;});

- Barry

---

好的。我以为你的意思是用boost版本来初始化sameThing。 - NathanOliver

@NathanOliver 不支持。我的意思是要证明ranges也支持管道。 - Barry

好的。我不知道那个。我总是从你的回答中学到一些东西。谢谢。 - NathanOliver

@Barry 我一开始也和Nathan有同样的误解，也许你可以把这个写进你的答案中。 - Felix Dombek

Answer 2

例如。

vector<int> ints {1, 9, 3, 27, 5, 19, 3, 8, 2, 12};
vector<int> evens;

std::copy_if( ints.begin(), ints.end(), std::back_inserter( evens ),
              []( int x ) { return x % 2 == 0; } );

这是一个演示程序

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> ints { 1, 9, 3, 27, 5, 19, 3, 8, 2, 12 };
    std::vector<int> evens;

    std::copy_if( ints.begin(), ints.end(), std::back_inserter( evens ),
                  []( int x ) { return x % 2 == 0; } );

    for ( int x : evens ) std::cout << x << ' ';
    std::cout << std::endl;
}        

它的输出是

8 2 12

- Vlad from Moscow

---

请记住，与C#或其他语言中的Select相比，这些函数不是惰性的，因此可能非常昂贵。 - Mats Fredriksson

公平地说，这个问题的示例代码也不是懒惰的。如果需要进行懒惰评估过滤，可以将std::find_if包装在迭代器适配器中。 - Useless

@MatsFredriksson 我们很快就会有针对惰性求值的范围。 - bolov

Answer 3

根据你的具体需求，考虑使用 std::stable_partition（或 std::partition）。它会重新排序范围内的元素，使所有满足谓词的元素都排在前面。你可以将其视为将范围分成“子集”和“非子集”两部分。以下是一个示例：

#include <algorithm>
#include <vector>
#include <iostream>

int main()
{
    using std::begin;
    using std::end;
    using std::cbegin;
    using std::cend;

    std::vector<int> ints { 1, 9, 3, 27, 5, 19, 3, 8, 2, 12 };

    auto const greater_than_7 = [](int number) { return number > 7; };

    auto const iter_first_not_greater_than_7 = std::stable_partition(begin(ints), end(ints), greater_than_7);

    for (auto const_iter = cbegin(ints); const_iter != iter_first_not_greater_than_7; ++const_iter)
    {
        std::cout << *const_iter << "\n";
    }
}

然而，如果您愿意将每个匹配的元素复制到新集合中，例如因为源范围不得修改，则使用std::copy_if。

---

也许你真正需要的是一个不可修改范围的视图。在这种情况下，你的问题解决方法是错误的。你不需要特定算法；更自然的解决方案是一种过滤迭代器，例如Boost's Filter Iterator。你可以使用 Boost 中的迭代器或学习它的实现来了解如何编写过滤迭代器。

- Christian Hackl

---

这正是我要建议的。具体来说，使用std::stable_partition。 - erip