Re: Equivalent keys/elements in Ada.Containers Maps and Sets

["Matthew Heaney" <mheaney@on2.com>]

Matthew Heaney wrote:
> Niklas Holsti wrote:
> >
> > One point where this may be significant is the definition of the "="
> > operator on Sets in A.18.7(20/2). The definition requires each element
> > of the Left set to be compared for "=" with the elements of the Right
> > set. If the actual "=" function is unrelated to the Hash function or to
> > the "<" operator for elements, I don't see how the "=" operator on Sets
> > can be implemented in less than O(N**2) complexity.
>
> No, your premise is false.
>
>   E1 = E2 => Hash (E1) = Hash (E2)
>
> Equality is always O(1).  There are no operations that are O(N**2).
                              ^^^^^^

Oops!  I meant to say that equality is always O(n).   

-Matt