Array and related collections.
-
Making my application i have suddently got and evil optimization question about "What are the internals of the array list" :sigh:. Does any of you know if it is based on a linked list or on an array. Also do you know where i can get my hand on a Simple Linked List or a Binary Tree. Thank you for help.
-
Making my application i have suddently got and evil optimization question about "What are the internals of the array list" :sigh:. Does any of you know if it is based on a linked list or on an array. Also do you know where i can get my hand on a Simple Linked List or a Binary Tree. Thank you for help.
An ArrayList is an array that grows dynamically by recreating the array (often doubling the size) everytime the bounds are surpassed. As far as binary trees go, I suggest you take a peak at the MSDN article[^] regarding data structures. Part 3[^] of the article shows off some trees, including the source for a binary tree in C#. --------------------------- He who knows that enough is enough will always have enough. -Lao Tsu
-
Making my application i have suddently got and evil optimization question about "What are the internals of the array list" :sigh:. Does any of you know if it is based on a linked list or on an array. Also do you know where i can get my hand on a Simple Linked List or a Binary Tree. Thank you for help.
As Judah said, it uses a new array that typically doubles whenever the
Capacityis reached. To note, theArrayListis used internally by many collections, so don't think you can escape it so easily! ;)Microsoft MVP, Visual C# My Articles
-
As Judah said, it uses a new array that typically doubles whenever the
Capacityis reached. To note, theArrayListis used internally by many collections, so don't think you can escape it so easily! ;)Microsoft MVP, Visual C# My Articles
Thank both of you. I have another little question. What is the perforamce loss due to the type casting of array list elements. If my array list contains the same type elemets (or which share the same base class), could i use something equivalent to templates in C++. Thank again. Anton.
-
Thank both of you. I have another little question. What is the perforamce loss due to the type casting of array list elements. If my array list contains the same type elemets (or which share the same base class), could i use something equivalent to templates in C++. Thank again. Anton.
An
ArrayListstoresobjects, so if you add reference types to the list, there's really no performance hit (1 to 2 extra instructions are required to cast, and optionally store, your type, but that's negligible). If you store value types, there is a slight performance hit because value types must be boxed and unboxed to store as anobject. This is one of many reasons why generics will be great to have in the upcoming .NET Framework 2.0. Then you can declare a new list of value types, likeList<int> ints = new List<int>();. This (un)boxing is typically not too big a problem if you don't use it a lot and don't need to milk your app for performance for every last drop. If you do, then you might consider implementing your ownArrayList-like class, implementing all the same interfaces (for the best support) and keep an array of whatever value type you need. Grow it when needs be, just like theArrayListwould.Microsoft MVP, Visual C# My Articles
-
An
ArrayListstoresobjects, so if you add reference types to the list, there's really no performance hit (1 to 2 extra instructions are required to cast, and optionally store, your type, but that's negligible). If you store value types, there is a slight performance hit because value types must be boxed and unboxed to store as anobject. This is one of many reasons why generics will be great to have in the upcoming .NET Framework 2.0. Then you can declare a new list of value types, likeList<int> ints = new List<int>();. This (un)boxing is typically not too big a problem if you don't use it a lot and don't need to milk your app for performance for every last drop. If you do, then you might consider implementing your ownArrayList-like class, implementing all the same interfaces (for the best support) and keep an array of whatever value type you need. Grow it when needs be, just like theArrayListwould.Microsoft MVP, Visual C# My Articles
In this case i will keep it, since making changes later would be much easier. Thank you.