Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>I implemented generic <code>OrderedDictionary&lt;TKey, TValue&gt;</code> by wraping around <code>SortedList&lt;TKey, TValue&gt;</code> and adding private <code>Dictionary&lt;TKey, int&gt;</code> <code>_order</code>. Then I created internal implementation of <code>Comparer&lt;TKey&gt;</code> passing reference to the _order dictionary. Then I use this comparer for internal SortedList. This class keeps order of elements passed to constructor and order of additions.</p> <p>This implementation has almost the same BigO characteristics as <code>SortedList&lt;TKey, TValue&gt;</code> since Adding and Removing to _order is O(1). Each element will take (according to the book 'C# 4 in a Nutshell', p. 292, table 7-1) additional memory space of 22 (overhead) + 4 (int order) + TKey size (let assume 8) = 34. Together with <code>SortedList&lt;TKey, TValue&gt;</code> overhead of 2 bytes the total overhead is 36 bytes, while the same book says that non-generic <code>OrderedDictionary</code> has overhead of 59 bytes.</p> <p>If I pass <code>sorted=true</code> to constructor, then _order is not used at all, the <code>OrderedDictionary&lt;TKey, TValue&gt;</code> is exactly <code>SortedList&lt;TKey, TValue&gt;</code> with minor overhead for wrapping, if at all meaningful.</p> <p>I am going to store not-so-many large reference objects in the <code>OrderedDictionary&lt;TKey, TValue&gt;</code>, so for me this c.36 bytes overhead is tolerable.</p> <p>The main code is below. The complete updated code is on this <a href="https://gist.github.com/buybackoff/5060586#file-ordereddictionary-tkey-tvalue" rel="nofollow">gist</a>.</p> <pre><code>public class OrderedList&lt;TKey, TValue&gt; : IDictionary&lt;TKey, TValue&gt;, IDictionary { private readonly Dictionary&lt;TKey, int&gt; _order; private readonly SortedList&lt;TKey, TValue&gt; _internalList; private readonly bool _sorted; private readonly OrderComparer _comparer; public OrderedList(IDictionary&lt;TKey, TValue&gt; dictionary, bool sorted = false) { _sorted = sorted; if (dictionary == null) dictionary = new Dictionary&lt;TKey, TValue&gt;(); if (_sorted) { _internalList = new SortedList&lt;TKey, TValue&gt;(dictionary); } else { _order = new Dictionary&lt;TKey, int&gt;(); _comparer = new OrderComparer(ref _order); _internalList = new SortedList&lt;TKey, TValue&gt;(_comparer); // keep prder of the IDictionary foreach (var kvp in dictionary) { Add(kvp); } } } public OrderedList(bool sorted = false) : this(null, sorted) { } private class OrderComparer : Comparer&lt;TKey&gt; { public Dictionary&lt;TKey, int&gt; Order { get; set; } public OrderComparer(ref Dictionary&lt;TKey, int&gt; order) { Order = order; } public override int Compare(TKey x, TKey y) { var xo = Order[x]; var yo = Order[y]; return xo.CompareTo(yo); } } private void ReOrder() { var i = 0; _order = _order.OrderBy(kvp =&gt; kvp.Value).ToDictionary(kvp =&gt; kvp.Key, kvp =&gt; i++); _comparer.Order = _order; _lastOrder = _order.Values.Max() + 1; } public void Add(TKey key, TValue value) { if (!_sorted) { _order.Add(key, _lastOrder); _lastOrder++; //very rare event if (_lastOrder == int.MaxValue) ReOrder(); } _internalList.Add(key, value); } public bool Remove(TKey key) { var result = _internalList.Remove(key); if (!_sorted) _order.Remove(key); return result; } // Other IDictionary&lt;&gt; + IDictionary members implementation wrapping around _internalList // ... } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload