Fog Creek Software
Discussion Board




Welcome! and rules

Joel on Software

Looking for a Set implementation

Seems like they overlooked an important collection type in designing the .NET collections framework, the Set.  Or at least I can't find it.  Anyone know where I can get a reasonable implementation of one, preferably based on hashing?  I've been using a HashMap with keys and values being the same object, but this bugs me.

my kingdom for a Set
Tuesday, February 17, 2004

Given the random order that data comes out of a set, what exact behavior are you after? Prevention of duplicates? It seems like one of the normal containers would be just fine, if that wasn't a requirement.

Brad Wilson (dotnetguy.techieswithcats.com)
Tuesday, February 17, 2004

What I'm basically after is the membership predicate supported by sets.  I'd like to add items to the set and be able to check if a given item is already a member of a set.  I'd also like to be able to enumerate the members of the set as well.

I'm sure I could make due with one of the other collections, but there are some clarity and performance considerations that have me wanting to use a more proper abstraction.  I'm currently using the hashmap, but it's grating on me :)

my kingdom for a Set
Tuesday, February 17, 2004

Could you give a specific example of a Set in another programming language?

Wayne
Tuesday, February 17, 2004

Smalltalk has a class called Set that does what I'd like.  Also, Recursion Software/ObjectSpace makes collections libraries for Java and .NET, each of which supports a Set abstraction.  Also, I think the original Booch components included Set abstractions of several stripes.  The Eiffel base libraries include a cluster called base.structures.set that provides a number of variations on the Set abstraction.

The basic idea is that the object supports insertion, removal, iteration, and very fast membership testing, and usually some cardinality functions like IsEmpty, NotEmpty, Count, etc. Most Sets also have the property that no duplicates appear in the collection - if you add an item multiple times, it only appears once in the collection.  Also, most basic Set implementations make no guarantees about the order in which elements appear in the collection.

My current need for this is to track a set of visited nodes as I traverse a graph so that I don't walk any cycles in the graph.  In this case, the performance of the membership test dominates the performance of the traversal algorithm.  I'm currently using .NET's Hashmap collection, but this requires at least twice the storage I'd expect to be using for this function, plus the implementation doesn't logically match the design.  It's curious to me that this abstraction was overlooked in the design of the .NET collections framework, especially given that many implementations of Dictionary abstractions are based on the Set type.

my kingdom for a Set
Tuesday, February 17, 2004

This might be what you're looking for:

Add Support for "Set" Collections to .NET
http://www.codeproject.com/csharp/sets.asp

Invoice:  One kingdom, net 30 days.  <g>

Robert Jacobson
Thursday, February 19, 2004

Thanks for the pointer.  Seeing little traffic here, I decided to just write my own and be done with it.  I think I'll still have a look at this one, though, and see what's what.

About the kingdom.... did I mention the F.O.B. origin shipping clause? :P

Thanks for taking the time to answer.

my kingdom for a Set
Thursday, February 19, 2004

*  Recent Topics

*  Fog Creek Home