问题标签 [set-intersection]

我有一组向量 A _i使得 i = 1...N; 其中 N 可以非常大，并且向量包含除 0 之外的整数。所有向量的长度相同，所以这很好。我需要一个函数，其输出是单元格数组 C（数据类不一定是单元格 btw），这样 C 索引实际上是向量元素，单元格内容是共享内容的 A 向量的 i 索引。

F : A_我--> C

例子：

结果 C 应该是

当然，我想避免按元素进行 for 循环。

我想知道这是否可以使用 lambda 表达式来解决：

我目前正在从事一个爱好项目，其中我在 2D 虚构宇宙中拥有数千颗星星。我需要将这些星星渲染到屏幕上，但显然我不想对所有星星进行操作——只对在任何给定时间可见的星星进行操作。

为了概念验证，我编写了一个蛮力算法，它会查看每颗星星并根据玩家屏幕的边界测试它的坐标：

虽然这种笨拙的方法确实只将可见的星星绘制到屏幕上，但它显然是在线性时间中运行的。由于星星只是背景的一部分，坦率地说，对于处理器来说，花时间过滤并不是最重要的事情，我想设计一种更快的算法来减少一些负载。

所以，我目前的思路是使用二分搜索来找到相关的星星。为此，我显然需要对我的数据进行排序。但是，我不太确定如何对坐标数据进行排序——我想不出任何绝对排序可以让我按升序正确排序数据（关于 x 和 y 坐标） .

因此，我实现了两个新容器——一个用于按 x 坐标排序的数据，另一个用于按 y 坐标排序的数据。我最初的想法是取这两个排序集的交集并将生成的星星绘制到屏幕上（x 和 y 坐标位于屏幕边界内的星星）：

然后我对这些容器进行了排序：

不幸的是，我似乎既无法为 std::set_intersection 提供合适的比较函数，也无法使用迭代器手动比较坐标的方法。

你们能指出我正确的方向吗？非常欢迎对我的方法或实施提供反馈。

谢谢你的时间！

在 C++ 中找到两个范围交集的最佳方法是什么？例如，如果我有一个包含 [1...20] 的范围，另一个包含 [13...45] 的范围，我想获得 [13...20]，因为这是它们之间的交集。

我曾考虑在 C++ 中使用本机集合交集函数，但我首先必须将范围转换为集合，这对于大值会花费太多计算时间。

首先，我的目的是在两个已知集合中随机获取一个元素。所以我原来的方法是先相交两组。然后从相交集中随机选取一个元素。但这是愚蠢的，因为我只需要一个元素，但需要一个相交集。

所以我需要找到set.intersection()的算法。

我比较了 'set.intersection()' 和 'for{for{}}' 方法之间的成本时间。Set.intersection() 比其他更快（100 倍）。所以使用'for{for{}}'来随机选取一个元素并不是一个明智的主意。

python中set.intersection()背后的算法是什么？

我试图得到两个集合的交集和差异，每个集合都由这种形式的单链表表示

我已经在之前的任务中编写了这个函数，它计算列表中元素的数量并确定某个元素是否包含在列表中。

现在我必须编写以下函数，但我不知道该怎么做。我是否应该遍历一个列表并为列表中的每个元素循环遍历第二个列表以检查它是否包含在第二个列表中？对于这项任务来说，这似乎很复杂，必须有一种更简单的方法来做到这一点。希望你能帮我

大家好 :) id 喜欢创建一个个人集合类并重载运算符 /=，在我的类的情况下，这个运算符应该用于获取两个集合的交互。我收到以下错误：

错误：分配只读位置 '__result.std::_Rb_tree_const_iterator<_Tp>::operator*()'

这是给我这个错误的代码部分：

我是 C++ 的新手，我不明白我在哪里试图在只读位置分配一些东西......请你向我解释一下，然后告诉我应该如何正确使用 set_intersection（来自库

对不起，我的英文大概是，已经谢谢你的帮助=D

用户 Régis Jean-Gilles 优雅地回答了我之前在 CanBuildFrom 和丰富函数（又名“pimp my library”或“enrich my library”）中苦苦挣扎的问题：

在 Scala 中创建一个使用正确类型包装 map() 的隐式函数：不适合胆小的人

但这一次我遇到了一个更复杂的问题。

我有一个函数来实现变体intersectWith, 通过它们的键相交集合。我设法使它们像正确的收集功能一样工作：

现在，我目前也有非CanBuildFrom版本intersectBy和朋友，这些我无法作为CanBuildFrom版本工作。

到目前为止我能想到的最好的版本是这样的：

首先，我不明白为什么需要用可变缓冲区重写对map产生的调用；keyed_a似乎必须有更好的方法。但我仍然在底线得到同样的错误：

所以我的问题是：

1. 如何调用mapGenTraversableLike？
2. 如何使呼叫intersectWith正常工作？我知道我必须以某种方式传递CanBuildFrom基于我收到的那个，并且我知道关于mapResultBuilders，但我不确定在这里做什么，或者这是否可能。

的一个例子intersectBy，它与浮点数列表相交，如果它们的整数部分相同，则将两个数字视为相同，并计算绝对差：

（除了返回的类型应该是List[Double]）

谢谢你的帮助。

我正在尝试获取数组和向量的交集。我决定将它们都设为向量，因为 cplusplus.com 就是这样举个例子的。

这是我收到的错误消息：

这是我的代码：

该getNumbers()函数返回一个数组。

编辑

这是getNumbers()函数 - 它只返回相同返回类型的属性：

我试图弄清楚它是如何thrust::set_intersection工作的，但从我的测试结果来看，我对这个函数的作用更加困惑。

这里有几个例子：

返回2, 3, 4, 5

返回2, 3, 4, 5, 6

什么都不返回

我明白什么是默认值set_intersection作用，并且我同意结果，但是对于任何其他示例，我完全迷失了结果的来源？或者是怎么计算的？

知道这个算法是如何工作的吗？有人可以解释一下吗？

编辑：

我的目标是给定 2 组元组（假设大小为 2）：

所以我想在像 >< 这样的元组上定义 on 运算符，它返回所有满足运算符的元素：

><定义为a.first > b.first && a.second < b.second

所以答案只有 A[0] 和 B[0]。

所以你不能用set_intersection正确的方式实现这一点？

编辑答案： 没关系，我通过这些规则在这里找到了答案，这样的运算符不会是“严格的弱排序”运算符。