Friday, October 29, 2010

C# Generics Collections

 .NET System.Collections.Generic Namespace

One of the most powerful and useful capabilities of the .NET Framework and C# language is the support for generic types. These types, mainly found in the System.Collections.Generic namespace, are polymorphic based on their type parameters (parametric polymorphism). As we describe here, the types in System.Collections.Generic can provide amazing performance and simplicity in your source code.
::: Implementation classes :::
    Comparer<>
    Dictionary<>
    EqualityComparer<>
    HashSet<>
    KeyValuePair<>
    LinkedList<>
    LinkedListNode<>
    List<>
    Queue<>
    SortedDictionary<>
    SortedList<>
    SortedSet<>
    Stack<>

::: Interfaces :::
    ICollection<>
    IComparer<>
    IDictionary<>
    IEnumerable<>
    IEnumerator<>
    IEqualityComparer<>
    IList<>
    ISet<>

::: Exceptions :::
    KeyNotFoundException

Dictionary<>, IDictionary<>

In the .NET Framework, a Dictionary is a lookup table that allows objects as keys and objects as values. It is typically implemented with hash code lookups, making it extremely fast to search for elements.

Comparer<>, EqualityComparer<>, IComparer<>, IEqualityComparer<>

The Comparer and EqualityComparer interfaces are contracts that require methods to compare two objects. The difference is that Comparer requires a method Compare() that will tell which object is greater or less than the other. EqualityComparer, on the other hand, only needs to determine if two objects are considered equal.

HashSet<>, SortedSet<>, ISet<>

The HashSet and SortedSet implement set logic. This means that only one element with a certain value can be present in the collection, and you can use set operations such as Union or Overlaps to mutate the set. The ISet interface defines common functionality in the HashSet and SortedSet. The HashSet is typically faster for programs that need frequent lookups.

KeyValuePair<>

This type is implemented as a struct; it simply stores two references to objects. You can store any type in the key and any type in the value slot. Another type that is similar to the KeyValuePair<> type is the Tuple type.

LinkedList<>, LinkedListNode<>

Linked lists are collections that allow for fast insertion and removal of elements anywhere in the list. For most other purposes, though, they are slower than a regular List. In my experience, the LinkedList type is not very popular, and it is often more trouble than it is worth.

List<>, IList<>

The List type is a fantastic resizable array data structure. You can append elements to its end very quickly, and it contains internal logic to avoid excessive resizes. Adding elements to the start is slow, however, and you cannot do very fast lookups. I recommend the List most often.

Queue<>

The Queue type is not often useful, but when you need to implement a history mechanism which stores the last several items used, it can be useful. It does not really provide any performance advantages over other implementations. It can make for simpler code in some cases.

SortedDictionary<>

The SortedDictionary is much slower for lookups than a Dictionary, but it always has a sorted representation of its internal elements. If having a sorted collection is most important to you, consider this collection. If you have any concern about lookup performance, or don't want to have that concern in the future, prefer Dictionary.

SortedList<>

The SortedList is another always-sorted collection. If you have a List and are always sorting the List before displaying it or persisting it, consider the SortedList to make your code simpler.

Stack<>

The most famous use for a Stack is the implementation of parsers. When parsing HTML, you can push an element to the top of the stack, and when that element closes, you can pop the element from the top of the Stack.

IEnumerable<>

The IEnumerable interface allows you to loop over a variable in a foreach-loop. As each iteration of the foreach-loop is reached, the IEnumerable interface can execute arbitrary code. This can improve performance in some programs because work that is not needed is not done.

IEnumerator<>

The IEnumerator<> interface is implemented on generic collections and allows users to loop over all the elements in the foreach-loop. The IEnumerator interface is part of other generic collections, while the IEnumerable interface can be used directly to support looping.

KeyNotFoundException

The KeyNotFoundException is not a generic type, but it is found in the System.Collections.Generic namespace. It represents an error that occurs when trying to access a key that does not exist in a Dictionary or similar (IDictionary-based) collection.

Summary

The .NET Framework contains other generic types that are not present in System.Collections.Generic, but the ones here are some of the most popular and core to the framework. A solid understanding of these types can benefit your programs and also save you time and the hassle of implementing custom data structures when none are needed.

 

Collections

Collections are type instances that contain other type instances; they include the List, ArrayList and Dictionary types. These types, as well as many others, are detailed here.

C# List Examples

You have questions about the List collection in the .NET Framework, which is located in the System.Collections.Generic namespace. You want to see examples of using List and also explore some of the many useful methods it provides, making it an ideal type for dynamically adding data. This document has lots of tips and resources on the List constructed type, with examples using the C# programming language.
Lists are dynamic arrays in the C# language.
They can grow as needed when you add elements.
They are considered generics and constructed types.
You need to use < and > in the List declaration.

Adding values

To start, we see how to declare a new List of int values and add integers to it. This example shows how you can create a new List of unspecified size, and add four prime numbers to it. Importantly, the angle brackets are part of the declaration type, not conditional operators that mean less or more than. They are treated differently in the language.
~~~ Program that adds elements to List (C#) ~~~

using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> list = new List<int>();
        list.Add(2);
        list.Add(3);
        list.Add(5);
        list.Add(7);
    }
}
Adding objects. The above example shows how you can add a primitive type such as integer to a List collection, but the List collection can receive reference types and object instances. There is more information on adding objects with the Add method on this site.

Loops

Here we see how you can loop through your List with for and foreach loops. This is a very common operation when using List. The syntax is the same as that for an array, except your use Count, not Length for the upper bound. You can also loop backwards through your List by reversing the for loop iteration variables. Start with list.Count - 1, and proceed decrementing to >= 0.
~~~ Program that loops through List (C#) ~~~

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> list = new List<int>();
        list.Add(2);
        list.Add(3);
        list.Add(7);

        foreach (int prime in list) // Loop through List with foreach
        {
            Console.WriteLine(prime);
        }

        for (int i = 0; i < list.Count; i++) // Loop through List with for
        {
            Console.WriteLine(list[i]);
        }
    }
}

~~~ Output of the program ~~~
    (Repeated twice)
2
3
7

Counting elements

To get the number of elements in your List, access the Count property. This is fast to access, if you avoid the Count() extension method. Count is equal to Length on arrays. See the section "Clearing List" for an example on using the Count property.

Clearing List—setting to null

Here we see how to use the Clear method, along with the Count property, to erase all the elements in your List. Before Clear is called, this List has 3 elements; after Clear is called, it has 0 elements. Alternatively, you can assign the List to null instead of calling Clear, with similar performance. However, after assigning to null, you must call the constructor again.
=== Program that counts List (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<bool> list = new List<bool>();
        list.Add(true);
        list.Add(false);
        list.Add(true);
        Console.WriteLine(list.Count); // 3

        list.Clear();
        Console.WriteLine(list.Count); // 0
    }
}

=== Output of the program ===

3
0

Copying array to List

Here we see an easy way to create a new List with the elements in an array that already exists. You can use the List constructor and pass it the array as the parameter. List receives this parameter, and fills its values from it.
--- Program that copies array to List (C#) ---

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[] arr = new int[3]; // New array with 3 elements
        arr[0] = 2;
        arr[1] = 3;
        arr[2] = 5;
        List<int> list = new List<int>(arr); // Copy to List
        Console.WriteLine(list.Count);       // 3 elements in List
    }
}

--- Output of the program ---
    (Indicates number of elements.)

3
Notes on the example. It is useful to use the List constructor code here to create a new List from Dictionary keys. This will give you a List of the Dictionary keys. The array element type must match the type of the List elements, or the compiler will refuse to compile your code.

Finding elements

Here we an example of how you can test each element in your List for a certain value. This shows the foreach loop, which tests to see if 3 is in the List of prime numbers. Note that more advanced List methods are available to find matches in the List, but they often aren't any better than this loop. They can sometimes result in shorter code.
~~~ Program that uses foreach on List (C#) ~~~

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // New list for example
        List<int> primes = new List<int>(new int[] { 2, 3, 5 });

        // See if List contains 3
        foreach (int number in primes)
        {
            if (number == 3) // Will match once
            {
                Console.WriteLine("Contains 3");
            }
        }
    }
}

~~~ Output of the program ~~~

Contains 3

Using capacity

You can use the Capacity property on List, or pass an integer into the constructor, to improve allocation performance when using List. The author's research shows that capacity can improve performance by nearly two times for adding elements. Note however that this is not usually a performance bottleneck in programs that access data.
TrimExcess method. There is the TrimExcess method on List as well, but its usage is very limited and I have never needed to use it. It reduces the memory used. Note: "The TrimExcess method does nothing if the list is at more than 90 percent of capacity".

Using BinarySearch

You can use the binary search algorithm on List with the instance BinarySearch method. Binary search uses guesses to find the correct element much faster than linear searching. It is often much slower than Dictionary.

Using AddRange and InsertRange

You can use AddRange and InsertRange to add or insert collections of elements into your existing List. This can make your code simpler. See an example of these methods on this site.

Using ForEach method

Sometimes you may not want to write a regular foreach loop, which makes ForEach useful. This accepts an Action, which is a void delegate method. Be very cautious when you use Predicates and Actions, because they can decrease the readability of your code.
Another useful method. There is a TrueForAll method that accepts a Predicate. If the Predicate returns true for each element in your List, the TrueForAll method will return true also. Else, it will return false.

Using Join—string List

Here we see how you can use string.Join on a List of strings. This is useful when you need to turn several strings into one comma-delimited string. It requires the ToArray instance method on List. The biggest advantage of Join here is that no trailing comma is present on the resulting string, which would be present in a loop where each string is appended.
=== Program that joins List (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // List of cities we need to join
        List<string> cities = new List<string>();
        cities.Add("New York");
        cities.Add("Mumbai");
        cities.Add("Berlin");
        cities.Add("Istanbul");

        // Join strings into one CSV line
        string line = string.Join(",", cities.ToArray());
        Console.WriteLine(line);
    }
}

=== Output of the program ===

New York,Mumbai,Berlin,Istanbul

Getting List from Keys in Dictionary

Here we see how you can use the List constructor to get a List of keys in your Dictionary collection. This gives you a simple way to iterate over Dictionary keys, or store them elsewhere. The Keys instance property accessor on Dictionary returns an enumerable collection of keys, which can be passed to the List constructor as a parameter.
::: Program that converts Keys (C#) :::

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Populate example Dictionary
        var dict = new Dictionary<int, bool>();
        dict.Add(3, true);
        dict.Add(5, false);

        // Get a List of all the Keys
        List<int> keys = new List<int>(dict.Keys);
        foreach (int key in keys)
        {
            Console.WriteLine(key);
        }
    }
}

::: Output of the program :::

3, 5

Inserting elements

Here we see how you can insert an element into your List at any position. The string "dalmation" is inserted into index 1, which makes it become the second element in the List. Note that if you have to Insert elements extensively, you should consider the Queue and LinkedList collections for better performance. Additionally, a Queue may provide clearer usage of the collection in your code.
~~~ Program that inserts into List (C#) ~~~

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<string> dogs = new List<string>(); // Example List

        dogs.Add("spaniel");         // Contains: spaniel
        dogs.Add("beagle");          // Contains: spaniel, beagle
        dogs.Insert(1, "dalmation"); // Contains: spaniel, dalmation, beagle

        foreach (string dog in dogs) // Display for verification
        {
            Console.WriteLine(dog);
        }
    }
}

~~~ Output of the program ~~~

spaniel
dalmation
beagle

Removing elements

The removal methods on List are covered in depth in another article on this site. It contains examples for Remove, RemoveAt, RemoveAll, and RemoveRange, along with the author's notes.

Sorting and reversing

You can use the powerful Sort and Reverse methods in your List collection. These allow you to order your List in ascending or descending order. Additionally, you can use Reverse even when your List is not presorted. There is more information on these topics, as well as sorting your List with LINQ on a property on this site.

Converting List to array

You can convert your List to an array of the same type using the instance method ToArray. There are examples of this conversion, and the opposite, on this site.

Getting range of elements

Here we see how you can get a range of elements in your List collection using the GetRange instance method. This is similar to the Take and Skip methods from LINQ, but has different syntax.
--- Program that gets ranges from List (C#) ---

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<string> rivers = new List<string>(new string[]
        {
            "nile",
            "amazon",     // River 2
            "yangtze",    // River 3
            "mississippi",
            "yellow"
        });

        // Get rivers 2 through 3
        List<string> range = rivers.GetRange(1, 2);
        foreach (string river in range)
        {
            Console.WriteLine(river);
        }
    }
}

--- Output of the program ---

amazon
yangtze

Testing Lists for equality

Sometimes you may need to test two Lists for equality, even when their elements are unordered. You can do this by sorting both of them and then comparing, or by using a custom List equality method. This site contains an example of a method that tests lists for equality in an unordered way.

Using List with structs

When using List, you can improve performance and reduce memory usage with structs instead of classes. A List of structs is allocated in contiguous memory, unlike a List of classes. This is an advanced optimization. Note that in many cases using structs will actually decrease the performance when they are used as parameters in methods such as those on the List type.

Using var keyword

Here we see how you can use List collections with the var keyword. This can greatly shorten your lines of code, which sometimes improves readability. The var keyword has no effect on performance, only readability for programmers.
~~~ Program that uses var with List (C#) ~~~

using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var list1 = new List<int>();       // <- var keyword used
        List<int> list2 = new List<int>(); // <- Is equivalent to
    }
}

Summary

In this tutorial, we saw lots of examples with the List constructed type. You will find that List is powerful and performs well. It provides flexible allocation and growth, making it much easier to use than arrays. In most programs that do not have memory or performance constraints and must add elements dynamically, the List constructed type in the C# programming language is ideal.

C# ArrayList Examples, Usage and Tips

You need to use the ArrayList class in an older C# program to fix or improve the dynamic arrays. ArrayList is still useful, even when newer classes are more durable and popular. Here we see examples and tips using the ArrayList class in the C# programming language, moving from the simpler tasks to the more advanced usages of ArrayList.

Adding elements

The Add method on ArrayList is used in almost every program. It appends a new element object to the very end of the ArrayList. You can keep adding elements to your collection until memory runs out. The objects are stored in the managed heap.
=== Program that uses ArrayList (C#) ===

using System.Collections;

class Program
{
    static void Main()
    {
        //
        // Create an ArrayList and add three elements.
        //
        ArrayList list = new ArrayList();
        list.Add("One");
        list.Add("Two");
        list.Add("Three");
    }
}

=== Result of the program ===
    An ArrayList with three elements is created.
What the example shows. First, this is a complete console program that you can run in the Visual Studio IDE. When you run this example, there will be three elements added to the ArrayList. The first element is a string containing "One". The last element is "Three".

Using ArrayList in methods

Structural programming with ArrayList is easy, as you can simply pass the object with the ArrayList type. However, in the receiving function, you have to know (or find out) what the type of each element is. Here we pass the ArrayList as a parameter.
=== Program that uses ArrayList parameter (C#) ===

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        //
        // Create an ArrayList and add two ints.
        //
        ArrayList list = new ArrayList();
        list.Add(5);
        list.Add(7);
        //
        // Use ArrayList with method.
        //
        Example(list);
    }

    static void Example(ArrayList list)
    {
        foreach (int i in list)
        {
            Console.WriteLine(i);
        }
    }
}

=== Output of the program ===

5
7
Note on using ArrayList as return value. You can also use the ArrayList as a return value. Use the ArrayList type as the return keyword at the start of your method. Note that generally it is best to reuse the same ArrayList instead of combining more than one.

Adding one ArrayList to second one

There are different ways to add one ArrayList to another, but the best way is using AddRange. Internally, AddRange uses the Array.Copy or CopyTo methods, which have better performance than some loops.
=== Program that uses Add and AddRange (C#) ===

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        //
        // Create an ArrayList with two values.
        //
        ArrayList list = new ArrayList();
        list.Add(5);
        list.Add(7);
        //
        // Second ArrayList.
        //
        ArrayList list2 = new ArrayList();
        list2.Add(10);
        list2.Add(13);
        //
        // Add second ArrayList to first.
        //
        list.AddRange(list2);
        //
        // Display the values.
        //
        foreach (int i in list)
        {
            Console.WriteLine(i);
        }
    }
}

=== Output of the program ===

5
7
10
13
Description of the two ArrayLists. The first ArrayList has two elements added to it. Next, the second ArrayList has two elements added to it. The second ArrayList is then appended to the first using the AddRange method. The example finally shows the output.

Using Count and Clear

The ArrayList class provides the Count property, which is a virtual property. When you use Count, no counting is actually done; instead, a cached field value is returned. This means that Count is fairly fast. The example also shows Clear.
=== Program that uses Count (C#) ===

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        //
        // Create an ArrayList with two values.
        //
        ArrayList list = new ArrayList();
        list.Add(9);
        list.Add(10);
        //
        // Show number of elements in ArrayList.
        //
        Console.WriteLine(list.Count);
        //
        // Clear the ArrayList.
        //
        list.Clear();
        //
        // Show count again.
        //
        Console.WriteLine(list.Count);
    }
}

=== Output of the program ===

2
0
Usage of Count. The Count property returns an int, and you can assume this will always be a positive value. Sometimes, you can store the count in a local variable for better performance, but this isn't usually needed because no calculation takes place in the property itself.
Usage of Clear method. You can call the instance method Clear on your ArrayList. Internally, this calls the Array.Clear method. Sometimes, your code is clearer if you create a new ArrayList instead.

Sorting and reversing ArrayList

Many dynamic arrays such as ArrayList must be sorted frequently, before insertion into the output web page or Windows program. This greatly improves the functionality and usability in programs. You can call the instance Sort method on an ArrayList, and then we call Reverse on that sorted collection. These methods work in-place.
Sorting ranges in your ArrayList. You can sort subsets (ranges) of elements in your ArrayList using the third overload. This can be useful for rare situations, but isn't likely to be needed. Additionally, you can Reverse only a range of your ArrayList.

Inserting and removing elements

Here we see how you can insert and remove elements with the Insert and Remove family of methods. Specifically, we see the RemoveAt method for erasing a single element, then the Insert method and RemoveRange methods.
=== Program that uses Insert and Remove (C#) ===

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        //
        // Create an ArrayList with three strings.
        //
        ArrayList list = new ArrayList();
        list.Add("Dot");
        list.Add("Net");
        list.Add("Perls");
        //
        // Remove middle element in ArrayList.
        //
        list.RemoveAt(1); // It becomes [Dot, Perls]
        //
        // Insert word at beginning of ArrayList.
        //
        list.Insert(0, "Carrot"); // It becomes [Carrot, Dot, Perls]
        //
        // Remove first two words from ArrayList.
        //
        list.RemoveRange(0, 2);
        //
        // Display the result ArrayList.
        //
        foreach (string value in list)
        {
            Console.WriteLine(value); // <-- "Perls"
        }
    }
}

=== Output of the program ===

Perls

Looping with 'for'

In C# programming, the for loop is a very popular and useful loop construct. However, when using for on an ArrayList, you will need to cast the element after using its index. The [i] part in the example below demonstrates how to use the indexer on the ArrayList. You can find more separate information on indexers here.
=== Program that uses ArrayList and for (C#) ===

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        //
        // Create an ArrayList with three strings.
        //
        ArrayList list = new ArrayList();
        list.Add("man");
        list.Add("woman");
        list.Add("plant");
        //
        // Loop over ArrayList with for.
        //
        for (int i = 0; i < list.Count; i++)
        {
            string value = list[i] as string;
            Console.WriteLine(value);
        }
    }
}

=== Output of the program ===

man
woman
plant
Using "as" cast with ArrayList elements. The "as" cast in C# is probably the best way to cast reference types such as string. After you cast, you can check the result for null before using the variable, to see if the cast succeeded. This is not always needed.

Getting range of values

Another interesting method you can use is the GetRange method, which will return to you a subset of the original ArrayList in a new ArrayList. This is ideal when you know a certain part of your ArrayList has a different purpose or behavior.
=== Program that uses GetRange (C#) ===

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        //
        // Create an ArrayList with 4 strings.
        //
        ArrayList list = new ArrayList();
        list.Add("fish");
        list.Add("amphibian");
        list.Add("bird");
        list.Add("plant");
        //
        // Get last two elements in ArrayList.
        //
        ArrayList range = list.GetRange(2, 2);
        //
        // Display the elements.
        //
        foreach (string value in range)
        {
            Console.WriteLine(value); // bird, plant
        }
    }
}

=== Output of the program ===

bird
plant
Note on SetRange and RemoveRange. The SetRange method on ArrayList is also useful when you need to replace a range. However, the author has not found SetRange to be useful, as often you will just want to replace elements in a for loop.

Understanding IndexOf and LastIndexOf

The IndexOf and LastIndexOf methods on ArrayList are similar to those on strings. You pass in the value you are looking for, the start index, the number of elements to search. IndexOf will return -1 if the element could not be located.

Converting ArrayList to array

Arrays in C# offer more performance and compatibility, so you will want to convert ArrayLists to arrays. Due to the boxing and unboxing requirements with the ArrayList, you need to specify more complex casts than with the List constructed type. This site has more details on converting ArrayLists.

Understanding BinarySearch method

The BinarySearch method on ArrayList implements the binary searching algorithm. This uses a "divide and conquer" approach to finding the correct element, and only works on a pre-sorted array. For this reason, never use BinarySearch if your ArrayList might not be sorted.

Performance and memory usage

There is a significant performance penalty in using ArrayList, particularly on value types. This is because boxing occurs, which is a way the runtime turns a value type into an object. This site has some material on the cost of unboxing.

Should I use List<T> instead?

Yes, assuming the project you are working on is compatible. Older .NET deployed applications may be using ArrayList, and it is often best not to have to rewrite them. Lists not only avoid boxing or unboxing, but they also lead to clearer and less bug-prone code. This is because the compiler can check your code for type integrity before runtime.

Summary

Here we saw how you can use ArrayList in a variety of contexts in the C# language. Generally, ArrayList is best used in legacy programs. The newer .NET runtimes offer better collections in System.Collections.Generic. However, the examples here are practical for you if you are working with an old program or learning from an older book. This article is based on .NET 3.5 SP1.

C# Dictionary Examples, Keys and Values

You want to use Dictionary in your C# program for constant lookup times and to associate keys with values. Look at some examples of using Dictionary with Keys and KeyValuePair, as well as with classes and methods. This document has tips and examples for using Dictionary with keys and values using the C# programming language.
Dictionary provides fast lookup of elements.
Used when you have many different elements.
Found in the System.Collections.Generic namespace.
Specify the types of its keys and values.

Adding keys

To get started, let's add four keys with values to a Dictionary instance. Afterwards, we look inside the Dictionary using Visual Studio's debugger. You will see that the Dictionary is composed of separate keys and values. Here's the Dictionary code and then its internal view.
~~~ Program that uses Dictionary Add method (C#) ~~~

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, int> d = new Dictionary<string, int>();
        d.Add("cat", 2);
        d.Add("dog", 1);
        d.Add("llama", 0);
        d.Add("iguana", -1);
    }
}
Inside the Dictionary. Here's what the above code looks like in memory. It is represented by a collection of key and value pairs. The screenshot is worth looking at. This article is based on .NET 3.5 SP1, but the contents apply to other versions as well.
Dictionary internals

Looking up values

Here we see how you can check to see if a given string is present in a Dictionary with string keys. We look at more types of Dictionaries further on, but here is the ContainsKey method.
=== Program that uses ContainsKey (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, int> d = new Dictionary<string, int>();
        d.Add("apple", 1);
        d.Add("windows", 5);

        // See if Dictionary contains this string
        if (d.ContainsKey("apple")) // True
        {
            int v = d["apple"];
            Console.WriteLine(v);
        }

        // See if Dictionary contains this string
        if (d.ContainsKey("acorn"))
        {
            Console.WriteLine(false); // Nope
        }
    }
}

=== Output of the program ===

1
Note on efficiency. There is a more efficient method called TryGetValue on the Dictionary class, and you should definitely use it when possible. As its name implies, it tests for the key and then returns the value if it finds the key.

KeyNotFoundException

If you are running into the KeyNotFoundException, you are accessing a key in your Dictionary that doesn't exist. Dictionary is not the same as Hashtable and you must test keys for existence first, with ContainsKey or TryGetValue.

Understanding KeyValuePair

Hint: this is not in every beginner's C# book. When Dictionary, or any object that implements IDictionary, is used in a foreach loop, it returns an enumeration. In the case of Dictionary, this enumeration is in the form of KeyValuePairs.

Using foreach on Dictionary

Here we use foreach syntax and KeyValuePair generics in the foreach loop. With collections like Dictionary, we must always know the value types. With each KeyValuePair, there is a Key member and Value member.
=== Program that uses foreach on Dictionary (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Example Dictionary again
        Dictionary<string, int> d = new Dictionary<string, int>()
        {
            {"cat", 2},
            {"dog", 1},
            {"llama", 0},
            {"iguana", -1}
        };
        // Loop over pairs with foreach
        foreach (KeyValuePair<string, int> pair in d)
        {
            Console.WriteLine("{0}, {1}",
                pair.Key,
                pair.Value);
        }
        // Use var keyword to enumerate dictionary
        foreach (var pair in d)
        {
            Console.WriteLine("{0}, {1}",
                pair.Key,
                pair.Value);
        }
    }
}

=== Output of the program ===

cat, 2
dog, 1
llama, 0
iguana, -1

cat, 2
dog, 1
llama, 0
iguana, -1
Overview of the code. The code example declares and populates an example Dictionary. This Dictionary happens to indicate what animals we have and how many of them.
Using the foreach loop. It has a ShowDictionaryPair method. This method demonstrates the foreach loop and the KeyValuePair declaration. Pay careful attention to the syntax in the foreach loop. Each KeyValuePair has two members, pair.Key and pair.Value, which contain string keys and int values.
Using the var keyword. The final loop in the code shows how you can make the syntax for looping really simple by using the var keyword. This is not always desirable on some projects, however.

Getting all Dictionary keys

Here we use the Keys property and then look through each key and lookup the values. This method is slower but has the same results. Using the Keys collection and putting it in an array or List is very effective in other situations.
=== Program that gets Keys from Dictionary (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, int> d = new Dictionary<string, int>()
        {
            {"cat", 2},
            {"dog", 1},
            {"llama", 0},
            {"iguana", -1}
        };
        // Store keys in a List
        List<string> list = new List<string>(d.Keys);
        // Loop through list
        foreach (string k in list)
        {
            Console.WriteLine("{0}, {1}",
                k,
                d[k]);
        }
    }
}

=== Output of the program ===

cat, 2
dog, 1
llama, 0
iguana, -1

Benchmarking KeyValuePair usage

Using foreach on KeyValuePairs is several times faster than using Keys. This is probably because the Keys collection is not used. KeyValuePair allows us to simply look through each pair one at a time. This avoids lookups and using the garbage-collected heap for storage.
=== Benchmark for KeyValuePair foreach loop ===

KeyValuePair: 125 ms
Note:         This loops through the pairs in the Dictionary.

Keys loop:    437 ms
Note:         This gets the Keys, then loops through them.
              It does another lookup for the value.
Note on the benchmark. The author made a small change to the Keys version for clarity and performance, so these figures are only general and apply to the previous version. Using KeyValuePair is most likely still faster.

Sorting your Dictionary values

If you need to sort the values in your Dictionary, you may be perplexed at first and wonder how to order the keys properly. Fortunately, I have an article about how to do this, although it is not optimal.

Related collections

You will find other collections, such as SortedDictionary, in the base class libraries, BCL, available for you to use. However, my experience is that it is hard to get as good performance as with Dictionary.

Using different types in Dictionary

Dictionary in C# is a generic class, which means it requires you to specify a type for it to use. So, you can use an int key, just as easily as a string key. Here is an example of a Dictionary with int keys.
=== Program that uses int keys (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Use a dictionary with an int key.
        Dictionary<int, string> dict = new Dictionary<int, string>();
        dict.Add(100, "Bill");
        dict.Add(200, "Steve");
        // You can lookup the int in the dictionary.
        if (dict.ContainsKey(200))
        {
            Console.WriteLine(true);
        }
    }
}

=== Output of the program ===

True
Advanced features of Dictionary. For more advanced developers, you can use the GetHashCode() method and override it to create Dictionaries or hashes with the class. This can improve performance in those cases.

Enhancing lookup speed

To enhance lookup speed on your Dictionary, you can change the size of the keys you use. My research has shown that when you use shorter string keys, the lookup time is improved. This could create more collisions, so testing may be necessary.

Using Dictionary with LINQ

By using the ToDictionary method, which is an extension method on IEnumerable that will place the keys and values into a new Dictionary using lambda expressions.
=== Program that uses LINQ (C#) ===

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        string[] arr = new string[]
        {
            "One",
            "Two"
        };
        var dict = arr.ToDictionary(item => item, item => true);
        foreach (var pair in dict)
        {
            Console.WriteLine("{0}, {1}",
                pair.Key,
                pair.Value);
        }
    }
}

=== Output of the program ===

One, True
Two, True
Explanation of the example. The above example uses ToDictionary, which resides in the System.Linq namespace, on the string[] array to create a lookup table where both strings can be accessed in constant time, O(1).

Using ContainsValue to find values

Dictionary also helpfully implements a method called ContainsValue. This method does not enjoy the constant-time lookup speed that ContainsKey has, however. It instead searches the entire collection, making it linear in complexity.
=== Program that uses ContainsValue (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, int> d = new Dictionary<string, int>();
        d.Add("cat", 1);
        d.Add("dog", 2);
        if (d.ContainsValue(1))
        {
            Console.WriteLine(true); // true
        }
    }
}

=== Output of the program ===

True
ContainsValue method. The above example will internally loop through all elements in the Dictionary until it finds the match, or there are no more to check. MSDN: "This method is an O(n) operation, where n is Count."

Clearing and counting

You can erase all the key/value pairs within your Dictionary by using the Clear() method, which accepts no parameters. Alternatively, you can assign the variable to null. The difference between Clear and null is not important for memory, as in either case the entries are garbage-collected. Internally, I see that Clear calls Array.Clear, which is not managed code.
Counting your Dictionary. The Count method on the Dictionary collection gives you an effective way of computing the total number of keys in the instance. This is much simpler than accessing the Keys property or looping over the Dictionary to count it. This Count property is covered in more detail on this site.

Removing an entry

Here you want to eliminate an entry, not just by setting its value to null or string.Empty, but by also removing the key itself. Fortunately, you can use the Remove method.
~~~ Program that uses Remove (C#) ~~~

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, int> d = new Dictionary<string, int>();
        d.Add("cat", 1);
        d.Add("dog", 2);

        d.Remove("cat");     // Removes cat
        d.Remove("nothing"); // Doesn't remove anything
    }
}
Execution of the code. Running the code in Visual Studio, no exceptions are thrown, which means that when you remove a key that doesn't exist, nothing happens. However, Remove throws System.ArgumentNullException when it receives a null parameter.

Copying entire Dictionary

The Dictionary class has a useful constructor that allows you to easily copy all the values and keys in your Dictionary into a new Dictionary instance. You can write the logic yourself, but using this constructor improves code reuse and simplicity. This site has more information on the Dictionary copy constructor.

Parameters and return values

It is also possible to use the Dictionary constructed type in the C# language as a parameter to methods or as a return value from methods or properties. Because the Dictionary type is defined as a class, it is always passed as a reference type, meaning only 32-64 bits will be copied on the method invocation. The same principles apply when copying a Dictionary return value from a method. You can find more information on Dictionary parameters on this site.
Question

Should I use List or Dictionary?

I suggest you almost always use Dictionary when you need to do lookups. If you use List and you need to look up a key, your program may freeze if you happen to have a huge number of elements. In other words, if you use Dictionary, your program can recover from pathological, edge cases.

Using multiple variables in single key

You can sometimes use multiple variables in a key by creating a special function that transforms those variables into a string, serializing them. So, you could use the string "1,2" to mean the ints 1 and 2.

Initializing Dictionary at class level

Sometimes it is useful to have a Dictionary in your class that is allocated at the class level, not in a method or constructor. Additionally, if you have a static class then you should always initialize your Dictionary at the class level like this instead of the static constructor. Static constructors have performance penalties, which I have measured.
=== Program that uses Dictionary with class (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Example e = new Example();
        Console.WriteLine(e.GetValue());
    }
}

class Example
{
    Dictionary<int, int> _d = new Dictionary<int, int>()
    {
        {1, 1},
        {2, 3}, // <--
        {3, 5},
        {6, 10}
    };
    public int GetValue()
    {
        return _d[2]; // Example only
    }
}
=== Output of the program ===

3

Summary

In this article, we saw how you can use Dictionary with KeyValuePair to look through all pairs in the Dictionary. Additionally, we saw material on ContainsKey, which lets you check key existence. Finally, the author considers Dictionary one of the most interesting subjects in the programming world.

C# Collection Articles

The .NET Framework has an expansive selection of collections, which are classes that store many instances of data. Some collections are listed in more specific categories on the site. Nearly every C# program will use collections, as they provide an excellent way to encapsulate data.

Introduction

As shown in this program, the ArrayList is a collection found in System.Collections and it can store objects of any derived type. You don't need to worry about the type of the elements, at least until you need to know their types to use them.
--- Program that uses System.Collections [C#] ---

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        ArrayList list = new ArrayList();
        list.Add("cat");
        list.Add(2);
        list.Add(false);

        foreach (var element in list)
        {
            Console.WriteLine(element);
        }
    }
}

--- Output of the program ---

cat
2
False

List implementations

Although the List generic type is the best implementation available for its purpose on the .NET Framework, there are other versions of lists that you can use instead. These articles show the ArrayList, the LinkedList and the SortedList types.

Hashtable

The Hashtable is a lookup data structure that uses a hash code to find elements quickly. The newer Dictionary collection is usually more appropriate for programs when available.

Tuple

You can use the Tuple collection to store data in new versions of the .NET Framework. The Tuple enables you to use strongly typed fields instead of a custom class.

Lookup implementations

There are many versions of lookup data structures other than the Hashtable and Dictionary in the .NET Framework. This section covers several of them; it also shows the implementation of a custom MultiMap data structure.

BitArray

The BitArray is an abstract data type for representing bit data. It uses an efficient representation of the underlying bits, which can make it a good choice for programs that have many boolean values.

Stack

The Stack collection gives you the ability to push and pop elements onto its top. You can implement certain kinds of parsers with stacks. You could use an array for this, but the Stack presents a clearer interface for your code.

Queue

The Queue implements a different algorithm than the Stack: when you remove an element, the first element added is removed instead of the most recently added. The Queue can be used for certain kinds of caches.

Sets

The HashSet implements set logic in its many instance methods. You can use methods such as Union on different HashSets for your program's logic. You could use a Dictionary instead, but the HashSet may be clearer if you are familiar with set theory. Also, the SortedSet is implemented as a binary tree but also provides set logic.

KeyValuePair

One of the most useful data structures in the C# language is the KeyValuePair. This gives you a way to store a key and a value together in a struct; it is a simple form of a Tuple. The Dictionary collection uses KeyValuePairs in some of its methods.

Lazy

You can use the Lazy type to implement the lazy instantiation pattern in your programs. The linked article has an example for using the Lazy type. (The Lazy class has nothing to do with the Sleep method.)

Capacities

An optimization you can use on your collections is to set capacities in their constructors. This will reduce the number of allocations in some programs, which further reduces the memory pressure and the burden of garbage collection.

 


 


 


 


 

 


 

4 comments:

  1. Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a .Net developer learn from Dot Net Online Training from India. or learn thru ASP.NET Essential Training Online . Nowadays Dot Net has tons of job opportunities on various vertical industry.
    JavaScript Online Training from India

    ReplyDelete
  2. From your discussion I have understood that which will be better for me and which is easy to use. Really, I have liked your brilliant discussion. I will comThis is great helping material for every one visitor. You have done a great responsible person. i want to say thanks owner of this blog.

    Java training in Chennai

    Java training in Bangalore

    ReplyDelete
  3. After reading this web site I am very satisfied simply because this site is providing comprehensive knowledge for you to audience.
    Thank you to the perform as well as discuss anything incredibly important in my opinion. We loose time waiting for your next article writing in addition to I beg one to get back to pay a visit to our website in



    Selenium training in bangalore
    Selenium training in Chennai
    Selenium training in Bangalore
    Selenium training in Pune
    Selenium Online training

    ReplyDelete
  4. After reading this web site I am very satisfied simply because this site is providing comprehensive knowledge for you to audience.
    Thank you to the perform as well as discuss anything incredibly important in my opinion. We loose time waiting for your next article writing in addition to I beg one to get back to pay a visit to our website in



    Selenium training in bangalore
    Selenium training in Chennai
    Selenium training in Bangalore
    Selenium training in Pune
    Selenium Online training

    ReplyDelete