1

我想将 aview::filter应用于一个向量，以便找到它与另一个向量的 set_intersection（或 set_difference 等）。

我这样做的兴趣在于它允许您更改原始容器的特定子集（并且还可以节省一些附带的复制std::set_intersection）。

这或多或少是我想要做的：

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    std::vector<int> set1 = { 1, 2, 3, 4, 5, 6 },
                     set2 =          { 4, 5, 6, 7, 8, 9 };

    auto intersection = set1 | std::views::filter([&set2](int n)
    { return std::find(set2.cbegin(), set2.cend(), n) != set2.cend(); });

    for (int& v : intersection)
        v *= 2;

    for (auto v : set1)
        std::cout << v << " ";   // prints 1 2 3 8 10 12
}

然而，这段代码看起来非常低效，因为它会多次迭代 set2。ranges图书馆有没有更好的方法来实现这一点？

4

3 回答 3

2

然而，这段代码看起来非常低效，因为它会多次迭代 set2。

它效率低下，而且这种方法通常也不是有效的。在您的示例中，元素都是不同的。但如果他们不是呢？

std::vector<int> a = { 1, 1, 2, 2, 3 };
std::vector<int> b = { 1, 4, 5 };

这两者的交集应该是但是查看in{ 1 }的每个元素的方法会产生。目前其他两个答案也有同样的问题。ab{ 1, 1 }

最简单的做法是使用 range-v3，它的范围适配器比 C++20 多得多。特别是，它有一个名为views::set_intersection：

namespace rv = ranges::views;

int main() {
    std::vector<int> a = {1, 1, 2, 2, 3};
    std::vector<int> b = {1, 3, 4, 5};

    std::cout << rv::set_intersection(a, b) << '\n'; // prints [1,3]
}

然后您可以根据需要使用它来更改原始容器：

namespace rv = ranges::views;

int main() {
    std::vector<int> a = {1, 1, 2, 2, 3};
    std::vector<int> b = {1, 3, 4, 5};

    for (int& i : rv::set_intersection(a, b)) {
        i *= 2;
    }

    std::cout << rv::all(a) << '\n'; // prints [2,1,2,2,6]
}

请注意，只有第一个1是双倍的。

于 2021-02-15T04:48:08.420 回答
0

假设在问题中，“到向量”，“向量的”和“ std::set_intersection”被认为是重要的，我想我们只想处理已经排序的向量（不将元素转移到另一个容器）（根据要求 std::set_intersection()）。

我会使用可变闭包来将其内部状态从一次迭代更改为另一次迭代。然后，我们可以使用与可能的实现std::set_intersection相同的技巧。由于我们总是向前推进set2（虽然元素被认为太小）并且从不回头，因此复杂性与 N1×N2 不同，而是与 N1+N2 相似（如文档中所述）。

    auto intersection = set1 | std::views::filter(
      [b2=cbegin(set2), e2=cend(set2)](int n) mutable
      {
        while((b2!=e2)&&(*b2<n))
        {
          advance(b2, 1);
        }
        return (b2!=e2)&&(*b2==n);
      });
于 2021-02-14T08:23:48.737 回答
0

为什么不直接将值的集合set2放入一个 actualstd::set中，以便检查一个元素set1是否在 inset2中更有效？

这样做，您可以简单地set1通过返回不变的那些不在其中的值set2并更改那些值来进行转换：

#include <iostream>
#include <algorithm>
#include <vector>
#include <ranges>
#include <set>

int main() {
    std::vector<int> set1 = { 1, 2, 3, 4, 5, 6 };
    std::set<int>    set2 =          { 4, 5, 6, 7, 8, 9 };
    auto set1edit = set1 | std::ranges::views::transform( // O(set1.size())
            [&set2 = std::as_const(set2)](auto const& x){
            if (set2.find(x) != set2.end()) // O(log(set2.size()))
                return x*2;
            else
                return x;
            });

    for (int const& v : set1edit)
        std::cout << v << " ";   // prints 1 2 3 8 10 12
}

请注意，我已经强调了 ; 的复杂性transform是 O( set1.size())，因为您处理了 ; 中的每个set1.size()元素set1。set1制作a甚至没有意义std::set，因为如果我们必须循环所有元素， astd::vector就很好。

另一方面， usingstd::set<>::find保证比 using 更好的性能std::find。

正如评论所暗示的那样，如果您知道两个向量都已排序，那么一切都可以变得更容易，但我觉得您示例中的排序向量只是您尝试的“过度”简化的结果。

于 2021-02-14T08:54:57.290 回答