확실히 바퀴의 재발명!자작 C# 컬렉션 총서 Arc.Collection

Arc.Collection
Arc.Collection은 다양한 컬렉션을 구현하는 빠른 C#장서 라이브러리입니다.저희 집은 GiitHub입니다.archi-Doc/Arc.Collection에서.
수장하다
설명UnorderedList<T>List<T>와 동일)
색인에 접근할 수 있는 대상 목록입니다.UnorderedLinkedList<T>LinkedList<T>와 동일)
양방향 목록Node에서 사용할 수 있습니다.OrderedList<T>정렬된 접근 가능한 인덱스의 대상 목록입니다.필요IComparable<T> 또는 IComparer<T>.OrderedKeyValueList<TKey, TValue> ( SortedList<TKey,TValue> )
Key/Value 목록은 정렬 후에 색인에 액세스할 수 있습니다.필요IComparable<TKey> 또는 IComparer<TKey>.OrderedMap<TKey, TValue> ( SortedDictionary<TKey, TValue> )
Key 정렬됨(Red-Black Tree)의 Key/Value 모음집입니다.SortedDictionary<TKey, TValue>와 달리 Node는 방문할 수 있고 TKey는 비어 있을 수 있다.필요IComparable<TKey> 또는 IComparer<TKey>.OrderedSet<T> ( SortedSet<T> )
정렬된 모음(Red-Black Tree)입니다.OrderedSet<T>는 OrderedMap<TKey, TValue> 서브집합이고 실제로는 OrderedMap<T, int>(TValue는 int이며 사용하지 않음)이다.OrderedMultiMap<TKey, TValue>Key 정렬됨(Red-Black Tree)의 Key/Value 모음집입니다.반복 키를 사용할 수 있습니다.OrderedMultiSet<T>정렬된 모음(Red-Black Tree)입니다.객체를 반복할 수도 있습니다.UnorderedMap<TKey, TValue> ( Dictionary<TKey, TValue> )
Hash table에서 관리하는 Key/Value 모음집입니다.UnorderedMap<TKey, TValue>는 Dictionary<TKey, TValue>보다 느리고 UnorderedMap<TKey, TValue>는 조작Node index할 수 있고 TKey도 비울 수 있다.UnorderedSet<T> UnorderedMap<TKey, TValue>의 서브집합은 실제로UnorderedMap<T, int>(TValue는 int이고 사용하지 않음)이다.UnorderedMultiMap<TKey, TValue>Hash table에서 관리하는 Key/Value 모음집입니다.반복 키를 사용할 수 있습니다.UnorderedMultiSet<T> UnorderedMap<TKey, TValue>의 서브집합은 실제로UnorderedMap<T, int>(TValue는 int이고 사용하지 않음)이다.
보통 제니릭 소장품이 있는데.
바퀴의 재발명이라고 할 수 밖에 없어요. CrossLink 필요하니까 했어요.실장 작업은 매우 재미있다.
Quick Start
Package Manager Constore를 통해 설치합니다.

Install-Package Arc.Collection

샘플 코드.일반 소장품과 동일하게 사용할 수 있습니다.

using Arc.Collection;

var array = new int[] { 2, 1, 3, };
var os = new OrderedSet<int>(array);

ConsoleWriteIEnumerable("Array:", array); // 2, 1, 3
ConsoleWriteIEnumerable("OrderedSet:", os); // 1, 2, 3

Console.WriteLine("Add 4, 0");
os.Add(4);
os.Add(0);
ConsoleWriteIEnumerable("OrderedSet:", os); // 0, 1, 2, 3, 4

static void ConsoleWriteIEnumerable<T>(string header, IEnumerable<T> e)
{
    Console.WriteLine(string.Format("{0,-12}", header) + string.Join(", ", e));
}

PerformanceOrderedSet<T>와SortedSet<T>처럼 데이터 구조는 붉은 나무와 검은 나무를 사용했다.차이점OrderedSet<T>은 내부에 부모 노드에 대한 링크가 있고 노드에 접근할 수 있다는 점이다.SortedSet<T> 고속 동작을 시작한다.일반적인 사용도 빠르고 사용Node의 접근 속도가 절대 빠르다.
Reference: System.Collections.Generic.SortedSet<T>Method
Length
Mean
Error
StdDev
Median
Gen 0
Allocated
NewAndAdd_SortedSet
100
4,160.11 ns
16.214 ns
22.730 ns
4,157.33 ns
1.0223
4288 B
NewAndAdd_OrderedSet
100
3,384.44 ns
8.101 ns
12.126 ns
3,384.49 ns
1.4381
6024 B
NewAndAdd2_SortedSet
100
8,709.41 ns
151.310 ns
221.788 ns
8,551.29 ns
1.8463
7776 B
NewAndAdd2_OrderedSet
100
8,042.45 ns
53.162 ns
79.570 ns
8,043.79 ns
2.0599
8664 B
AddRemove_SortedSet
100
422.21 ns
0.637 ns
0.934 ns
421.94 ns
0.0381
160 B
AddRemove_OrderedSet
100
172.03 ns
0.423 ns
0.593 ns
171.93 ns
0.0534
224 B
AddRemoveNode_OrderedSet
100
128.04 ns
0.327 ns
0.469 ns
127.89 ns
0.0534
224 B
AddRemoveReuse_OrderedSet
100
118.24 ns
0.239 ns
0.335 ns
118.13 ns
-
-
AddRemoveReplace_OrderedSet
100
11.76 ns
0.211 ns
0.289 ns
11.54 ns
-
-
Enumerate_SortedSet
100
1,664.30 ns
17.294 ns
25.349 ns
1,682.97 ns
0.0401
168 B
Enumerate_OrderedSet
100
1,218.03 ns
4.344 ns
6.230 ns
1,219.51 ns
0.0114
48 B
Collections
각 모음집의 특징.구분해서 사용하세요.
Name
Structure
Access
Add
Remove
Search
Sort
Enum.UnorderedList<T>Array
Index
O(1)
O(n)
O(n)
O(n log n)
O(1)UnorderedLinkedList<T>Linked list
Node
O(1)
O(1)
O(n)
O(n log n)
O(1)OrderedList<T>Array
Index
O(n)
O(n)
O(log n)
Sorted
O(1)OrderedKeyValueList<V>Array
Index
O(n)
O(n)
O(log n)
Sorted
O(1)OrderedMap<K, V>RB Tree
Node
O(log n)
O(log n)
O(log n)
Sorted
O(log n)OrderedSet<T>RB Tree
Node
O(log n)
O(log n)
O(log n)
Sorted
O(log n)OrderedMultiMap<K, V>RB Tree
Node
O(log n)
O(log n)
O(log n)
Sorted
O(log n)OrderedMultiSet<T>RB Tree
Node
O(log n)
O(log n)
O(log n)
Sorted
O(log n)UnorderedMap<K, V>Hash table
Node
O(1)
O(1)
O(1)
-
O(1)UnorderedSet<T>Hash table
Node
O(1)
O(1)
O(1)
-
O(1)UnorderedMultiMap<K, V>Hash table
Node
O(1)
O(1)
O(1)
-
O(1)UnorderedMultiSet<T>Hash table
Node
O(1)
O(1)
O(1)
-
O(1)

Ordered 수집은 대상을 정렬해야 한다IComparable<T> 또는IComparer<T>.

Hashtable 컬렉션UnorderedMap<TKey, TValue>을 사용하려면 적정IEquatable<T>/GetHashCode() 또는IEqualityComparer<T>이 필요합니다.

Multi의 모음은 중복 키를 사용할 수 있습니다.

OrderedMap<TKey, TValue>는 적흑목(Red-black trees)을 사용해 OrderedKeyValueList<TKey, TValue>보다 대부분의 경우보다 빠르다.Index 액세스가 절대적으로 필요한 경우를 제외하고는 권장OrderedMap<TKey, TValue>