c++ - 没有比较的多集？

Question

我想用来multiset计算一些自定义键。键在数字上不可比较，比较两个键没有任何意义，但可以检查它们的相等性。

我看到该multiset模板想要Compare订购多重集。顺序对我来说并不重要，重要的是数量。如果我完全省略Compare会发生什么？多重设置对我的自定义键没有任何问题吗？如果我不能使用std::multiset我的替代方案是什么？

Answer 1

如果您只能比较键是否相等，那么您不能使用std::multiset. 对于关联容器，您的键类型必须具有由比较操作强加的严格弱排序。

严格的弱排序不一定是数字的。

[对于在关联容器中使用，您实际上不需要相等比较。密钥等价由!compare(a, b) && !compare(b, a).]

如果您真的无法为您的键定义排序，那么您唯一的选择是使用键值对的序列容器并使用线性搜索进行查找。不用说，对于类似集合的操作，这将比 a 效率低，multiset因此您可能应该尽可能努力创建一个排序。

Answer 2

如果您完全省略Compare，它将获得默认值，即less（给出<应用于您的密钥的运算符的结果） - 它可能会或什至可能不会为您的密钥编译。

有一个排序的原因是它允许实现通过它们的键更快地查找元素（在插入、删除等时），要理解为什么，想象一下在字典中查找单词。传统字典使用字母顺序，这使得单词易于查找。如果你正在为一种不容易排序的语言准备字典——比如象形语言——那么要么很难在其中找到单词（你必须搜索整个字典），或者你' d 尝试找到一种合乎逻辑的方式对它们进行排序（例如，将所有可以用笔画的图片放在首位，然后是两条线，等等......） - 因为即使这个顺序是完全任意的，它也会使找到字典中的条目效率更高。

同样，即使您的密钥不需要为您自己的目的进行排序，并且没有任何自然顺序，您通常也可以定义一个足以解决这些问题的排序。排序必须是可传递的（如果a<b和b<c然后a<c），严格（从不返回真a<a），不对称（a<b并且b>a从不同时为真）。理想情况下，它应该对所有元素进行排序（如果a& 与orb不同），尽管您可以摆脱这不正确的情况（即严格的弱排序）——尽管这是相当技术性的。a<bb<a

事实上，也许它最明显的用途是完全不可能订购商品的罕见情况——在这种情况下，您可以提供一个始终返回 false 的比较运算符。这很可能会导致性能不佳，但至少会正常运行。

Answer 3

std::multiset如果您没有严格的弱排序，则无法使用。您的选择是：

1. 对您的数据实施严格-弱排序。如果您的键是“线性”数据结构，那么按字典顺序比较它通常是一个好主意。

2. 使用无序容器等价物，例如boost::unordered_multiset. 为此，您需要使您的自定义数据类型可散列，这通常比强加某种顺序更容易。

Answer 4

因此，您列出了两个重要标准。

1. 你不在乎订单
2. 键的比较没有任何意义

一个假设，

1. 您正在使用的事实multiset意味着有很多实例

那么，为什么不使用std::vectoror std::dequeorstd::list呢？然后您可以利用可以使用相等检查的各种算法（例如count_if等）