Skip to content
BigBro222's Blog
LinkedInGitHub

Collections in C# (The basics 1)

— C# basics — 6 min read

1. What is collections

There are usually three default namespaces when creating a new C# script in Unity, they are

1using System.Collections;
2using System.Collections.Generic;
3using UnityEngine;

Of Course, you can change the default scripts using this method. But still, it’s easy to see that collection is a very important concept in programming, especially C#.

According to Microsoft coding guide Collections provide a more flexible way to work with groups of objects. Unlike arrays, the group of objects you work with can grow and shrink dynamically as the needs of the application change.

The System.Collection namespace contains interfaces and classes that define various collections of objects, such as lists, queues, bit arrays, hash tables, and dictionaries.

The System.Collection.Generic namespace contains interfaces and classes that define generic collections, which allow users to create strongly typed collections that provide better type safety and performance than non-generic strongly typed collections.

2. System.Collection.Generic

If your collection contains elements of only one data type, you can use one of the classes in the System.Collections.Generic namespace. A generic collection enforces type safety so that no other data type can be added to it. When you retrieve an element from a generic collection, you do not have to determine its data type or convert it.

There are 9 basic classes:

  1. Dictionary<TKey,TValue>
  2. SortedDictionary<TKey,TValue>
  3. SortedList<TKey,TValue>
  4. List<T>
  5. LinkedList<T>
  6. HashSet<T>
  7. SortedSet<T>
  8. Stack<T>
  9. Queue<T>

2.1 Collections with<key, value> pair

2.1.1 Dictionary<TKey,TValue>

Dictionary is a very common data structure to access each element, it is a generic collection that stores key-value pairs in no particular order. It always takes the same time no matter how many elements is stored with an internal mechanism of Hashtable.

pros: take the same time to query, add, remove an element no matter how many elements are stored

cons: dictionary has no particular order, so it will take time to iterate through the dictionary

1// Create a new dictionary of strings, with string keys.
2Dictionary<string, string> openWith =
3    new Dictionary<string, string>();
4// Add some elements to the dictionary. There are no
5// duplicate keys, but some of the values are duplicates.
6openWith.Add("txt", "notepad.exe");
7// The indexer can be used to change the value associated
8// with a key.If a key does not exist, setting the indexer for that key
9// adds a new key/value pair.
10openWith["rtf"] = "winword.exe";
11Console.WriteLine("For key = \"rtf\", value = {0}.",
12    openWith["rtf"]);
13

14// The indexer throws an exception if the requested key is
15// not in the dictionary.
16catch (KeyNotFoundException)
17{
18    Console.WriteLine("Key = \"tif\" is not found.");
19}
20// When a program often has to try keys that turn out not to
21// be in the dictionary, TryGetValue can be a more efficient
22// way to retrieve values.
23string value = "";
24openWith.TryGetValue("tif", out value)
25

26// ContainsKey can be used to test keys before inserting
27// them.
28openWith.ContainsKey("ht"))
29// When you use foreach to enumerate dictionary elements,
30// the elements are retrieved as KeyValuePair objects.
31foreach( KeyValuePair<string, string> kvp in openWith )
32{
33    Console.WriteLine("Key = {0}, Value = {1}",
34        kvp.Key, kvp.Value);
35}
36

37// To get the values alone, use the Values property.
38Dictionary<string, string>.ValueCollection valueColl =
39// To get the keys alone, use the Keys property.
40Dictionary<string, string>.KeyCollection keyColl =
41    openWith.Keys;
42

43// Use the Remove method to remove a key/value pair.
44openWith.Remove("doc");

2.1.2 SortedDictionary<TKey,TValue>

The usage of SortedDictionary is quite similar to Dictionary although it’s implemented using binary-tree.It has O(log n) retrieval.While using foreach loop, the output will be ordered by key values in ascending order（on the other hand, dictionary will be ordered by the time the keyvalue pair is added）

note that TKey must implement IComparable<TKey> interface in order to be sorted.（I haven’t find any useful scenario for using SortedDictionary yet, except for that the unique performance while doing foreach loop）

1SortedDictionary<int, string> sd = new SortedDictionary<int, string>();
2        sd.Add(9, "九");
3        sd.Add(8, "八");
4        sd.Add(7, "七");
5        sd.Add(6, "六");
6        sd.Add(1, "一");
7        sd.Add(5, "五");
8        sd.Add(3, "三");
9        sd.Add(2, "二");
10        Debug.Log("-----SortDictionary-----");
11        //print the dictionary
12        foreach (var item in sd)
13        {
14            string info = string.Format(" Key = {0}, Value = {1}", item.Key, item.Value);
15            Debug.Log(info);
16        }
17

18//foreach loop with print from key 1 to key 9

2.1.3 SortedList<Tkey,TValue>

The SortedList<TKey,TValue> generic class is an array of key/value pairs with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary<TKey,TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

Another difference is that SortedList<TKey,TValue> supports get values and keys by index

1// Create a new sorted list of strings, with string
2        // keys.
3        SortedList<string, string> openWith =
4            new SortedList<string, string>();
5

6        // Add some elements to the list. There are no
7        // duplicate keys, but some of the values are duplicates.
8        openWith.Add("txt", "notepad.exe");
9        openWith.Add("bmp", "paint.exe");
10

11        // ContainsKey can be used to test keys before inserting
12        // them.
13        openWith.ContainsKey("ht")
14

15        // To get the values alone, use the Values property.
16        IList<string> ilistValues = openWith.Values;
17        // To get the keys alone, use the Keys property.
18        IList<string> ilistKeys = openWith.Keys;
19

20        // Use the Remove method to remove a key/value pair.
21        Console.WriteLine("\nRemove(\"doc\")");
22        openWith.Remove("doc");
23

24        //get the index of a key
25        Debug.Log("Key 7 is has the index of"+sd.IndexOfKey(7));
26        //remove the item with biggest key
27        openWith.RemoveAt(sd.Count - 1);
28

29        //get value by index
30        string value=(openWith.Values)[3];
31        Debug.Log("the forth value is " + value);

2.2.1 List<T>

Represents a strongly typed list of objects that can be accessed by index. Provides methods to search, sort, and manipulate lists.

The List<T> class is the generic equivalent of the ArrayList class. It implements the IList<T> generic interface by using an array whose size is dynamically increased as required. The capacity of the List<T> is increased by automatically reallocating the internal array to accommodate the new elements, and the existing elements are copied to the new array before the new elements are added. (This can be very heavy and waste a lot of rooms when the items number is huge)

1//The default length is 4 and is increased exponentially
2int num = (_items.Length == 0) ? 4 : (_items.Length * 2)

The TrimExcess method is used to reduce the capacity to match the count, and the Capacity and Count properties are displayed. If the unused capacity had been less than 10 percent of total capacity, the list would not have been resized.

1// Create a list of parts.
2        List<Part> parts = new List<Part>();
3

4        // Add parts to the list.
5        parts.Add(new Part() { PartName = "crank arm", PartId = 1234 });
6        parts.Add(new Part() { PartName = "chain ring", PartId = 1334 });
7

8        // Check the list for part #1734. This calls the IEquatable.Equals method
9        // of the Part class
10        parts.Contains(new Part { PartId = 1734, PartName = "" }));
11

12        // Insert a new item at position 2.
13        parts.Insert(2, new Part() { PartName = "brake lever", PartId = 1834 });
14

15        // This will remove part 1534 even though the PartName is different,
16        // because the Equals method only checks PartId for equality.
17        parts.Remove(new Part() { PartId = 1534, PartName = "cogs" });
18

19        // This will remove the part at index 3.
20        parts.RemoveAt(3);
21

22        string[] input = { "Brachiosaurus",
23                           "Amargasaurus",
24                           "Mamenchisaurus" };
25

26        List<string> dinosaurs = new List<string>(input);
27        dinosaurs.AddRange(dinosaurs);
28

29        dinosaurs.RemoveRange(2, 2);
30

31        dinosaurs.InsertRange(3, input);
32

33        string[] output = dinosaurs.GetRange(2, 3).ToArray();

The List<T> class uses both an equality comparer and an ordering comparer.

  • Contains, IndexOf, LastIndexOf, and Remove use an equality comparer for the list elements. If type T implements the IEquatable<T> generic interface, then the equality comparer is the Equals(T) method of that interface; otherwise, the default equality comparer is Object.Equals(Object).
  • BinarySearch and Sort use an ordering comparer for the list elements. If type T implements the IComparable<T> generic interface, then the default comparer is the CompareTo(T) method of that interface; otherwise, if type T implements the nongeneric IComparable interface, then the default comparer is the CompareTo(Object) method of that interface. If type T implements neither interface, then there is no default comparer, and a comparer or comparison delegate must be provided explicitly. The List<T> is not guaranteed to be sorted. You must sort the List<T> before performing operations (such as BinarySearch) that require the List<T> to be sorted.
  • List<T> accepts null as a valid value for reference types and allows duplicate elements.

2.2.2 LinkedList<T>

You can remove nodes and reinsert them, either in the same list or in another list, which results in no additional objects allocated on the heap.

Each node in a LinkedList<T> object is of the type LinkedListNode<T>. Because the LinkedList<T> is doubly linked, each node points forward to the Next node and backward to the Previous node.

LinkedList<T> accepts null as a valid Value property for reference types and allows duplicate values.

The LinkedList<T> class does not support chaining, splitting, cycles, or other features that can leave the list in an inconsistent state. The list remains consistent on a single thread. The only multithreaded scenario supported by LinkedList<T> is multithreaded read operations.

LinkedList is mostly used for a more precise operation

1// Create the link list.
2        string[] words =
3            { "the", "fox", "jumps", "over", "the", "dog" };
4        LinkedList<string> sentence = new LinkedList<string>(words);
5        Console.WriteLine(sentence.Contains("jumps"));
6

7        // Add the word 'today' to the beginning of the linked list.
8        sentence.AddFirst("today");
9

10        // Move the first node to be the last node.
11        LinkedListNode<string> mark1 = sentence.First;
12        sentence.RemoveFirst();
13        sentence.AddLast(mark1);
14       
15        // Move the last node to be the first node.
16        mark1 = sentence.Last;
17        sentence.RemoveLast();
18        sentence.AddFirst(mark1);
19       
20

21        // Indicate the last occurence of 'the'.
22        sentence.RemoveFirst();
23        LinkedListNode<string> current = sentence.FindLast("the");
24

25        // Indicate 'fox' node.
26        current = sentence.Find("fox");
27 
28

29        // Add 'quick' and 'brown' before 'fox':
30        sentence.AddBefore(current, "quick");
31        
32        // Keep a reference to the current node, 'fox',
33        // and to the previous node in the list. Indicate the 'dog' node.
34        mark1 = current;
35        LinkedListNode<string> mark2 = current.Previous;
36        current = sentence.Find("dog");

2.2.3 Stack<T> and Queue<T>

StackRepresents a variable size last-in-first-out (LIFO) collection of instances of the same specified type. Stack<T> is implemented as an array.

Queue implements a generic queue as a circular array. Objects stored in a Queue<T> are inserted at one end and removed from the other. （first-in-first-out）

Stacks and queues are useful when you might want to discard an element after retrieving its value. Use Queue<T> if you need to access the information in the same order that it is stored in the collection. Use System.Collections.Generic.Stack<T> if you need to access the information in reverse order.

A common use for System.Collections.Generic.Stack<T> is to preserve variable states during calls to other procedures.

-Three main operations can be performed on a System.Collections.Generic.Stack<T> and its elements:

  • Push inserts an element at the top of the Stack.
  • Pop removes an element from the top of the Stack.
  • Peek returns an element that is at the top of the Stack but does not remove it from the Stack.

As elements are added to a Stack<T>, the capacity is automatically increased as required by reallocating the internal array.

If Count is less than the capacity of the stack, Push is an O(1) operation. If the capacity needs to be increased to accommodate the new element, Push becomes an O(n) operation, where n is Count. Pop is an O(1) operation.

1Stack<string> stack = new Stack<string>();
2stack.Push("object");//add data
3stack.Peek();//get data without delete
4stack.Pop();//get data and delete from the stack

-Three main operations can be performed on a Queue<T> and its elements:

  • Enqueue adds an element to the end of the Queue<T>.
  • Dequeue removes the oldest element from the start of the Queue<T>.
  • Peek peek returns the oldest element that is at the start of the Queue<T> but does not remove it from the Queue<T>.
1//Queue is useful for performing tasks
2Queue<string> queue = new Queue<string>();
3queue.Enqueue("object");//add data
4queue.Enqueue("object1");
5foreach (var item in queue)
6{
7 Console.WriteLine(item);
8}
9queue.Dequeue();//get the earliest item and delete from the queue
10queue.Peek();//get data without delete

2.2.4 HashSet<T>

The HashSet<T> class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order. A HashSet<T> object's capacity automatically increases as elements are added to the object.

The HashSet<T> class is based on the model of mathematical sets and provides high-performance set operations similar to accessing the keys of sed on the model of mathematical sets and provides high-performance set operations similar to accessing the keys of the  Dictionary<TKey,TValue> .

HashSet<T> provides many mathematical set operations, such as set addition (unions) and set subtraction.

1HashSet<int> evenNumbers = new HashSet<int>();
2HashSet<int> oddNumbers = new HashSet<int>();
3// Populate numbers with just even numbers.
4evenNumbers.Add(i * 2);
5// Populate odd numbers with just odd numbers.
6oddNumbers.Add((i * 2) + 1);
7

8// Create a new HashSet populated with even numbers.
9HashSet<int> numbers = new HashSet<int>(evenNumbers);
10numbers.UnionWith(oddNumbers);
11

12// Ensures that this hash set can hold the specified number of elements without growing.
13evenNumbers.EnsureCapacity(30);
14

15//The lower range of values is then removed from the larger set using the ExceptWith method.
16highNumbers.ExceptWith(lowNumbers);
17

18//Modifies the current HashSet<T> object to contain only elements that are present in that object and in the specified collection.
19highNumbers.IntersectWith(lowNumbers);
20

21//bool value of if the allNumbers subset has some elements in common with the lowNumbers
22lowNumbers.Overlaps(allNumbers));
23

24//bool value of allNumbers and lowNumbers are equal sets
25allNumbers.SetEquals(lowNumbers));
26

27// Show the results of sub/superset testing
28lowNumbers.IsSubsetOf(allNumbers));
29allNumbers.IsSupersetOf(lowNumbers));
30lowNumbers.IsProperSubsetOf(allNumbers));
31allNumbers.IsProperSupersetOf(lowNumbers));
32

33// Check if the hash table contains 0 and, if so, remove it.
34if (numbers.Contains(0)) {
35    numbers.Remove(0);
36}
37

38// Remove all odd numbers.
39numbers.RemoveWhere(IsOdd);
40bool IsOdd(int i)
41{
42    return ((i % 2) == 1);
43}
44

45//to contain only the values that are not present in both sets.
46lowNumbers.SymmetricExceptWith(highNumbers);
47

48//release the memory
49collection-csharp-basic-1 copyNumbers.TrimExcess();
50

51// Create a new HashSet populated with even numbers.Constructor
52HashSet<int> numbers = new HashSet<int>(evenNumbers);

2.2.5 SortedSet<T>

Represents a collection of objects that is maintained in sorted order. The relationship between SortedSet and HashSet is similar to the relationship between Dictionary and SortedDictionary. Implemented using binary-tree.It has O(log n) retrieval. While using foreach loop, the output will be ordered in ascending order（and can be reversed by the reverse method）.

2.2.6 PriorityQueue<TElement,TPriority>

There is already an implementation on the official documentation, but cannot be used in Unity right now. Might need further investigation in the future.

2.3 Concurrent collections

There are several collections for multithreading, is under System.Collections.Concurrent namespace, which I think I will investigate on it after I finish my multithreading theme learning.

The previous are mostly about how to use generic collections, here is a link for further discussion for analysing the source code. I will take a further look in the near future

Collections in C# (The basics 1)

Collections in C# (The basics 2)

Collections in C# (The basics 3)

Reference

https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/collections

System.Collection

System.Collection.Generic

The implementation of Dictionary (ZH)

Systems.Collections.Concurrent

从零开始分析C#所有常用集合类的设计（源码向）

© 2023 by BigBro222's Blog. All rights reserved.