title: Efficiency of very large collections; iteration and sort
body: <p>I have a csv parser that reads in 15+ million rows (with many duplicates), and once parsed into structs, need to be added to a collection.  Each struct has properties Key (int), A(datetime), and B(int) (and others that aren't relevant here).</p>
  
  <p><strong>Requirement A:</strong> The collection needs to enforce uniqueness by a Key.</p>
  
  <p><strong>Requirement B:</strong> In a later step, I need the collection sorted by properties A(timestamp) then B(int).</p>
  
  <p><strong>Constraint:</strong> The structs eventually need to be traversed in order, one by one, with references to neighbors (a LinkedList presents the cleanest solution here); the point of this operation is to partition the set.  Please assume that this is the earliest that partitioning can occur (ie, it cannot be partitioned at the parsing stage).</p>
  
  <p>I've found that the SortedSet works quite well for Requirement A, and it's quite performant as well, even though the O(log n) insertions are much slower than with <code>HashSet&lt;T&gt;</code>'s O(1), though I don't care about sorting on the key.  <code>HashSet&lt;T&gt;</code> gets bogged down when the collection gets huge, which apparently is a known issue, while <code>SortedSet&lt;T&gt;</code> does not suffer this drawback.</p>
  
  <p><strong>The problem:</strong> When I get to the step for Requirement B, sorting the collection (a <code>SortedSet&lt;T&gt;</code> passed to a method as <code>IEnumerable&lt;T&gt;</code>) takes a prohibitive amount of time (20+ minutes of grinding, all in-memory, no page file usage). </p>
  
  <p><strong>The question:</strong> Which collection(s) is(are) best suited to address this problem?  One idea is to use two collections: one to enforce uniqueness (like a <code>HashSet&lt;int&gt;</code> or <code>SortedSet&lt;int&gt;</code> of keys), and a second <code>SortedSet&lt;T&gt;</code> to handle sorting at the parsing stage (ie, as far upstream as possible).  But the application is already memory-intensive, and the performance penalties of needing the pagefile is prohibitive.<br>
  What options does that leave me with for a single collection that enforces uniqueness by one characteristic, but sorts by other unrelated characteristics?  <code>SortedSet&lt;T&gt;</code> uses <code>IComparer&lt;T&gt;</code> (but not both <code>IComparer&lt;T&gt;</code> and <code>IEquitable&lt;T&gt;</code>), so if it relies on CompareTo to enforce uniqueness, then it doesn't seem to fit my requirements.  Is subclassing SortedSet the way to go?</p>
  
  <p><strong>Edit:</strong> The sort code:</p>
  
  <pre><code>SortedSet&lt;Dto&gt; parsedSet = {stuff};
  var sortedLinkedStructs = new LinkedList&lt;Dto&gt;(parsedSet.OrderBy(t =&gt; t.Timestamp).ThenBy(i =&gt; i.SomeInt));
  </code></pre>
  
  <p>The struct:</p>
  
  <pre><code>public readonly struct Dto: IEquatable&lt;Dto&gt;, IComparer&lt;Dto&gt;, IComparable&lt;Dto&gt;
  {
       public readonly datetime Timestamp;
       public readonly int SomeInt;
       public readonly int Key;
  
       ctor(ts, int, key){assigned}
  
       public bool Equals(Dtoother) =&gt; this.Key == other.Key;
       public override int GetHashCode() =&gt; this.Key.GetHashCode();
       public int Compare(Dto x, Dto y) =&gt;  x.Key.CompareTo(y.Key);
       public int CompareTo(Dto other) =&gt; this.Key.CompareTo(other.Key);
  }
  </code></pre>