Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Comparing Sets

There is a special family of operators for comparing sets. Consider two sets, say S and T. We say that S is a subset  of T, written tex2html_wrap_inline63372, if every element of S is also an element of T. If there is at least one element of T that is not also an element of S, we say that S is a proper subset   of T, written tex2html_wrap_inline67364. We can also reverse the order in which the expressions are written to get tex2html_wrap_inline67366 or tex2html_wrap_inline67368, which indicates that T is a (proper) superset    of S.

The set comparison operators follow the rule that if tex2html_wrap_inline63372 and tex2html_wrap_inline63374 then tex2html_wrap_inline67378, which is analogous to a similar property of numbers: tex2html_wrap_inline67380. However, set comparison is unlike numeric comparison in that there exist sets S and T for which neither tex2html_wrap_inline63372 nor tex2html_wrap_inline63374! E.g., clearly this is the case for tex2html_wrap_inline67390 and tex2html_wrap_inline67392. Mathematically, the relation tex2html_wrap_inline67394 is called a partial order  because there exist some pairs of sets for which neither tex2html_wrap_inline63372 nor tex2html_wrap_inline63374 holds; whereas the relation tex2html_wrap_inline59841 (among integers, say) is a total order.

Program gif overloads the operators == and <= for SetAsArray operands. The former tests its operands for equality and the latter determines whether the relation tex2html_wrap_inline67394 holds between its operands. Both operators return a Boolean result. The worst-case running time of each of these operations is clearly O(N).

   program28356
Program: SetAsArray Class Comparison Operator Definitions

A complete repertoire of comparison operators would also include definitions for <, >, >= and !=. These operations follow directly from the implementation shown in Program gif (Exercise gif).


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.