Multiset without Compare?

Question

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?

Answer 1

You cannot use std::multiset if you don't have a strict weak ordering. Your options are:

1. 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.

2. 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.

Answer 2

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 multiset so you should probably try hard to create an ordering if at all possible.

Answer 3

If you omit the Compare completely, it will get the default value, which is less (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<b and b<c then a<c), and strict (never return true for a<a), asymmetric (a<b and b>a never both true). Ideally it should order all elements (if a & b are different then either a<b or b<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.

Answer 4

So you have two important criteria which you listed.

1. You don't care about order
2. comparison of keys do not mean anything

and one assumed,

1. the fact that you are using multiset implies that there are many instances

So, why not use std::vector or std::deque or std::list? then you can take advantage of the various algorithms that can use the equality check (such as count_if etc.)