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. ICollection8742468051c85b06f0a0af9e3e506b5c 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 ICollection8742468051c85b06f0a0af9e3e506b5c. ICollection does not provide the functions of editing collections, namely Add and Remove. Including checking whether the element exists Contains is not supported.

​IList8742468051c85b06f0a0af9e3e506b5c 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.

​IReadOnlyList8742468051c85b06f0a0af9e3e506b5c

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

IDictionary8c189faf63255a5ea96468ba21dd0564

IDictionary provides access to a collection of key-value pairs. It also inherits ICollection8742468051c85b06f0a0af9e3e506b5c 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. Dictionary8c189faf63255a5ea96468ba21dd0564

2. 
   

3. ## SortedDictionary8c189faf63255a5ea96468ba21dd0564

4. 
   

5. SortedList8c189faf63255a5ea96468ba21dd0564

Dictionary8c189faf63255a5ea96468ba21dd0564

Dictionary8c189faf63255a5ea96468ba21dd0564 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).

Dictionary8c189faf63255a5ea96468ba21dd0564The 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 Dictionaryb6842da76bed01162354d37c4f2d3464 in a certain order.

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

SortedDictioanry8c189faf63255a5ea96468ba21dd0564

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

​SortedList8c189faf63255a5ea96468ba21dd0564 ​

SortedList8c189faf63255a5ea96468ba21dd0564 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. List8742468051c85b06f0a0af9e3e506b5c

2. 
   

3. LinkedList8742468051c85b06f0a0af9e3e506b5c

4. 
   

5. HashSet8742468051c85b06f0a0af9e3e506b5c

6. 
   

7. SortedSet8742468051c85b06f0a0af9e3e506b5c

8. 
   

9. Stack8742468051c85b06f0a0af9e3e506b5c

10. 
    

11. Queue8742468051c85b06f0a0af9e3e506b5c

List8742468051c85b06f0a0af9e3e506b5c

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.

LinkedList8742468051c85b06f0a0af9e3e506b5c

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.

HashSet8742468051c85b06f0a0af9e3e506b5c

HashSet is an unordered set that can maintain uniqueness. We can also think of HashSet as Dictionary8c189faf63255a5ea96468ba21dd0564, 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.

SortedSet8742468051c85b06f0a0af9e3e506b5c

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.

Stack8742468051c85b06f0a0af9e3e506b5c

Last in, first out queue
​Does not support accessing

by pressing the subscript

Queu8742468051c85b06f0a0af9e3e506b5c

First in first out queue
​Does not support accessing

by pressing the subscript Recommended usage scenarios

# gather	Order in order	Lianshun Storage	Direct access method	interview time	Operation time	Remark
Dictionary		yes	Key	Key: O(1)	O(1)	The fastest access performance, does not support sorting
SortedDinctionary	Sort in order	no	Key	Key: O(log n)	O(log n)	Tradeoffs for fast access and support for sorting
SortedList	Sort in order	yes	Key	Key: O(log n)	O(n)	Similar to SortedDictionary, except that data is used internally instead of the tree as the storage structure.
List	Users can precisely control the position of elements	yes	Index	Index: O(1) Value: O(n)	O(n)	Best suited for small collections that require direct access to each element.
LinkedList	Users can precisely control the position of elements	no	not support	Value: O(n)	O(1)	Best suited for scenarios where direct access to individual elements is not required, but very frequent additions/removals to the collection are required.
HashSet	not support	yes	Key	Key: O(1)	O(1)	A collection that maintains the uniqueness of elements. Sorting is not supported
SortedSet	Arrange in order	no	Key	Key: O(log n)	O(log n)	Can maintain element uniqueness and support sorting.
Stack	LIFO	yes	Only the top element can be obtained	Top: O(1)	O(1)
Queue	FIFO	yes	Only the bottom element can be obtained	Front: O(1)	O(1)

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 List8742468051c85b06f0a0af9e3e506b5c.

1. HashTable was later replaced by Dictionary8c189faf63255a5ea96468ba21dd0564.

2. 
   

3. Queue was later replaced by Queue8742468051c85b06f0a0af9e3e506b5c.

4. 
   

5. SortedList was later replaced by SortedList8742468051c85b06f0a0af9e3e506b5c.

6. 
   

7. Stack was later replaced by Stack8742468051c85b06f0a0af9e3e506b5c.

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!