Element type

Operations required

• Copy (required for all containers)
• Equality test (required for sets and for dictionary keys)
• Less-than or equal test (required for balanced tree implementations for sets and dictionary)
• Hash function (required for hash table implementations for sets and dictionary)

Equality test

Necessary whenever a collection is asked if it contains a given element (or at which position it is, or what value is assigned to it as a key). A collection contains an element if that element is equal - according to the equality test - with the given one.

Requirements:

• a==b keeps the same value at each evaluation, as long as a and b keep the same values. In other words, the equality test is a pure function.
• After assigning a=b, we have a==b.
• a==a (reflexivity).
• If a==b, then b==a (symmetry).
• If a==b, and b==c then a==c (transitivity).

Less-than or equal test

Requirements:

• If a==b, then a<=b; this also means that a<=a (reflexivity)
• If a<=b and b<=c then a<=c (transitivity).
• If a<=b and b<=a then a==b (antisymmetry).

Hash function

This will be discussed later, when discussing about hash tables.