Detailed explanation of the graphic code of C# collection types

Collections in C

# Collections are an important part of .NET FCL (Framework Class Library) and one of the most commonly used functions in our development. They are almost everywhere. As the saying goes, know what it is and why it is so. When you see IEnumerable, IEnumerator, and ICollection, do you know the differences between them? In addition to List and Dictionary, what other collection classes have you used? Without further ado, today we will take a look at some of the interfaces that define collection classes and their implementations.

Collection interface

Let’s first take a look at what interfaces FCL provides us:

​

​IEnumerable and IEnumberator

public interface IEnumerator
{
 
    bool MoveNext();
    object Current {  get; }
    void Reset();
}

IEnumerator defines the basic method for us to traverse the collection so that we can achieve one-way forward access to each element in the collection. IEnumerable has only one method, GetEnumerator, which is the traverser.

public interface IEnumerable
{
    IEnumerator GetEnumerator();
}

Note: The foreach we often use is a kind of syntactic sugar. In fact, it still calls the traversal function implemented by Current and MoveNext in Enumerator.

List<string> list = new List<string>() 
{ 
    "Jesse",
    "Chloe",
    "Lei",
    "Jim",
    "XiaoJun"
};
 
// Iterate the list by using foreach
foreach (var buddy in list)
{
    Console.WriteLine(buddy);
}
 
// Iterate the list by using enumerator
List<string>.Enumerator enumerator = list.GetEnumerator();
while (enumerator.MoveNext())
{
    Console.WriteLine(enumerator.Current);
}

The foreach and enumerator used in the above code will eventually be translated into enumerator's MoveNext and Current in IL.

IEnumerable is a very useful interface. The benefits of implementing it include:

1. Support foreach statement

2. 
   

3. Interacts with other libraries as a standard collection class

4. 
   

5. Meet the needs of more complex collection interfaces

6. 
   

7. Support collection initializer

Of course, there are many ways to achieve it, as follows:

1. If our collection comes by encapsulating other collection classes, then we can directly return the enumerator

2. 
   

3. of this collection. Return

4. 
   

5. # through yield return Implement our own IEnumerator to achieve

Here I will show you how to return enumerator

public class BuddyList : IEnumerable
{
    private string[] data= new string[]
    { 
        "Jesse",
        "Chloe",
        "Lei",
        "Jim",
        "XiaoJun"
    };
 
    public IEnumerator GetEnumerator()
    {
        foreach (var str in data)
        {
            yield return str;
        }
    }
}
 
var myBuddies= new BuddyList();
foreach (var str in myBuddies)
{
    Console.WriteLine(str);
}

through yield. ICollection and ICollection

From the first picture at the top, we can know that ICollection is directly inherited from IEnumerable. In fact, this is also the case. We can say that ICollection supports more functions than IEnumerable, not only providing basic traversal functions, but also including:

1. Count the number of collections and elements

2. 
   

3. Get the subscript of the element

4. 
   

5. Determine whether there is

6. 
   

7. Add elements to the end

8. 
   

9. Remove elements and so on. . .

ICollection is slightly different from ICollection. ICollection does not provide the functions of editing collections, namely Add and Remove. Including checking whether the element exists Contains is not supported.

​IList and IList

IList directly inherits from ICollection and IEnumerable. So it includes the functionality of both, and supports accessing and adding elements based on subscripts. IndexOf, Insert, RemoveAt and so on. We can say that IEnumerable supports the least functions, only traversal. ICollection supports slightly more functions, including not only traversing but also maintaining the collection. And IList is the most complete version.

​IReadOnlyList

This is a new interface type in Framework 4.5. It can be regarded as a shortened version of IList, removing all functions that may change this collection. For example: Add, RemoveAt, etc.

IDictionary

IDictionary provides access to a collection of key-value pairs. It also inherits ICollection and IEnumerable, and extends the method of accessing and operating data through Key.

Associative generic collection class

The associative collection class is what we often call a key-value pair collection, allowing us to access and maintain the collection through Key. Let’s first take a look at what generic association collection classes FCL provides us:

1. Dictionary

2. 
   

3. ## SortedDictionary

4. 
   

5. SortedList

Dictionary

Dictionary is probably our most commonly used associative collection. The time it takes to access, add, and delete data is the fastest among all collection classes, because it uses Hashtable internally as a storage structure, so no matter No matter how many key-value pairs are stored, the time it takes to query/add/delete is the same, and its time complexity is O(1).

DictionaryThe advantage is that it is fast to search and insert, so what are its disadvantages? Because Hashtable is used as the storage structure, it means that the data inside is arranged out of order, so it takes a little effort to traverse the data in Dictionary in a certain order.

The type as TKey must implement GetHashCode() and Equals() or provide a IEqualityComparer, otherwise operate Problems may arise.

SortedDictioanry

SortedDictionary and Dictionary are roughly similar, but there is a slight difference in implementation. SortedDictionary uses a binary tree as the storage structure. And arranged in key order. In this case, the TKey of SortedDictionary must implement IComparable. If you want to query quickly and support sorting well, then use SortedDictionary.

​SortedList ​

SortedList is another associative collection that supports sorting. But the difference is that SortedList actually stores data in an array. That is to say, the addition and removal operations are linear, and the time complexity is O(n), because operating the elements may cause all data to move. But because binary search is used during search, the search performance will be better, and the time complexity is O(log n). Therefore, the recommended usage scenario is as follows: If you want to search quickly, and you want the collection to be arranged in the order of keys, and the last collection operation (addition and removal) is relatively small, it is SortedList.

Non-associative generic collection class

Non-associative collections are collection classes that do not require key operations. Usually we can use the elements themselves or subscripts to operate. FCL mainly provides us with the following non-associative generic collection classes.

1. List

2. 
   

3. LinkedList

4. 
   

5. HashSet

6. 
   

7. SortedSet

8. 
   

9. Stack

10. 
    

11. Queue

List

The generic List class provides a collection type with no limit on length. List maintains an array of a certain length internally (the default initial length is 4). When the length of the inserted element exceeds 4 or the initial length, it will be re-created. New array, the length of this new array is 2 times the initial length (not always 2 times, when it is found that it continues to expand, the multiple will become larger), and then copy the original array. So if we know how many elements we are going to use this collection to hold, we can specify the initial value when creating it, thus avoiding repeatedly creating new arrays and copying values.

In addition, since the internal essence is an array, adding data to the List may not be faster, but adding or deleting data at the head or middle of the data is relatively less efficient because it will affect the rearrangement of other data.

LinkedList

LinkedList maintains a two-way linked list internally, which means that the performance of adding or deleting data anywhere in LinkedList is very fast. Because it does not cause other elements to move. Under normal circumstances, List is enough for us, but if the addition and deletion operations in the middle of this collection are very frequent, it is recommended to use LinkedList.

HashSet

HashSet is an unordered set that can maintain uniqueness. We can also think of HashSet as Dictionary, except that both TKey and TValue point to the same object. HashSet is very suitable when we need to keep the elements in the set unique but do not need to be arranged in order.

HashSet does not support subscript access.

SortedSet

SortedSet and HashSet are just like SortedDictionary and Dictionary. Do you still remember the difference between the two? SortedSet is also a binary tree internally, used to support arranging elements in order.

Stack

Last in, first out queue
​Does not support accessing

Queu

First in first out queue
​Does not support accessing

by pressing the subscript Recommended usage scenarios

Non-generic class collection

The generic collection class came out in .NET 2.0, which means that there was no such convenient thing in .NET 1.0. Now basically we don't use these collection classes anymore, except when doing some work to maintain compatibility with old code. Let’s take a look at what collection classes can be used by .NET programmers in the 1.0 era.

1. ArraryList

Later replaced by List.

1. HashTable was later replaced by Dictionary.

2. 
   

3. Queue was later replaced by Queue.

4. 
   

5. SortedList was later replaced by SortedList.

6. 
   

7. Stack was later replaced by Stack.

Thread-safe collection class

1. ConcurrentQueue thread-safe version of Queue

2. 
   

3. ConcurrentStack thread-safe version of Stack

4. 
   

5. ConcurrentBag thread-safe object collection

6. 
   

7. ConcurrentDictionary Thread-safe Dictionary

8. 
   

9. BlockingCollection

The collection classes provided by .NET are one of our most commonly used tool classes. I hope this article can help everyone better understand these collection classes. Of course, I personally feel that there are still imperfections. For example, HashTable and Binary Search Tree are not studied in detail, and the comparison between one-way linked lists and doubly linked lists is not mentioned in this article. Interested friends can learn more about it.

The above is the detailed content of Detailed explanation of the graphic code of C# collection types. For more information, please follow other related articles on the PHP Chinese website!