Representation for Set
Posted on 2000-04-09
I'm translating a language to C++.The language has direct support for sets of any type, where a set is a collection with no duplicates, and has union and intersection done on it. I need to write a template for it. The language provides defining equality between two objects of same type. There need not exist any comparison (except for equality) between elements of a set.
I can't use hashing, since I can't assume that obects which give "true" on equality tests will hash to the same value. I am looking for an efficient representation, especially for union and intersection.
Any help will be greatly appreciated. Thank you very much.