Class SortedDictionary<K, V>
A sorted Dictionary implementation using balanced binary search tree. IEnumerable will enumerate in sorted order.
This may be better than regular Dictionary implementation which can give o(K) in worst case (but O(1) amortized when collisions K is avoided).
Inheritance
SortedDictionary<K, V>
Assembly: Advanced.Algorithms.dll
Syntax
public class SortedDictionary<K, V> : IEnumerable<KeyValuePair<K, V>> where K : IComparable
Type Parameters
| Name |
Description |
| K |
The key datatype.
|
| V |
The value datatype.
|
Constructors
SortedDictionary()
Declaration
public SortedDictionary()
SortedDictionary(IEnumerable<KeyValuePair<K, V>>)
Initialize the dictionary with given key value pairs sorted by key.
Time complexity: log(n).
Declaration
public SortedDictionary(IEnumerable<KeyValuePair<K, V>> sortedKeyValuePairs)
Parameters
| Type |
Name |
Description |
| IEnumerable<KeyValuePair<K, V>> |
sortedKeyValuePairs |
|
Properties
Count
Declaration
public int Count { get; }
Property Value
Item[K]
Get/set value for given key.
Time complexity: O(log(n)).
Declaration
public V this[K key] { get; set; }
Parameters
| Type |
Name |
Description |
| K |
key |
|
Property Value
Methods
Add(K, V)
Add a new value for given key.
Time complexity: O(log(n)).
Declaration
public void Add(K key, V value)
Parameters
| Type |
Name |
Description |
| K |
key |
|
| V |
value |
|
ContainsKey(K)
Does this dictionary contains the given key.
Time complexity: O(log(n)).
Declaration
public bool ContainsKey(K key)
Parameters
| Type |
Name |
Description |
| K |
key |
The key to check.
|
Returns
| Type |
Description |
| Boolean |
True if this dictionary contains the given key.
|
ElementAt(Int32)
Time complexity: O(log(n))
Declaration
public KeyValuePair<K, V> ElementAt(int index)
Parameters
| Type |
Name |
Description |
| Int32 |
index |
|
Returns
| Type |
Description |
| KeyValuePair<K, V> |
|
GetEnumerator()
Declaration
public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
Returns
| Type |
Description |
| IEnumerator<KeyValuePair<K, V>> |
|
IndexOf(K)
Time complexity: O(log(n))
Declaration
public int IndexOf(K key)
Parameters
| Type |
Name |
Description |
| K |
key |
|
Returns
NextHigher(K)
Return the next higher key-value pair after given key in this dictionary.
Time complexity: O(log(n)).
Declaration
public KeyValuePair<K, V> NextHigher(K key)
Parameters
| Type |
Name |
Description |
| K |
key |
|
Returns
| Type |
Description |
| KeyValuePair<K, V> |
Null if the given key does'nt exist or next key does'nt exist.
|
NextLower(K)
Return the next lower key-value pair before given key in this dictionary.
Time complexity: O(log(n)).
Declaration
public KeyValuePair<K, V> NextLower(K key)
Parameters
| Type |
Name |
Description |
| K |
key |
|
Returns
| Type |
Description |
| KeyValuePair<K, V> |
Null if the given key does'nt exist or previous key does'nt exist.
|
Remove(K)
Remove the given key.
Time complexity: O(log(n)).
Declaration
public bool Remove(K key)
Parameters
| Type |
Name |
Description |
| K |
key |
|
Returns
RemoveAt(Int32)
Remove the element at given index.
Time complexity: O(log(n)).
Declaration
public KeyValuePair<K, V> RemoveAt(int index)
Parameters
| Type |
Name |
Description |
| Int32 |
index |
|
Returns
| Type |
Description |
| KeyValuePair<K, V> |
|