|
Bug in this[object key] set property
|
|
|
|
|
Did you see the article entitled "STL-Compatible Hybrid of Linked List & Hash Map" in the August 2005 issue of Dr. Dobbs Journal?
|
|
|
|
|
Hello Marc, I took your ideas and played around with another class (HashtableList) that derives directly from Hashtable just to see how the inheritance route would work. I did not make it as elaborate as you did but it works for what I needed, which was a simple way to preserve the order of the entries. When I looked at your code, I did not want the overhead you added ; granted I may be missing some important aspect that you added but I could not think of anything since DictionaryEntry is a struct and its a pain to update the reference anyway.
I thought I would instead just keep a single keyList (ArrayList) and reference the hashtable as I needed to. I tested with a basic driver stub (bottom) - if anyone sees problems with this or can add to it for more array like support please email me, see comments for info.
I'll try to paste the VB code here (I would have used C# as my preference but my project is VB).
Imports System.Collections
Module Module1
' HashtableList - derives from Hashtable and adds fixed ArrayList enumeration of objects
' based on the order that they were added, unlike Hashtable, SortedList, etc.
' Until Generics/Templates, this will serve its purpose. Acts more like hashtable than arraylist.
' 01 Feb 2005 Marty Spallone / Blue Object Software, LLC., martyone(nospam)@snet.net
' Much code and ideas borrowed from Marc Clifton, Code Project 01 Feb 2005
'
Class HashtableList
Inherits System.Collections.Hashtable
Private keyList As ArrayList = New ArrayList
Public Overrides Sub Add(ByVal key As Object, ByVal value As Object)
MyBase.Add(key, value)
keyList.Add(key)
End Sub
Public Overrides Sub Remove(ByVal key As Object)
keyList.RemoveAt(IndexOf(key)) ' Remove me first!
MyBase.Remove(key)
End Sub
Public Overrides Sub CopyTo(ByVal array As System.Array, ByVal index As Integer)
End Sub
Public Overrides Function GetEnumerator() As System.Collections.IDictionaryEnumerator
Return New KeyedListEnumerator(keyList, Me)
End Function
Public Overloads ReadOnly Property Keys() As ICollection
Get
Dim retkeyList As New ArrayList
Dim i As Integer
For i = 0 To keyList.Count - 1
retkeyList.Add(keyList(i))
Next i
Return retkeyList
End Get
End Property
Public Overloads ReadOnly Property Values() As ICollection
Get
Dim retkeyList As New ArrayList
Dim i As Integer
For i = 0 To keyList.Count - 1
retkeyList.Add(MyBase.Item(keyList(i)))
Next i
Return retkeyList
End Get
End Property
Private Function IndexOf(ByVal key As Object) As Integer
Dim i As Integer
For i = 0 To keyList.Count - 1
If (keyList(i) = key) Then
Return i
End If
Next i
Return -1
End Function
Public Overloads ReadOnly Property IsSynchronized() As Boolean
Get
Return False
End Get
End Property
End Class
Public Class KeyedListEnumerator
Implements IDictionaryEnumerator
Private index As Integer = -1
Private objs As ArrayList ' access to the consumer's arraylist
Private ref As IDictionary ' access to the consumer's hashtable
Friend Sub New(ByVal list As ArrayList, ByVal refHT As IDictionary)
objs = list
ref = refHT
End Sub
Public Function MoveNext() As Boolean Implements IDictionaryEnumerator.MoveNext
index += 1
If index >= objs.Count Then
Return False
End If
Return True
End Function
Public Sub Reset() Implements IDictionaryEnumerator.Reset
index = -1
End Sub
Public ReadOnly Property Current() As Object Implements IDictionaryEnumerator.Current
Get
If index < 0 Or index >= objs.Count Then
Throw New InvalidOperationException
End If
Return objs(index)
End Get
End Property
Public ReadOnly Property Entry() As DictionaryEntry Implements IDictionaryEnumerator.Entry
Get
Return New DictionaryEntry(Current, ref(Current))
End Get
End Property
Public ReadOnly Property Key() As Object Implements IDictionaryEnumerator.Key
Get
Return Entry.Key
End Get
End Property
Public ReadOnly Property Value() As Object Implements IDictionaryEnumerator.Value
Get
Return Entry.Value
End Get
End Property
End Class
Sub Main()
Dim htl As HashtableList = New HashtableList
htl.Add(1100, "Pluto as we know it")
htl.Add(200, "might not be")
htl.Add(201, "a planet")
htl.Remove(201)
htl.Add(206, "an asteroid")
For Each key As Integer In htl.Keys
Console.WriteLine("Original {0}, Value {1}", key, htl(key).ToString())
Next
Dim i As IDictionaryEnumerator = htl.GetEnumerator
While (i.MoveNext)
Console.WriteLine("Using GetEnumerator {0}, Value {1}", i.Key, i.Value.ToString())
End While
For Each key As Integer In htl.Keys
Console.WriteLine("Pass 3 {0}, Value {1}", key, htl(key).ToString())
Next
Console.WriteLine("Completed")
End Sub
End Module
Marty Spallone
Blue Object Software, LLC
www.blueobject.net
|
|
|
|
|
I forgot to include the CopyTo sub.
Public Overrides Sub CopyTo(ByVal array As System.Array, ByVal index As Integer)
For Each key As Object In keyList
array(index) = MyBase.Item(key)
index = index + 1
Next
End Sub
|
|
|
|
|
Working version here (sorry for the large post and mistakes).
Imports System.Collections
Namespace {Your NameSpace}
' HashtableList - derives from Hashtable and adds fixed ArrayList enumeration of objects
' based on the order that they were added, unlike Hashtable, SortedList, etc.
' Until Generics/Templates, this will serve its purpose. Acts more like hashtable than arraylist.
' 01 Feb 2005 Marty Spallone / Blue Object Software, LLC., martyone(nospam)@snet.net
' Much code and ideas borrowed from Marc Clifton, Code Project 01 Feb 2005
'
' 01 Feb 2005 - Added CopyTo()
'
Public Class HashtableList
Inherits System.Collections.Hashtable
Private keyList As ArrayList = New ArrayList
Public Overrides Sub Add(ByVal key As Object, ByVal value As Object)
MyBase.Add(key, value)
keyList.Add(key)
End Sub
Default Public Overloads Property Item(ByVal key As Object) As Object
Get
Return MyBase.Item(key)
End Get
Set(ByVal Value As Object)
If keyList.Contains(key) Then
MyBase.Item(key) = Value
Else
Me.Add(key, Value)
End If
End Set
End Property
Public Overrides Sub Remove(ByVal key As Object)
keyList.RemoveAt(IndexOf(key)) ' Remove me first!
MyBase.Remove(key)
End Sub
Public Overrides Sub CopyTo(ByVal array As System.Array, ByVal index As Integer)
Dim o As ArrayList = New ArrayList(keyList.Count)
For Each key As Object In keyList
o.Add(MyBase.Item(key))
Next
o.CopyTo(array, index)
End Sub
Public Overrides Function Clone() As Object
Dim htl As HashtableList = New HashtableList
For Each key As Object In Me.keyList
htl.Add(key, MyBase.Item(key))
Next
Return htl
End Function
Public Overrides Function GetEnumerator() As System.Collections.IDictionaryEnumerator
Return New KeyedListEnumerator(keyList, Me)
End Function
Public Overloads ReadOnly Property Keys() As ICollection
Get
Dim retkeyList As New ArrayList
Dim i As Integer
For i = 0 To keyList.Count - 1
retkeyList.Add(keyList(i))
Next i
Return retkeyList
End Get
End Property
Public Overloads ReadOnly Property Values() As ICollection
Get
Dim retkeyList As New ArrayList
Dim i As Integer
For i = 0 To keyList.Count - 1
retkeyList.Add(MyBase.Item(keyList(i)))
Next i
Return retkeyList
End Get
End Property
Private Function IndexOf(ByVal key As Object) As Integer
Dim i As Integer
For i = 0 To keyList.Count - 1
If (keyList(i).Equals(key)) Then
Return i
End If
Next i
Return -1
End Function
Public Overloads ReadOnly Property IsSynchronized() As Boolean
Get
Return False
End Get
End Property
End Class
Friend Class KeyedListEnumerator
Implements IDictionaryEnumerator
Private index As Integer = -1
Private objs As ArrayList ' access to the consumer's arraylist
Private ref As IDictionary ' access to the consumer's hashtable
Public Sub New(ByVal list As ArrayList, ByVal refHT As IDictionary)
objs = list
ref = refHT
End Sub
Public Function MoveNext() As Boolean Implements IDictionaryEnumerator.MoveNext
index += 1
If index >= objs.Count Then
Return False
End If
Return True
End Function
Public Sub Reset() Implements IDictionaryEnumerator.Reset
index = -1
End Sub
Public ReadOnly Property Current() As Object Implements IDictionaryEnumerator.Current
Get
If index < 0 Or index >= objs.Count Then
Throw New InvalidOperationException
End If
Return objs(index)
End Get
End Property
Public ReadOnly Property Entry() As DictionaryEntry Implements IDictionaryEnumerator.Entry
Get
Return New DictionaryEntry(Current, ref(Current))
End Get
End Property
Public ReadOnly Property Key() As Object Implements IDictionaryEnumerator.Key
Get
Return Entry.Key
End Get
End Property
Public ReadOnly Property Value() As Object Implements IDictionaryEnumerator.Value
Get
Return Entry.Value
End Get
End Property
End Class
End Namespace
|
|
|
|
|
in method public object this[object key]
the line reading
objectTable[IndexOf (key)] = new DictionaryEntry (key, value);
should read
objectList[IndexOf (key)] = new DictionaryEntry (key, value);
Jakob Røjel
|
|
|
|
|
Thanks for the code. I tried to convert it to vb.net but encounterd two problems. If I kept the Namespace System.Collections then it would not let me add the implements information to the members. This is a bit odd and I would love to be edified. The Secon and harder for me to understand is that is the two GetEnumerator members. They are conflicting with one another. I would greatly appreciate it if someone could explain this to me.
I am putting the code in this message. Hopefully it will fit.
Imports System
Imports System.Collections
'Namespace System.Collections
Public Interface IOrderedDictionary
Sub Insert(ByVal index As Int32, ByVal key As [Object], ByVal value As [Object])
Sub RemoveAt(ByVal index As Int32)
End Interface
<Serializable()> Public Class KeyedList
Implements IDictionary, IEnumerable, IOrderedDictionary
Private objectTable As New Hashtable
Private objectList As New ArrayList
Public Sub Add(ByVal key As Object, ByVal value As Object) Implements IDictionary.Add
objectTable.Add(key, value)
objectList.Add(New DictionaryEntry(key, value))
End Sub
Public Sub Clear() Implements IDictionary.Clear
objectTable.Clear()
objectList.Clear()
End Sub
Public Function Contains(ByVal key As Object) As Boolean Implements IDictionary.contains
Return objectTable.Contains(key)
End Function
Public Sub CopyTo(ByVal array As Array, ByVal idx As Integer) Implements ICollection.CopyTo
objectTable.CopyTo(array, idx)
End Sub
Public Sub Insert(ByVal idx As Integer, ByVal key As Object, ByVal value As Object) Implements IOrderedDictionary.Insert
If idx > Count Then
Throw New ArgumentOutOfRangeException("index")
End If
objectTable.Add(key, value)
objectList.Insert(idx, New DictionaryEntry(key, value))
End Sub
Public Sub Remove(ByVal key As Object) Implements IDictionary.Remove
objectTable.Remove(key)
objectList.RemoveAt(IndexOf(key))
End Sub
Public Sub RemoveAt(ByVal idx As Integer) Implements IOrderedDictionary.RemoveAt
If idx >= Count Then
Throw New ArgumentOutOfRangeException("index")
End If
objectTable.Remove(CType(objectList(idx), DictionaryEntry).Key)
objectList.RemoveAt(idx)
End Sub
Function GetEnumerator() As IDictionaryEnumerator Implements IDictionary.GetEnumerator
Return New KeyedListEnumerator(objectList)
End Function
Function GetEnumerator() As IEnumerator Implements IEnumerable.GetEnumerator
Return New KeyedListEnumerator(objectList)
End Function
Public ReadOnly Property Count() As Integer Implements ICollection.Count
Get
Return objectList.Count
End Get
End Property
Public ReadOnly Property IsFixedSize() As Boolean Implements IDictionary.isFixedSize
Get
Return False
End Get
End Property
Public ReadOnly Property IsReadOnly() As Boolean Implements IDictionary.IsReadOnly
Get
Return False
End Get
End Property
Public ReadOnly Property IsSynchronized() As Boolean Implements IDictionary.IsSynchronized
Get
Return False
End Get
End Property
Default Public Property Item(ByVal idx As Integer) As Object
Get
Return CType(objectList(idx), DictionaryEntry).Value
End Get
Set(ByVal Value As Object)
If idx < 0 Or idx >= Count Then
Throw New ArgumentOutOfRangeException("index")
End If
Dim key As Object = CType(objectList(idx), DictionaryEntry).Key
objectList(idx) = New DictionaryEntry(key, Value)
objectTable(key) = Value
End Set
End Property
Default Public Property Item(ByVal key As Object) As Object Implements IDictionary.item
Get
Return objectTable(key)
End Get
Set(ByVal Value As Object)
If objectTable.Contains(key) Then
objectTable(key) = Value
objectTable(IndexOf(key)) = New DictionaryEntry(key, Value)
Return
End If
Add(key, Value)
End Set
End Property
Public ReadOnly Property Keys() As ICollection Implements IDictionary.keys
Get
Dim retList As New ArrayList
Dim i As Integer
For i = 0 To objectList.Count - 1
retList.Add(CType(objectList(i), DictionaryEntry).Key)
Next i
Return retList
End Get
End Property
Public ReadOnly Property Values() As ICollection Implements IDictionary.values
Get
Dim retList As New ArrayList
Dim i As Integer
For i = 0 To objectList.Count - 1
retList.Add(CType(objectList(i), DictionaryEntry).Value)
Next i
Return retList
End Get
End Property
Public ReadOnly Property SyncRoot() As Object Implements System.Collections.ICollection.SyncRoot
Get
Return Me
End Get
End Property
Private Function IndexOf(ByVal key As Object) As Integer
Dim i As Integer
For i = 0 To objectList.Count - 1
If CType(objectList(i), DictionaryEntry).Key.Equals(key) Then
Return i
End If
Next i
Return -1
End Function
End Class
_
Public Class KeyedListEnumerator
Implements IDictionaryEnumerator
Private index As Integer = -1
Private objs As ArrayList
Friend Sub New(ByVal list As ArrayList)
objs = list
End Sub 'New
Public Function MoveNext() As Boolean Implements IDictionaryEnumerator.MoveNext
index += 1
If index >= objs.Count Then
Return False
End If
Return True
End Function
Public Sub Reset() Implements IDictionaryEnumerator.Reset
index = -1
End Sub
Public ReadOnly Property Current() As Object Implements IDictionaryEnumerator.Current
Get
If index < 0 Or index >= objs.Count Then
Throw New InvalidOperationException
End If
Return objs(index)
End Get
End Property
Public ReadOnly Property Entry() As DictionaryEntry Implements IDictionaryEnumerator.Entry
Get
Return CType(Current, DictionaryEntry)
End Get
End Property
Public ReadOnly Property Key() As Object Implements IDictionaryEnumerator.Key
Get
Return Entry.Key
End Get
End Property
Public ReadOnly Property Value() As Object Implements IDictionaryEnumerator.Value
Get
Return Entry.Value
End Get
End Property
End Class
'End Namespace 'System.Collections
Ken Johnson (kenjohnson777@hotmail.com)
|
|
|
|
|
a long time ago but did you get a solution to VB issue? thank-you
|
|
|
|
|
Use
objectList.CopyTo(array,index);
instead of
objectTable.CopyTo (array, idx);
Yes?
Thanks for sharing your googling research and resulting code!
|
|
|
|
|
you can use SortedList like follows:
SortedList list = new SortedList(13);
list.Add("one", 1);
list.Add("two", 2);
list.Add("three", 3);
int index = list.IndexOfKey("two");
int val = (int)list.GetByIndex(index);
|
|
|
|
|
Use SortedList like that may cause a reduction of efficiency, when you go through a huge list.
But i think it's nothing serious in most cases. In this way, go through a list with 10,000 elements use only 20 ms on my PC.
|
|
|
|
|
SortedList list = new SortedList(13);
list.Add("one", 1);
list.Add("two", 2);
list.Add("three", 3);
int val = (int)list["two"];
|
|
|
|
|
The set property of the 'this[object key]' sets the value of the 'objectTable' to a DictionaryEntry instead of setting the value of the 'objectList'. Should be as follows:
if (objectTable.Contains (key))
{
objectTable[key] = value;
objectList[IndexOf (key)] = new DictionaryEntry (key, value); // Should not be 'objectTable'
return;
}
Add (key, value);
|
|
|
|
|
I got tripped up by this, too.
A code update would be appreciated.
|
|
|
|
|
This is a great implementation. However, the delete operation is O(n). This isn't necessarily a problem especially if deletions are rare. But, when insertions, searches, and deletions are equally likely the amortized cost is still O(n) despite the fact that insertions and searches are O(1).
One possible solution to this is to store the key in a balanced binary search tree. The key, which I will refer to as the given key, will itself be keyed for lookups in the BST using an internal algorithm that ensures temporal ordering. I will call this the internal key. The internal key could easily be an integer that is incremented each time there is an insertion. The value and the internal key would be stored together in the hashtable keyed by the given key. Inserts and deletions would be O(lg n) and the search would remain O(1). Thus the amortized cost is O(lg n) for all operations. Of course, the trade-off is that it will take a little more storage space.
The interesting discussion is on which BST implementation to use. A standard binary search tree would be useless because of the sequential nature of the internal key. It would behave like a linked list resulting in O(n) operations. I was about to suggest the self balancing red-black tree, but a splay tree may be more appropriate because of the way it adapts to sequential access patterns.
I 5'd your article.
Brian
|
|
|
|
|
What about Strongly-Typed Collections? I've come up with a Template I use for all my Collection Classes that are strongly typed off the Objects in the Collection. And it also supports Keys and Enumerates using the order in which they were added to the Collection...
|
|
|
|
|
mikasa wrote:
I've come up with a Template I use for all my Collection Classes that are strongly typed off the Objects in the Collection.
Sounds interesting. I can't imagine how you do that though in C# without a wrapper for each type that you manage in the collection. Care to email me an example?
webmaster@knowledgeautomation.com
Marc
Latest AAL Article
My blog
Join my forum!
|
|
|
|
|
Sure, I'll send it. I basically got the idea from the "CollectionGen" utility. It takes a little bit of work for each one, but it's well worth it because they're super-fast and there is absolutely no casting involved (hence...strongly-typed). Unfortunately, I've done this in VB.NET (which I converted from C# ).
|
|
|
|
|
Hi,
Would you mind to send me your nice code.
My email: iftekhar.ivaan@donovandata.com
Thanks
|
|
|
|
|
Just download My Project[^] and look at the ListItems Collection Class.
|
|
|
|
|
Well, first of all, I think we all end up looking for a collection that behaves like this at saome point or another, so I think this is a usefull starting point.
However, a couple of comments (actually 3
1~ namespace pollution:
Why use the System.Collection namespace instead of your own ? I am just worried about "polluting" 'official' namespaces...
2~ memory
Sure, nowadays we don't worry too much about how much memory we use, but this class doubles the space required for storing each object, since it keeps 2 copies of each object (one in the hashtable, one in the array list).... or do you store only 2 references? If you store only the references, then you end up in the various possible problems due to aliasing. Of course, I understand that storing the objects in a single internal collection would mean a hit on the performance when searching by key or by value (but not both .
3~ Templates:
since the next version of C# should allow for templated classes, and this will be especially useful with collections, how does this class fit in that scheme?
Anyway, as I said, I think this is very usefull.
F.O.R.
|
|
|
|
|
Frank Olorin Rizzi wrote:
Why use the System.Collection namespace instead of your own ?
Good point, and I debated that. Well, it's easily changed! On the other hand, I can't understand why Microsoft is putting this in the Web.UI namespace. What--this class is only useful for web applications?
Frank Olorin Rizzi wrote:
since it keeps 2 copies of each object
Well, no. It keeps two references to an object. That takes up very little space.
Frank Olorin Rizzi wrote:
If you store only the references, then you end up in the various possible problems due to aliasing.
I'm not exactly sure what you mean here. If the object is removed from the KeyedList, it's removed from both the Array and the Hashtable at the same time.
I don't think either of these two points are an issue. Managing references is really not memory intensive. If memory is an issue, then the approach should be changed--why would you want to handle a million objects in memory? The Longhorn documentation also indicates that uses both an Array and a Hashtable, so I don't think Microsoft thinks there's a problem here either.
Frank Olorin Rizzi wrote:
since the next version of C# should allow for templated classes, and this will be especially useful with collections, how does this class fit in that scheme?
Obviously, it doesn't. Nor does any of the other classes in the Collections namespace. When templates show up, all those "object" variables simply get turned into "<t> t" variables and the class definition changes to something like "class KeyedList<t>" (I forget the actual template syntax at this point).
But I'm also not sure templates are necessary in all cases. The enumeration capabilities is already good enough to automatically cast an object to the specified type:
foreach (XmlSchemaObjectCollection schemaObjects in coll) {...}
The real problem is automatically converting the value type in the key list collections when you index them like:
object foo=schemaObject["XmlSchemaComplexType'];
Which is something that you can do much nicer, without casting, with templates.
Frank Olorin Rizzi wrote:
Anyway, as I said, I think this is very usefull.
Yup. It sure came in handy for me!
Marc
Latest AAL Article
My blog
Join my forum!
|
|
|
|
|
Hi Marc.
Thanks for replying.
Marc Clifton wrote:
Frank Olorin Rizzi wrote:
If you store only the references, then you end up in the various possible problems due to aliasing.
I'm not exactly sure what you mean here. If the object is removed from the KeyedList, it's removed from both the Array and the Hashtable at the same time.
I was thinking more along the lines of
1~ store an object in the KeyedList
2~ change the object (the original one)
Now the object in the list is changed as well. Now, since we have automated garbage collection, we don't risk to run into null references, but I always wonder, when using collections, if it is more appropriate to store a ref to the original or a deep copy (I end up doing my collections so that they store a deep copy). That's all.
For the rest, I agree.
Personally, I think that the introduction of templates will let us have strongly types collections without writing specialized ones ourselves all the times (i.e. instead of storing objects, if we want to store instances of the myClass class, we need to write a myClassCollection right now, where we can Add(myClass x) and have a "myClass Get(...)" routine and so on).
Of course, there are other advantages to templates
Thanks again, especially for the follow-up (I'm always interested in hearing other people's ideas).
Oh, and in regard to the namespaces... yeah, I don't see why MS is adding this type of collection only to the WebUI namespace... unless one of their internal teams developed this, but the others didn't have time to integrate it in the other namespaces.
F.O.R.
|
|
|
|
|
|
Since this uses the HashTable to store duplicate keys throw an exception. If duplicate keys are required you could use 2 ArrayLists instead (ie 1 for keys, and 1 for values), but for large collections key lookups would probably be slower than the HashTable.
|
|
|
|
|