Is there a collection among .NET collection that doesn't allow duplicates?
ArrayList is very suitable for what I need, except it allows duplicate values.
I've searched the System.Collections namespace but couldn't find anything alike.
Printable View
Is there a collection among .NET collection that doesn't allow duplicates?
ArrayList is very suitable for what I need, except it allows duplicate values.
I've searched the System.Collections namespace but couldn't find anything alike.
Couldn't find one myself so knocked up a simple implementation of Set
Thank you Norfy, very nice implementation.
I was going to implement a set anyway,
just wanted to check if there's already an implementation among .NET's collections.
No problem, just thought I would save you some typing.
For that alone could you 'rate this post'? :)
I would like to, but...
Quote:
You must spread some Reputation around before giving it to Norfy again.
Ah yes, multiple inheritance post ;)
Yes. :blush:Quote:
Originally Posted by Norfy
Quite simply, the behaviour of the keys collection of a Hashtable is that of a set.Quote:
Originally Posted by mehdi62b (Rating Comment)
For small sets then an IList is ok but for larger sets a Hashtable is quicker.
there are some interesting collections that NHibernate uses...
the DLL is Iesi.Collections.
I don't know the licensing policy, but i think they're ok generally. :)
we want to just look for in an collection and keys in hashtable are just an ICollection ...hastable is fast but when we give a key and want its item,well its time is O(1)Quote:
Originally Posted by Norfy
but when we want to get whether an item is included or not..
no difference between a hashtable(keys) and IList...(both of them are an ICollection)
both of them have O(n).
Sorry mehdi62b I couldn't follow your comment.
Whether you ask a Hashtable for a value or if it contains a key the access time is not linear O(n) , it uses hashing for both.
The keys are returned as an ICollection but are not implemented as such internally.
I meant when we ask a hashtable whetere it contains a key the time is not O(1)..I meant it doesn't use hashing...Quote:
Originally Posted by Norfy
and you tell it use hashing(how?) ..I don't know exactly..
no problem...should have a look at one of my book :wave:
Have you checked out Reflector yet?Quote:
Originally Posted by mehdi62b
Nice tool, lets you browse the (decompiled) core .NET libraries.
I will check that link :thumb:
Hi Norfy,
thank you very much for that link..I didn't know it..its very usefull tool
and yes,you were right..
public virtual bool Contains(object item);Declaring Type:System.Collections.ArrayList
and it clearly shows it has O(n)Code:public virtual bool Contains(object item)
{
if (item == null)
{
for (int num1 = 0; num1 < this._size; num1++)
{
if (this._items[num1] == null)
{
return true;
}
}
return false;
}
for (int num2 = 0; num2 < this._size; num2++)
{
if (item.Equals(this._items[num2]))
{
return true;
}
}
return false;
}
and to be countinued...
public virtual object this[object key] { get; set; }Declaring Type:System.Collections.Hashtable
and it should be O(1)Code:public virtual object this[object key]
{
get
{
uint num1;
uint num2;
Hashtable.bucket bucket1;
if (key == null)
{
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Hashtable.bucket[] bucketArray1 = this.buckets;
uint num3 = this.InitHash(key, bucketArray1.Length, out num1, out num2);
int num4 = 0;
do
{
int num5 = (int) (num1 % bucketArray1.Length);
bucket1 = bucketArray1[num5];
if (bucket1.key == null)
{
return null;
}
if (((bucket1.hash_coll & 0x7fffffff) == num3) && this.KeyEquals(key, bucket1.key))
{
return bucket1.val;
}
num1 += num2;
}
while ((bucket1.hash_coll < 0) && (++num4 < bucketArray1.Length));
return null;
}
set
{
this.Insert(key, value, false);
}
}
public virtual bool ContainsKey(object key);Declaring Type:System.Collections.Hashtable
and how similar to the perevious one!!and it should be O(1)Code:public virtual bool ContainsKey(object key)
{
uint num1;
uint num2;
Hashtable.bucket bucket1;
if (key == null)
{
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Hashtable.bucket[] bucketArray1 = this.buckets;
uint num3 = this.InitHash(key, bucketArray1.Length, out num1, out num2);
int num4 = 0;
do
{
int num5 = (int) (num1 % bucketArray1.Length);
bucket1 = bucketArray1[num5];
if (bucket1.key == null)
{
return false;
}
if (((bucket1.hash_coll & 0x7fffffff) == num3) && this.KeyEquals(bucket1.key, key))
{
return true;
}
num1 += num2;
}
while ((bucket1.hash_coll < 0) && (++num4 < bucketArray1.Length));
return false;
}
thank you very much :wave:
how about a real world test? i use a hashtable to weed out the lines of a text file, that are the same as the previous day's text file.. a bit like sql minus union..
a text file 4 megabytes big, with 100000 lines, is processed in about a second:
read all of file one into hashtable, using the whole line as the key, and null as the value
read file 2 and call ContainsKey repeatedly on the hashtable.. if the HT doesnt containskey the line being read, write it out to a third output file.
i htink my program is IO bound, as it takes just less than a second for files only a few hundred lines long...
so in a word.. yes there is a set/collection that disallows duplicate values: use a hashtable with the values you want to store as the Key, and NULL as the value.
ht.put(myValue, null)
or wrap this behaviour in a class called Set which is what the last few posts have been about. :)Quote:
so in a word.. yes there is a set/collection that disallows duplicate values: use a hashtable with the values you want to store as the Key, and NULL as the value.
ht.put(myValue, null)
How about simply implementing the CollectionBase class? it's pretty handy for these kind of stuff...
Sorry Andy but I don't think that is a good idea. CollectionBase gives you nothing more than an underlying list.
Anything to do with Set functionality you would have to write yourself, which with a basic implementation gives you something similar to
mehdi62b's solution.
Look at System.Collections.Generic.HashSet<T> generic class in .NET 3.5.
As a generic it is type-safe and avoids the boxing/unboxing operations if the "elements" are value types.