The .NET System.Collections.Generic.List class is not a linked list as non-.NET users might expect. This list class is actually more like an array list than a linked list. Because of this it has some of the benefits of arrays. Simply because of the array data structure which exists within the generic list class, the class is able to achieve a constant time Count function. The basic array data structure is a collection of objects which are stored contiguously in memory, and because of this it makes counting them easy. It also makes it quite easy to index into a specific location, because you can just jump straight to the correct location in memory. With a linked list one has to traverse the list. The advantage of the linked list is that it is held together using pointers, so if you want to add nodes it is simply an update to pointers. This means that adding a collection of nodes can take constant time.
I would highly recommend against the array list if you will be adding and removing objects from this collection often. Since there is an allocated amount of space in memory for the array this means that if you need to exceed this space then you will need to create a new list. Using Big O notation the AddRange function of list will take O(n) time to complete. The n in this case is the number of elements to add. This doesn't seem to bad, but when the allotted space is exceeded the array will need to move and recreate itself with more space. This is the big performance hit. For this operation it will have O(n+m) time, because you will have to do the regular n operations plus m operations for the original data in the array.
Removing an element from an array requires a little bit of work. One reason for this is that the array data structure should never contain an empty space. This means that first you will need to perform a linear search algorithm to find the element to remove. Stepping one by one through the list. Upon reaching the element to remove, it is removed, but then all the elements after that one must be moved forward in the array so no space exists. This causes the remove function to perform in linear time.
- Capacity O(1)
- Count O(1)
- AddRange O(n) or O(n+m)
- Remove O(n)
I am planning to write of series of little bits of stuff. If you catch any mistakes in any of this series please comment on the correction ASAP. I don't want to be passing along incorrect information.
I am fairly certain that the C++ Standard Template Library's list object's size function is an O(n) operation. For those of you less algorithmically informed people I am saying that a linked list which uses pointers to the next object in the list has to take linear time (directly corresponding to the number of elements) to find out the size of the list. At first this seems kind of odd. One would wonder why not just keep the count of the elements stored somewhere.
Keeping the count of the number of elements in a linked list will make what I believe is the linked list's greatest asset less valuable. The splice function (which is like the AddRange function) is able to just update pointers. This is amazingly useful because added n number of elements can take constant time. Meaning that it takes just as long to add 10 elements as to add 1000 elements. When needed that is a life saver. Having that ability though prevents being able to keep track of the size of the list, because the list doesn't know how many elements you are splicing in. It would need to take linear time to count them. Because of this it would make it linear instead of constant time. Ouch.
Because of this close relationship between the size and splice functions one will have to be linear and one constant. It seems that it was decided that with a linked list it would just be easier to iterate to the end instead of using the size. Splicing is a lot more important in my opinion to the usefulness of a linked list. I suggest perhaps a second object which is a linked list which has a constant size and a linear splice for when size will be checked more often than splicing will occur.
I was discussing this with someone recently and found it quite interesting, and I now think I am going to go and start reading more about the algorithms of the functions used in C#. Perhaps in the future I will write about the algorithms in .NET and the runtime of these algorithms. I hope so.
I was recently on Developer Fusion when I noticed some simple and easy to use C# to VB and VB to C# converters. It is not difficult to translate code from one language to the other, but sometimes I'll want to test out a code snippet from some site and it is in VB. I use C# and I don't want to have to sit there translating 20 lines of code, and I also don't want to go and get an expensive converter. These seem to do a reasonable job converting between the two languages. I've used them a fair amount so far, and I haven't run into a problem with them yet. I suggest you check them out and bookmark them. They've saved me plenty of time already.
Earlier today I was trying to debug a Stack Overflow Exception I was receiving. While debugging I was stepping into the function where the problem was occurring. I could not seem to find the problem. A line of code was calling a function and passing it a few properties as parameters and the value returned by the function was being stored in another property. Without really paying attention to which properties I was stepping into I just clicked through them and then it would throw the exception. I was quite confused and did not even think that it could be a problem with the properties, because I had stepped through them. Well, I as with many other people are annoyed when I am debugging and it steps into a property with no extra logic. Sometimes when I create a property I remember to add the DebuggerStepThrough property. If you don't know what that is I recommend you learn what it is and use it.
When a property has no extra logic in it I obviously don't care to step through its execution it is not the problem.... except when it is.
Someone added a property to a class recently and remembered to add the DebuggerStepThrough property to it. The problem is that this simple property created an infinite loop, which I did not even think to check because some of the properties I was stepping into. Only one did I not step into and it had the problem. It had the following problem.
private int _x;
public int X
X = value;
When I tried to set the value I jumped into a recursive loop which the debugger stepped through so it did not even let me see the problem when I was trying to debug. Gotta make sure that doesn't happen. Kind of bad when a property calls itself instead of setting the private member it is supposed to access.
In order to use an update panel you have to specify the triggers either individually or by setting the ChildrenAsTriggers property of the UpdatePanel. Sometimes you may need to set these triggers dynamically such as if the desired trigger is inside of a repeater and is not inside of the update panel. In instances such as this you will need to from the code behind register the control with the script manager. To do this you will want to use the RegisterAsynchPostBackControl function of the ScriptManager in the following manner:
This code could be inside of the OnItemDataBound event handler for a repeater or even in page load if you want to register it in code. The script manager will now know to hijack the postbacks created by this control and turn them into asynchronous postbacks. The good thing about this is that you will now not do a full postback. The bad part is that you still have to let the update panel know that it needs to update after the asynchronous postback. To do this you will want to Call the Update() method of the UpdatePanel so for example you might do the following:
protected void Button1_Click(object sender, EventArgs e)
// Do work
By using this method you will not be tied to your .aspx pages. It is not quite as elegant as when you just use the triggers collection in the UpdatePanel on the .aspx page, but this way of doing this is still easy and possible when inside of a template such as in a repeater or a gridview.
Recently I had forgotten how to access the ScriptManager in my MasterPage from one of the Content Pages. There is a static method on the ScriptManager class called GetCurrent() which will allow access to the current instance of a ScriptManager. This is useful because the ScriptManagerProxy is really just designed to do the declarative work normally performed on the ASP.NET page, but some work needs to be done through code. An example would be to check the ScriptManager instances IsInAsyncPostback property.
// Perform only in asynchronous postback logic here.
This is very useful and easy, but I seem to always forget it is here. Perhaps now that I have blogged about it I will remember, and if not I can at least come back here to find it. Yes, when I forget I go through the trouble of casting Master as my MasterPage's class and then I access it that way (what a pain).
I can’t wait to start using VS 2008. It has a lot of great features I plan on getting a lot of use out of.
As I mentioned in my previous blog post about Accessing a property of a base page from a user control, I am going to explain how to access a property on a MasterPage from the content page. One merely has to check the namespace and the class name of the masterpage, which can be found in the code behind file. Just cast the Content Page’s Master as the class of the masterpage file which it uses, and then just access the value. It is really quite simple.
int neededValue = ((MyNameSpace.MyMasterPageClassName)Master).MyProperty;
Using that method you are able to easily access a property of a masterpage file when needed.
Earlier today I was helping someone who was working with a user control. That control was on an ASP.NET page which was inheriting from a base page. From the user control he could not access the properties of the base page. He mentioned that he was getting an error message which said that the property did not exist in the current context.
I showed him that the reason he was having the problem is because the code in the user control came from the page before, and thus he would need to get the properties from there, but he was also going to need to cast the Page as the base Page in order to get to the property.
int myImportantValue = ((MyBasePage)Page).ImportantProperty;
This will retrieve the value from the property of the base page. It is a fairly simple task. Perhaps next I will show how to do a similar task with a masterpage.
I've now added that blog post about Accessing a Property of a MasterPage from a Content Page.
Earlier today I had a situation where I needed to clear the output cache entry of a page. After a quick Google search I turned up Steve Smith’s Article on Removing Page Output Cache Entries.
The article is a short, helpful article which quickly and easily explains how to remove the output cache entry of a page.
private void RemoveButton_Click(object sender, System.EventArgs e)
I hope everyone else finds this to be easy to understand and implement. The above should work as long as you have a page named “CacheForever.aspx” in the folder “caching” at the root of the site.