问题标签 [multiset]

我在另一个关于std::multiset的问题中问过，但现在我发现我需要一个体面的理解，并且在互联网上找不到任何更复杂的例子。

你能向我解释一下，也许可以举例说明std::multiset<A,B>，A 和 B 的工作原理和功能是什么，以及是否可以省略其中的任何一个？我可以将 A 或 B 放入某个变量吗？我真的很感激一些简短的例子或参考，

我想打印出多重集中的每个重复项，但不知何故迭代器对我来说表现得很奇怪。如何修复此代码？这段代码导致了一个永远的循环，这让我感到惊讶。

编辑 我在周期结束时添加了一个 --it

下面对 TEST_FUNCTION 的调用失败，并显示“ORA-03113：通信通道上的文件结尾”。TEST_FUNCTION2 中提供了一种解决方法。我将代码归结为我的实际功能要复杂得多。在 Oracle 11G 上测试。任何人都知道为什么第一个功能会失败？

是否可以在多集（值可以重复）上在 O(n) 中执行搜索第 k 个元素？

因为据我了解快速选择的想法，我必须使用一些枢轴对输入进行分区。然后我有 2 个数组，我选择用于递归搜索取决于我正在搜索的索引元素 + 两个数组的大小，例如：

1 7 8 5 3 2 4

假设枢轴是 4 我正在搜索第二大元素。所以分区后我可能会得到类似的订单

1 3 2 4 7 8 5

因为右子数组由 3 个元素组成，如果我是正确的，我仍然会尝试在右数组中找到第二大元素？

但是，如果我以 8 作为支点，我可能会得到类似的东西

1 3 2 7 5 4 8

因此我会尝试在左表中找到最大的元素（可能是线性的，但通常我会采用左子数组并搜索元素 - (|右子数组大小| + 1)）

但是多集呢？假设我有数组：

4 5 6 7 7 7 4 3 2 1

我的支点是 6 搜索第三大元素，分区后我收到：

4 5 3 2 4 1 6 7 7 7

所以如果我使用上面介绍的方法，我将尝试在右子数组上执行递归，而很明显第三个最大值是左边的 5？

我想出的唯一解决方案是使用一些数据结构（如 BST、Set 等）来 O(nlogn) 过滤掉重复项。然后使用 O(n) 快速选择。但是总的来说，它会给我非线性方法，这可以线性完成吗？

我还有一个额外的问题，如果无法分配内存怎么办？我能做的就是只使用本地整数+堆栈递归。这个问题可以在 O(n) 中解决吗？因为 O(nlogn) 可以通过排序 + 线性“通过计数”来完成。

只是为了好玩，我实现了可以想象的最简单的排序算法：

它只比std::sort我的测试数据慢 20 倍 :)

接下来，我想通过移动语义来提高性能：

但这并没有显着影响性能，即使我正在排序std::strings。

然后我记得关联容器从外部来看是恒定的，也就是说，std::move并且std::copy会在这里做同样的事情:(还有其他方法可以将数据移出树吗？

我需要在一个文件中存储大量整数。整数的顺序无关紧要，所以总信息量应该低于有序列表。有没有比任意排序的数组更节省空间的方法来存储数字？

编辑：我假设整数是完全随机的。我真的在寻找一种通用的方法来挤出通过修复排列引入的冗余信息。

我有一个 multiset mymulti 我根据类成员排序m_a。

然后我想检查所有排序的元素，如果m_a相邻字段的差异mymulti小于我给定的阈值，比如 0.001。如果是这样，那么我想更喜欢另一个类成员 m_b 较小的那个。

在这里我被卡住了，我没有使用多重集或迭代器的经验。我不知道如何比较两次迭代的迭代器。如果您能为我提供正确的代码，我将不胜感激！我的尝试，不是太多，只是我的概念：

我试图以这样的方式根据其两个成员对类对象进行排序：根据成员排序。如果两个对象具有相同的值（或者如果差异低于某个阈值），则根据成员b进行搜索。我正在使用multiset。

问题是，当另一个对象到来时，根据排序类进行检查，并满足返回 true （被放置在比被比较的对象更高的位置），它也可能在另一个更高一级的情况下满足。我如何在这里介绍，它应该检查尽可能多的先前对象，并且尽可能高？（获得排序良好的多重集！）下面是我编写排序类的方式。请给我一些好主意！

我在为这部分代码引入缩进时遇到了问题，任何人都可以帮我编辑吗？这是不可读的。

编辑：

粘贴这个，看看我想要什么，不能实现。如果 m_a 相同，我希望它随着 m_a 增加而随着 m_b 减少（你可以把相等或不等放在那里，也不起作用）

我可以在 Oracle 11g 中做这样的事情吗：

在普通 sql 中，没有预定义类型？它是否支持多态性之类的东西？

我在 Scala 中尝试了 Facebook Hacker Cup 2013 资格问题，对于第三个问题，我觉得需要一个有序的 Multiset，但在 scala (2.10) 的集合中找不到。scala 的集合中是否缺少此数据结构。它会在未来的版本中实现吗？如果您已经实现了一个集合，那么 Multiset 是否真的不需要？