问题标签 [unordered-multiset]

假设我们有std::unordered_multiset两个映射相同哈希值的值，c++ 标准是否有任何保证 find 将返回第一个插入的元素？

为什么std::unordered_multiset插入的最坏情况复杂度是线性的？我理解为什么会出现这种情况std::unordered_set（您必须检查插入的值不在集合中）但对于多集我不明白。我错过了一些明显的东西吗？

我使用 C++ STL 已经有一段时间了，但从未真正开始使用多重集（或多重映射）。我有一个基于计算具有相同键的元素数量的问题。例如。这是一个 unordered_multiset {0, 2, 5, 1, 1, 2, 7, 5}

如果我说 count(5)，它应该返回 2。有两种方法可以使用 unordered_multiset 的 C++11 标准来实现。1)计数 2) equal_range然后减去生成的迭代器。

1）据说在出现次数上需要线性时间，但 2）是恒定时间。这是为什么？

我有这段代码：

所以它只是在一个unordered_multiset. 但是我发现我在哈希中的元素越多，这个工作的速度就越慢？我无法理解原因。在我看来，在应用哈希函数并找到相等元素的桶之后（因为所有相等的元素都组合在一起）stl 只需将它们放在桶的末尾。

那么这里有什么问题呢？

udp：我找到了 unordered_multiset::insert 函数的描述

单个元素插入：平均情况：常数。最坏的情况：容器大小呈线性关系。

所以现在的问题可以改写为：“为什么最坏的情况是线性的”

我想知道为什么有人会使用std::unordered_multiset. 我的猜测是它与插入/擦除后迭代器的失效或非失效有关，但也许它更深层次？非常相似的问题在这里：用例 std::multimap，但更多的是关于地图的讨论。

在C++ 标准表 91的§23.2.7 无序关联容器 [unord.req]中，描述了 STL 无序关联容器必须满足的附加要求。在此表中，标准规定 STL 无序容器（即 、和）必须提供成员类型和。unordered_setunordered_mapunordered_multisetunordered_multimaplocal_iteratorconst_local_iterator

• local_iterator 是一个迭代器类型，其类别、值、差异、指针和引用类型与无序容器的iterator. 此迭代器可用于遍历单个存储桶，但不能跨存储桶。
• const_local_iterator是一个迭代器类型，其类别、值、差异、指针和引用类型与无序容器的const_iterator. 此迭代器可用于遍历单个存储桶，但不能跨存储桶。

问

这些迭代器有什么用途？

我在代码中使用 unordered_multiset 有以下两个原因，

1. 应该很容易找到或查找数据。
2. 应该支持加载重复值。

unordered_multiset 通常比 multisets & vector 快得多，无论是插入还是查找，有时甚至是删除。

但不好的是，它占用了太多的内存。

我在 unordered_multiset 中存储了无符号的 __int64（8 字节）值，并正确清除了 unordered_multiset 中的值。谁能解释一下，为什么要占用内存以及如何解决这种内存消耗？

我希望能够对对象实例执行“数学”操作。假设我有一个课程，Fruit然后是附加课程。Orange(Fruit)Apple(Fruit)

Apple具有颜色属性，并且该类知道“红苹果”与“绿”或“黄”苹果不同的面孔。

现在我希望能够：

1) 表示特定水果实例的数量。例如 3 个红苹果或 2 个橙子或 1 个香蕉（是的，这可能需要一个新的香蕉类）。

2）代表“水果袋”。例如 1 个红苹果和 2 个橙子。或 1 个红苹果和 2 个橙子

3）按预期对“水果袋”和“水果数量”进行操作。即“2个红苹果”+“1个红苹果和1个橙子”=>“3个红苹果和1个橙子”甚至可能是“2个红苹果”* 2 =>“4个红苹果”等等。

现在，在某些方面它看起来类似于Counter该类的功能，但我不确定我应该如何实现它。

我在这里的基本困境是，该类似乎Counter根据它们的散列确定两个对象是否相同，并根据相同的散列进行分组，并且没有为我提供一个选项来决定分组“3 red”的键苹果”是“红苹果”。

我知道如何处理所有的数学重载问题，我想我可以从头开始实现它，但我希望有一些其他现成的解决方案可以支持这些概念。

实际的应用程序当然更复杂，但我认为我在这里描述的问题的解决方案很容易扩展到我的实际需求。

你会建议我采取什么方法？Counter 可以如何使用还是我需要自己完成完整的实现？

编辑 1：我真的很喜欢@jbndlr 关于“你说整数 w/值 3，而不是 3 个整数”的评论。但是有区别...

您如何将一个值为 1 的整数、一个值为 1 的整数和一个值为 4 的第三个整数一起计算？三个整数是正确的答案吗？或者也许是“2个整数整数w/值1和1个整数w/值4？

数数不像求和...

从某种抽象层面来看，它会根据事物的类型发送计数，这将迫使你在 '1 red_apple' 和 '1 apple which is red' 之间做出强烈区分，即 '1 red_apple' + '1 green_apple 只是 '1 red_apple + 1 green_apple' （因为 green_apple 与 red_apple 不同），而 '1 apple which is red' + '1 apple which is green' 可以认为是 '2 apples' （因为一个苹果任何其他颜色都会像苹果一样）

问题是，如果您的应用程序域要求您按颜色对苹果进行分组，您仍然不想被迫创建 3 个不同类别的苹果，您只想按颜色区分苹果实例。

这可能是我走错了路，决定如何计数的正确方法是由进行实际计数的人进行，以便您可以提供散列方案作为调用某些 CounterFactory 函数的一部分是否会返回一个计数器，该计数器知道他对任何提供的某种类型的对象实例的期望。

另一种选择是假设每种类型只能以某种特定方式可数，并且由类知道计算其实例的正确方法是什么，因此提供类似 __counting_key__ 的东西来支持向后兼容的方式来控制Counter 类的行为。

感谢所有出色的答案，我当然有足够的能力与之合作。我会接受看起来最接近我最终实际选择的解决方案的那个。

我想从 中删除特定元素std::unordered_multiset，但是当我尝试使用erase功能时，它会删除所有项目，无论它们有多少。
例如：

我希望这会先打印 3，然后再打印 2。但它会先打印 3，然后再打印 0。那么如何只删除一项？

我正在尝试提出一种算法，您可以在其中按顺序从一组中生成组合，以使它们的总和按递增顺序排列。该集合必须是多集合，即允许重复。

例如你有一个集合 S = {1,2,2,3,4,5,5}

因此，我不想根据项目数量生成所有组合（比如从 1 个和 2 个项目开始，最后是全部 7 个），我想按以下顺序计算它们：

{1}、{2}、{2}、{1,2}、{1,2}、{3}、{1,3}、{2,2}、{4}...... .......{1,2,2,3,4,5,5}

为什么这个顺序：我们可以看到这些子集的总和：

{1}、{2}、{2}、{3}、{3}、{3}、{4}、{4}、{4}.......{ 22}

你知道任何可以有效地做到这一点的算法吗？？？