Containers.Hashed_Sets is a generic package that reclaims Element_Type, Hash function, Equivalent_Elements function and "=" function.
Why there is two functions to specify equivalence/equality?
generic
type Element_Type is private;
with function Hash (Element : Element_Type) return Hash_Type;
with function Equivalent_Elements (Left, Right : Element_Type)
return Boolean;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Hashed_Sets is
According to the Rationale for Ada 2005, "=" is only used for comparing whole sets for equality.
If you think about a set of Persons where you want to search by - for example - year of birth, two distinct Persons with the same year of birth would have other attributes (e.g. favourite programming language) which might differ. In this case, Equivalent_Elements would only compare the year of birth of Left and Right; and Hash would compute its result based only on the year of birth. "=", on the other hand, would compare the whole record.
I can understand some use, but this API doesn’t make sense for me. Hashed_Sets use two equivalence relations, named Equivalent_Elements and “=” (with some conditions between them). It could be possible to named it Equivalent_Elements_1 and Equivalent_Elements_2. Two equivalence relations can help in some cases, but only one is necessary to define the set structure. After all, why not three or more equivalence relations, that also can be useful in particular cases. Moreover why two equivalence relations for Hashed_Sets but only one for Ordered_Sets? https://docs.adacore.com/live/wave/arm12/html/arm12/arm12-A-18-9.html
If you want to add an item to a hashed set, you first find the hash bucket (which is where all equivalent items end up) and then search the associated “list” to see if one of the existing items is equal (as implemented by "="; they may not be bit-for-bit identical). If so, skip; if not, append the new item.
If two values are equal, they must be equivalent; the reverse is not true.
Similarly, ordered sets have two relations ("<" and "=").
“If you want to add an item to a hashed set, you first find the hash bucket”
I think this is the role of the Hash function, not of an equivalence relation.
“Similarly, ordered sets have two relations ("<" and "=").” Hashed_Sets have Hash and Equivalent_Elements. There is no real reason to have extra "=".
The actual function for the generic formal function Hash is expected to return the same value each time it is called with a particular element value. For any two equivalent elements, the actual for Hash is expected to return the same value. If the actual for Hash behaves in some other manner, the behavior of this package is unspecified.
I think I have to agree that we didn’t need Equivalent_Elements - the only use seems to be in Equivalent_Sets, which I fail to see the point of. But, I say again, elements may be equivalent without being equal.
I also agree that Equivalent_Elements is really obscure (and basically, since I can never remember its role, I always set it to “=” ).
I guess newer versions of Ada could somehow make it be equal to “=” by default (since it is of course way too late to remove it), though I don’t think there’s a current syntax in the language that make that possible.
).