问题标签 [multiset]

我正在比较 STL (g++) priority_queue 的性能，发现 push 和 pop 没有我预期的那么快。请参阅以下代码：

我编译了这个 -O3 然后运行 ​​valgrind --tool=callgrind，KCachegrind testMap 占 CPU 总量的 54% testPriorityQueue 占 CPU 的 44%

（不带-O3 testMap比testPriorityQueue快很多）调用testPriorityQueue似乎占用大部分时间的函数

该函数似乎是从 pop() 调用中调用的。

这个函数具体是做什么的？有没有办法通过使用不同的容器或分配器来避免它？

我有两个字符串，我希望它们上有交叉点，包括重复项：

我想让它返回：

有任何想法吗？

我试图从一组向量中打印出每个向量中的所有元素。构建失败，但错误发生在头文件的某处，恐怕我根本不了解错误代码。任何帮助将不胜感激！这是错误：

这是导致问题的代码。

是否可以使用管道计算 redis 中的多集操作，即说

(a union b union c) intersect (d union c) SUNION abc SINTER dc

显然你可以做任何一个，但前者更常见。

你为什么会选择后者，它是如何工作的？

我读到这个：http ://www.drdobbs.com/cpp/stls-red-black-trees/184410531 ；这让我觉得他们做到了。它说：

insert_always 是一个状态变量，它告诉 rb_tree 是否允许同一键值的多个实例。此变量由构造函数设置，并由 STL 用于区分 set 和 multiset 以及 map 和 multimap。set 和 map 只能出现一次特定键，而 multiset 和 multimap 可以出现多次。

虽然现在我认为这并不一定意味着。他们可能仍在使用容器。

我认为具有相同键的所有节点都必须排成一行，因为您必须将所有具有相同键的节点存储在右侧或左侧。因此，如果您将相等的节点存储在右侧并插入 1000 个 1 和一个 2，那么您基本上会有一个链表，这会破坏红黑树的属性。

为什么我找不到太多关于它的原因是它只是一个坏主意？

我想在多重集中插入​​一个整数值和一对。

所以我将其声明为：

要插入 multiset 我试过这个：

但它给出了编译时错误......有人可以建议正确的方法来实现它。

我有一个 std::multiset 排序的自定义对象。多重集中的两个相等对象（基于 < 运算符）可能包含一些不相等的字段。在这种情况下，我需要保持在 multiset<> 中插入对象的顺序。

我知道如果我使用的是 C++11，这不是问题，但目前还不是。

我看到的另一个解决方案使用类中的时间戳字段 using <ctime>，但分辨率为 1 秒。如果我在同一秒内有 2 次插入，那么我不能在比较操作中使用时间戳。我们没有/不能在这个项目上使用 boost::chrono。

我可以使用另一种方法来确保维护插入顺序吗？

我想知道 guava 的 multiset 和 multipmap 与 JDK 的 List 和 Map 在 1. 时间性能和 2. 内存消耗方面哪个更好

谁能解释一下番石榴的时间和记忆性能？

Java 有 multiset，SmallTalk 有 Bag 类，据说它们的功能相同：保留一组值，但允许多个值（每个值都有一个计数）。

但似乎多重集可以通过一个对键进行计数的哈希表来实现（或者可能还有其他可能的实现）。

多重集或包的某些实现是否提供比上述哈希更好的时间复杂度？所需的操作可以是

1. 插入项目
2. 删除项目
3. 获取集合中的最小值
4. 获取集合中的最大值

特别是，我希望对于上述 4 个操作中的每一个，它都可以做得比O(n)，可能全部O(log n)或更好。O(log n)（上面的 3 和 4仅在当添加或删除值时以某种排序方式维护多重集时才预期。）

我想问你一个提示，因为我是初学者，在互联网上找不到任何合适的答案。我收到此错误： 调试断言失败 - map/set iterator not dereferencable 在如下所示的行：

使用pointNext()函数，我看到一切正常，而关于active，我有：

更多信息：

活动是多集< classA, classB::classC >::const_iterator

setS有：setS.Q、setS.W、setS.T和setS.data，其中setS.data在方括号内有 0。当我在 .cpp 文件中有多重迭代器声明时，在调试期间我无法进入以查看内部活动的内容，当它在 .h 文件中时，我可以。

在 .cpp 我不能进入active，所以可以想象它就像指针（迭代器）不能取消引用，因为里面是错误的。如果它是空的，即setS.data是空的怎么办？或者里面是否有垃圾？

我知道这个东西以前在 linux 下运行，是否有一些我必须更改才能在 Windows 上运行的功能？例如将多个模板参数更改为一个？（正确地将setS.data归因于active，因为我不确定 - 我做得对吗？

很抱歉这个相当混乱的帖子，我想添加我的猜测，如果他们错了，我会忽略他们。如果这里有什么不清楚或缺少一些信息，我很乐意补充。你能告诉我什么原因可能导致我得到解引用错误，我应该在哪里寻找它？因为我被卡住了，不知道如何进行。

非常感谢任何帮助，谢谢！