Bad design of C# collections framework. Where is the "Set" collection?

[Mart]

What class does everyone out there use if they want to store a set of values
efficiently?

In java I use a HashSet, but there is no equivalent in C#.

Even worse, the lowest level interface to define the Add, Contains and
Remove methods is an IList, and we all should know that a set isn't a list.
ICollection only defines Count and CopyTo, which isn't useful at all. So
even if I want to write my own Set implementation, what interface should I
implement?

There are literally dozens of features which make C# a better language than
java, but the collections framework is definitely a step backwards.

So, back to my original question, what does everyone else use? The easiest
solution is to use a Hashtable with null values, but that would have the
overhead of storing unnecessary DictionaryEntry objects.

Hope someone can enlighten me about the rational for this design

 

[Chris R. Timmons]

What class does everyone out there use if they want to store a
set of values efficiently?

In java I use a HashSet, but there is no equivalent in C#.

Even worse, the lowest level interface to define the Add,
Contains and Remove methods is an IList, and we all should know
that a set isn't a list. ICollection only defines Count and
CopyTo, which isn't useful at all. So even if I want to write
my own Set implementation, what interface should I implement?

There are literally dozens of features which make C# a better
language than java, but the collections framework is definitely
a step backwards.

So, back to my original question, what does everyone else use?
The easiest solution is to use a Hashtable with null values, but
that would have the overhead of storing unnecessary
DictionaryEntry objects.

Hope someone can enlighten me about the rational for this design

Matt,

I don't know about enlightenment, but I agree that the .Net framework
needs a Set datatype.

Until that happens, here's a solution:

http://www.codeproject.com/csharp/Sets.asp

I've used this in several apps and it works great.

Hope this helps.

Chris.

 

[Chris R. Timmons]

Mart,

Oops. That should have been addressed to "Mart", not "Matt".

Chris.

 

[Frans Bouma]

What class does everyone out there use if they want to store a set of
values efficiently?

ArrayList? Array? HashTable? SortedList? Own class derived from
CollectionBase?

In java I use a HashSet, but there is no equivalent in C#.

What does the HashSet do? Indexed access to hashed objects? Use
HashTable.

Also, .NET isn't java. Things are called differently, other
decisions have been made which have resulted in other objects which
combine functionality of perhaps 2 java classes or vice versa.

Even worse, the lowest level interface to define the Add, Contains and
Remove methods is an IList, and we all should know that a set isn't a
list. ICollection only defines Count and CopyTo, which isn't useful at
all. So even if I want to write my own Set implementation, what
interface should I implement?

you should derive from CollectionBase.

There are literally dozens of features which make C# a better language
than java, but the collections framework is definitely a step backwards.

Perhaps java has even more ready to use collection/set classes
however I think the ones in .NET are pretty solid.

So, back to my original question, what does everyone else use? The
easiest solution is to use a Hashtable with null values, but that would
have the overhead of storing unnecessary DictionaryEntry objects.

If you just want to store a set of values, use the ArrayList.
That's a dynamic scaling collection (hence the 'list' ;D ). If you want
a typed version, derive your class from ArrayList and override the
add/remove etc methods, but you can also inherit from CollectionBase which
is teh prefered method.

FB

 

[=?ISO-8859-2?Q?Marcin_Grz=EAbski?=]

Hi Mart,

"IDictionary" interface has properties which can be
used as "Set" properties. It's more similar to "Hashtable"
but i often use it as a simple set collection.

Only difference is that you don't need values, only keys.
Then you can by default set value to key (value).

e.g.

IDictionary myDict=new Hashtable();
string myKey="my unique key";
myDict.Add(myKey, myKey);

and the you can use "Contains" and "Remove" methods that
work as in "Set" interface.

Regards.

Marcin Grzêbski

 

[Ben]

So where is foreach in Java then!

 

[Rod O.]

Hey Ben,

In Java, foreach is written like this:

Given a Collection c filled with objects of type Point

for (Point point : c)
point.doSomething();

Admittedly, this is new to the language as are a few other additions
that are C#-like. But better late than never eh?

Cheers,

Rod O.

 

[Mart]

----- Original Message -----
From: "Frans Bouma" <[email protected]>
Newsgroups: microsoft.public.dotnet.languages.csharp
Sent: Tuesday, July 08, 2003 5:35 PM
Subject: Re: Bad design of C# collections framework. Where is the "Set"
collection?

ArrayList? Array? HashTable? SortedList? Own class derived from
CollectionBase?


What does the HashSet do? Indexed access to hashed objects? Use
HashTable.

As mentioned by other people in this thread, HashTable is an IDictionary,
which maps keys to values. A HashSet is simply a set of keys with no
ordering and no duplicates.
Using HashTable is a fudge, and the internal maintenance of "dummy" values
will have a performace impact.

Also, .NET isn't java. Things are called differently, other
decisions have been made which have resulted in other objects which
combine functionality of perhaps 2 java classes or vice versa.


you should derive from CollectionBase.

Firstly, deriving from "base" classes should only be used for convenience,
not to define functionality.
Secondly, BaseCollection implements IList as well, so it should really be
called ListBase ...another fault in the .NET collection framework.

Perhaps java has even more ready to use collection/set classes
however I think the ones in .NET are pretty solid.


If you just want to store a set of values, use the ArrayList.
That's a dynamic scaling collection (hence the 'list' ;D ). If you want
a typed version, derive your class from ArrayList and override the
add/remove etc methods, but you can also inherit from CollectionBase which
is teh prefered method.

The "add", "contains" and "remove" methods would be very inefficient for
large sets when implemented as an ArrayList.

 

[Mark Mullin]

You can use ArrayList or Array to do this

1) There's a sort member function that can be used to sort the
members
2) There's a BinarySearch member function that will perform a binary
search on a sorted ArrayList/Array.

This is going to be much faster than Hashtable searches on
equivalently sized lists, with 'much faster' growing exponentially
against # of sort elements.

 

[BS]

Sorting a list can never be faster than O(Nlog(N)). Binary search
runs in O(log(N)). In contrast, Hashtable insertion and lookup are
constant-time (given a large-enough table and a good hash function.)

No offense, but you got it exactly backwards.

 

[MikeB]

You can use ArrayList or Array to do this

1) There's a sort member function that can be used to sort the
members
2) There's a BinarySearch member function that will perform a binary
search on a sorted ArrayList/Array.

This is going to be much faster than Hashtable searches on
equivalently sized lists, with 'much faster' growing exponentially
against # of sort elements.

Hashtable search times don't grow exponentially with the number of
elements - that's the point of a Hashtable.

However, adding or removing elements from a sorted array or ArrayList does
cause major compute time increases when the number of elements grow.
Again - this is a behavior that Hashtables are designed to help avoid.

The original poster is simply looking for a Hashtable that contains only
keys - no associated values. He is correct that the .NET Framework does not
have one built in. I'd probably just use the framework's Hashtable class,
while always providing nulls for the value property. I'm guessing the
overhead for this would be negligible as compared to a custom made Hashset
class. If it turned out to be a problem, then it would be time to complain
and/or implement a custom Hashset.

 

[Mark Mullin]

I used exponentially incorrectly when I should have used (linear *
larger constant + some additional noise)

I did assume this was a one time sort and then the lists were used
strictly for lookup, not additions.

In such a case I believe binary search is faster than a hashtable.
Hashing simply divides a set of values into subsets, where each subset
is searched linearly. A perfect hash leaves the problem of moving
from the hash key space to the storage space. Size of the hash key
space defines the number of collisions and I can't remember my Knuth
here.

 

[bestsss]

C# Collection Framework

I've come from a Very solid practice (love) with Java Framework (having been a lead developer of an JDO impl, thus includes proxing of virtually all the java collection framework) but recently I've joined the dark side of the power (I hope I will leave it since it doesn't attracts me xD).

C# hardly has any Collection framework. It's similar to JDK 1.0.2 where only Hashtable and Vector existed (both syncronized, btw), adding Stack which extended Vector and fully abstract class Dictionary.

C# Collection Framework badly misses functionality and versatality. While it's true that java's HashSet/TreeSer wraps a HashMap/TreeMap C# blatantly skips any Set definition and jumps to slow lists when it comes to add/remove/search operations.

IDictionary defines the keys as a collection which is inheritanty incorrect.

Also something I can't forgive to a very recent language is the lack of the best (IMO) collection type - LinkedHashSet/Map.


To the discussion of hash vs binary search. Hashing is Usually faster and binary search is useful Only if the target List is an array type which completely prohibits any add/remove operations.

In the end I am not trying to blame C# for so poor functionality but if anyone reads to make it a tad better.

ICollection shall be enriched w/ add/remove/contains and Sets should be added - this is the bare minimum I'd like to see.

Regards.