我想使用 multiset 来计算一些自定义定义的键。键在数字上不可比较，比较两个键没有任何意义，但可以检查它们的相等性。
我看到 multiset 模板需要一个 Compare 来订购多重集。顺序对我来说并不重要，只有计数才重要。如果我完全省略 Compare 会发生什么？我的自定义键的多重设置是否没有任何问题？如果我不能使用 std::multiset 我有什么选择？
I want to use multiset to count some custom defined keys. The keys are not comparable numerically, comparing two keys does not mean anything, but their equality can be checked.
I see that multiset template wants a Compare to order the multiset. The order is not important to me, only the counts are important. If I omit Compare completely what happens? Does multiset work without any problems for my custom keys? If I cannot use std::multiset what are my alternatives?
发布评论
评论（4）
如果您只能比较键是否相等，则不能使用 std::multiset。对于关联容器，您的键类型必须具有由比较操作强加的严格弱排序。
严格弱排序不一定必须是数字。
[对于在关联容器中使用，您实际上不需要相等比较。键等效性由
!compare(a, b) && 确定!compare(b, a).]如果您确实无法为键定义顺序，那么您唯一的选择是使用键值对的序列容器并使用线性搜索查找。不用说，对于类似集合的操作来说，这比多重集的效率要低，所以如果可能的话，您应该努力创建一个排序。
If you can only compare keys for equality then you cannot use
std::multiset. For associative containers your key type must have a strict weak ordering imposed by a comparison operation.The strict weak ordering doesn't necessarily have to be numerical.
[For use in an associative container, you don't actually need an equality comparison. Key equivalence is determined by
!compare(a, b) && !compare(b, a).]If you really can't define an ordering for your keys then your only option is to use an sequence container of key-value pairs and use an linear search for lookup. Needless to say this will be less efficient for set like operations than a
multisetso you should probably try hard to create an ordering if at all possible.如果没有严格的弱排序，则不能使用 std::multiset。您的选择是：
对您的数据实施严格弱排序。如果您的键是“线性”数据结构，则通常最好按字典顺序对其进行比较。
使用等效的无序容器，例如
boost::unordered_multiset。为此，您需要使自定义数据类型可散列，这通常比强加某种顺序更容易。You cannot use
std::multisetif you don't have a strict weak ordering. Your options are:Impose a strict-weak ordering on your data. If your key is a "linear" data structure, it is usually a good idea to compare it lexicographically.
Use an unordered container equivalent, e.g.,
boost::unordered_multiset. For that, you will need to make your custom data-type hash-able, which is often-times easier than imposing some kind of order.如果完全省略
Compare，它将获得默认值，即less（这给出了应用于<运算符的结果）你的密钥） - 它可能会也可能不会编译为你的密钥。进行排序的原因是它允许实现通过键更快地查找元素（插入、删除等时），要理解原因，想象一下在字典中查找单词。传统词典使用字母顺序，这使得单词易于查找。如果你正在为一种不容易订购的语言准备一本字典 - 比如象形语言 - 那么要么很难在其中找到单词（你必须搜索整个字典），要么你'尝试找到一种合乎逻辑的方式来对它们进行排序（例如，将所有可以用一笔画出来的图片放在前面，然后是两条线，等等......） - 因为即使这个顺序是完全任意的，它也会使查找字典中的条目效率更高。
同样，即使您的密钥不需要出于您自己的目的进行排序，并且没有任何自然顺序，您通常也可以定义一个足以解决这些问题的顺序。排序必须是传递的（如果
a 和 b 则 a），并且严格（对于 永远不会返回 true >a），不对称（ a 和 b>a永远不会同时成立）。理想情况下，它应该对所有元素进行排序（如果a和b不同，则a 或 b >），尽管你可以逃避这不是真的（即严格的弱排序） -虽然这相当技术性。 事实上，也许它最明显的用途是完全不可能订购商品的罕见情况 - 在这种情况下，您可以提供一个始终返回 false 的比较运算符。这很可能会导致性能不佳，但至少会正常运行。
If you omit the
Comparecompletely, it will get the default value, which isless(which gives the result of the<operator applied to your key) - which may or may not even compile for your key.The reason for having an ordering is that it allows the implementation to look up elements more quickly by their key (when inserting, deleting etc), To understand why, imagine looking words up in a dictionary. Traditional dictionaries use alphabetical order, which makes words easy to look up. If you were preparing a dictionary for a language that isn't easily ordered - say a pictographic language - then either it would be very hard to find words in it at all (you'd have to search the whole dictionary), or you'd try to find a logical way to order them (e.g. by putting all the pictures that can be drawn with one pen stroke first, then two lines, etc...) - because even if this order was completely arbitrary, it would make finding entries in the dictionary far more efficient.
Similarly, even if your keys don't need to be ordered for your own purposes, and don't have any natural order, you can usually define an ordering that is good enough to address these concerns. The ordering must be transitive (if
a<bandb<cthena<c), and strict (never return true fora<a), asymmetric (a<bandb>anever both true). Ideally it should order all elements (ifa&bare different then eithera<borb<a), though you can get away with that not being true (ie a strict weak ordering) - though that's rather technical.Indeed, perhaps the most obvious use for it is the rare case where it is completely impossible to order the items - in which case you can supply a comparison operator which always returns false. This will very likely result in poor performance, but will at least function correctly.
所以你列出了两个重要的标准。
，假设
multiset的事实意味着有很多实例所以，为什么不使用
std::vector或std::deque或std::list？那么您可以利用可以使用相等性检查的各种算法（例如count_if等）So you have two important criteria which you listed.
and one assumed,
multisetimplies that there are many instancesSo, why not use
std::vectororstd::dequeorstd::list? then you can take advantage of the various algorithms that can use the equality check (such ascount_ifetc.)