Table of Contents

SequencedDictionary<TKey, TValue> Class

Definition

Namespace
Bodu.Collections.Generic
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
SequencedDictionary{T,T}.DictionaryEnumerator.cs

Represents a dictionary that preserves the order in which entries are added and provides O(1) access to and removal of the first and last entries, optionally re-ordering entries on access.

public class SequencedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IReadOnlyDictionary<TKey, TValue>, IReadOnlyCollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable where TKey : notnull

Type Parameters

TKey

Specifies the type of keys in the dictionary.

TValue

Specifies the type of values in the dictionary.

Inheritance
SequencedDictionary<TKey, TValue>
Implements
IDictionary<TKey, TValue>
ICollection<KeyValuePair<TKey, TValue>>
IReadOnlyDictionary<TKey, TValue>
IEnumerable<KeyValuePair<TKey, TValue>>
Inherited Members
Extension Methods

Remarks

SequencedDictionary<TKey, TValue> is the .NET analogue of Java's LinkedHashMap: a hash-based dictionary that additionally maintains a doubly linked list across its entries so that enumeration follows a stable, predictable order. It realizes the same sequenced (encounter-order) contract that Java's SequencedMap defines: a well-defined first and last entry with constant-time access to each.

This differs from the BCL's OrderedDictionary<TKey, TValue> (.NET 9+), which is positional - it is index-addressable and supports inserting, overwriting, and removing at an arbitrary index, with O(1) random access by position but O(n) removal of a non-tail entry. SequencedDictionary<TKey, TValue> instead exposes no positional surface; it preserves a traversal order and adds O(1) access to and removal of either end, with O(1) removal of any entry by key. (On Bodu's net8.0 target the BCL OrderedDictionary<TKey, TValue> is not available at all.)

The dictionary supports two ordering modes, selected at construction:

  • Insertion order (the default): entries are enumerated in the order they were first added. Reads never change the order, and re-assigning an existing key's value leaves its position unchanged.
  • Access order: a successful lookup (via TryGetValue(TKey, out TValue) or the indexer getter) and an indexed value update move the affected entry to the end of the iteration order. This makes the most recently used entry the Last entry and the least recently used entry the First entry, which is the foundation of a least-recently-used cache built on top of TryRemoveFirst(out KeyValuePair<TKey, TValue>).

This type does not bound its size or evict entries; for a fixed-capacity, policy-driven cache use EvictingDictionary<TKey, TValue> instead. The capacity constructor argument is only an initial-size hint for the internal hash table.

Keys must be non-null (the type parameter is constrained by notnull). Values may be null when TValue is a reference type. Custom key equality is supported via IEqualityComparer<T>.

SequencedDictionary<TKey, TValue> is not thread-safe. In access-order mode reads mutate the iteration order, so concurrent reads and writes require external synchronization. 

// Insertion-order dictionary: enumeration follows the order keys were added.
var ordered = new SequencedDictionary<string, int>();
ordered.Add("A", 1);
ordered.Add("B", 2);
ordered.Add("C", 3);

foreach (var kvp in ordered)
    Console.WriteLine($"{kvp.Key} = {kvp.Value}"); // A, B, C

// Access-order dictionary: a lookup moves the entry to the end.
var lru = new SequencedDictionary<string, int>(accessOrder: true);
lru.Add("A", 1);
lru.Add("B", 2);
_ = lru["A"];           // "A" is now most-recently-used.
var oldest = lru.First; // { "B", 2 } - the least-recently-used entry.

Constructors

SequencedDictionary()

Initializes a new instance of the SequencedDictionary<TKey, TValue> class that is empty, uses insertion ordering, and uses the default key comparer.

public SequencedDictionary()

SequencedDictionary(bool)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class that is empty, uses the specified ordering mode, and uses the default key comparer.

public SequencedDictionary(bool accessOrder)

Parameters

accessOrder bool

true to move an entry to the end of the iteration order whenever it is read or its value is updated through the indexer; false to preserve insertion order.

SequencedDictionary(IEnumerable<KeyValuePair<TKey, TValue>>)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class with elements copied from the specified sequence, using insertion ordering and the default key comparer.

public SequencedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection)

Parameters

collection IEnumerable<KeyValuePair<TKey, TValue>>

The sequence of key/value pairs to copy. Must not be null.

Exceptions

ArgumentNullException

collection is null.

ArgumentException

collection contains one or more duplicate keys.

SequencedDictionary(IEnumerable<KeyValuePair<TKey, TValue>>, bool, IEqualityComparer<TKey>?)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class with elements copied from the specified sequence, using the specified ordering mode and key comparer.

public SequencedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, bool accessOrder, IEqualityComparer<TKey>? comparer)

Parameters

collection IEnumerable<KeyValuePair<TKey, TValue>>

The sequence of key/value pairs to copy. Must not be null.

accessOrder bool

true to move an entry to the end of the iteration order whenever it is read or its value is updated through the indexer; false to preserve insertion order.

comparer IEqualityComparer<TKey>

The equality comparer to use for keys, or null to use the default comparer.

Exceptions

ArgumentNullException

collection is null.

ArgumentException

collection contains one or more duplicate keys.

SequencedDictionary(IEnumerable<KeyValuePair<TKey, TValue>>, IEqualityComparer<TKey>?)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class with elements copied from the specified sequence, using insertion ordering and the specified key comparer.

public SequencedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey>? comparer)

Parameters

collection IEnumerable<KeyValuePair<TKey, TValue>>

The sequence of key/value pairs to copy. Must not be null.

comparer IEqualityComparer<TKey>

The equality comparer to use for keys, or null to use the default comparer.

Exceptions

ArgumentNullException

collection is null.

ArgumentException

collection contains one or more duplicate keys.

SequencedDictionary(IEqualityComparer<TKey>?)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class that is empty, uses insertion ordering, and uses the specified key comparer.

public SequencedDictionary(IEqualityComparer<TKey>? comparer)

Parameters

comparer IEqualityComparer<TKey>

The equality comparer to use for keys, or null to use the default comparer.

SequencedDictionary(int)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class that is empty, uses insertion ordering, and has the specified initial capacity.

public SequencedDictionary(int capacity)

Parameters

capacity int

The initial number of entries the internal hash table can hold without resizing.

Exceptions

ArgumentOutOfRangeException

capacity is less than zero.

SequencedDictionary(int, bool)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class that is empty, uses the specified ordering mode, and has the specified initial capacity.

public SequencedDictionary(int capacity, bool accessOrder)

Parameters

capacity int

The initial number of entries the internal hash table can hold without resizing.

accessOrder bool

true to move an entry to the end of the iteration order whenever it is read or its value is updated through the indexer; false to preserve insertion order.

Exceptions

ArgumentOutOfRangeException

capacity is less than zero.

SequencedDictionary(int, bool, IEqualityComparer<TKey>?)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class that is empty and has the specified initial capacity, ordering mode, and key comparer.

public SequencedDictionary(int capacity, bool accessOrder, IEqualityComparer<TKey>? comparer)

Parameters

capacity int

The initial number of entries the internal hash table can hold without resizing.

accessOrder bool

true to move an entry to the end of the iteration order whenever it is read or its value is updated through the indexer; false to preserve insertion order.

comparer IEqualityComparer<TKey>

The equality comparer to use for keys, or null to use the default comparer.

Exceptions

ArgumentOutOfRangeException

capacity is less than zero.

SequencedDictionary(int, IEqualityComparer<TKey>?)

Initializes a new instance of the SequencedDictionary<TKey, TValue> class that is empty, uses insertion ordering, and has the specified initial capacity and key comparer.

public SequencedDictionary(int capacity, IEqualityComparer<TKey>? comparer)

Parameters

capacity int

The initial number of entries the internal hash table can hold without resizing.

comparer IEqualityComparer<TKey>

The equality comparer to use for keys, or null to use the default comparer.

Exceptions

ArgumentOutOfRangeException

capacity is less than zero.

Properties

AccessOrder

Gets a value indicating whether a successful lookup or indexed value update moves the affected entry to the end of the iteration order.

public bool AccessOrder { get; }

Property Value

bool

true if the dictionary uses access ordering; false if it preserves insertion order.

Comparer

Gets the IEqualityComparer<T> used to determine key equality.

public IEqualityComparer<TKey> Comparer { get; }

Property Value

IEqualityComparer<TKey>

The comparer used for key identity and hash-table lookup.

Count

Gets the number of elements contained in the ICollection<T>.

public int Count { get; }

Property Value

int

The number of elements contained in the ICollection<T>.

First

Gets the first key/value pair in iteration order.

public KeyValuePair<TKey, TValue> First { get; }

Property Value

KeyValuePair<TKey, TValue>

The entry at the head of the iteration order.

Remarks

This is an O(1) operation and never changes the iteration order, even in access-order mode. In an access-order dictionary the first entry is the least recently used.

Exceptions

InvalidOperationException

The dictionary is empty.

IsReadOnly

Gets a value indicating whether the ICollection<T> is read-only.

public bool IsReadOnly { get; }

Property Value

bool

true if the ICollection<T> is read-only; otherwise, false.

this[TKey]

Gets or sets the element with the specified key.

public TValue this[TKey key] { get; set; }

Parameters

key TKey

The key of the element to get or set.

Property Value

TValue

The element with the specified key.

Remarks

In access-order mode, both reading and assigning through the indexer move the affected entry to the end of the iteration order. Assigning a new key appends it to the end; assigning an existing key updates its value in place.

Exceptions

ArgumentNullException

key is null.

KeyNotFoundException

The property is retrieved and key is not found.

NotSupportedException

The property is set and the IDictionary<TKey, TValue> is read-only.

Keys

Gets an ICollection<T> containing the keys of the IDictionary<TKey, TValue>.

public ICollection<TKey> Keys { get; }

Property Value

ICollection<TKey>

An ICollection<T> containing the keys of the object that implements IDictionary<TKey, TValue>.

Remarks

Returns a live, order-preserving view of the dictionary's keys. The collection is cached per instance, so repeated reads of Keys do not allocate; enumeration follows the dictionary's iteration order.

Last

Gets the last key/value pair in iteration order.

public KeyValuePair<TKey, TValue> Last { get; }

Property Value

KeyValuePair<TKey, TValue>

The entry at the tail of the iteration order.

Remarks

This is an O(1) operation and never changes the iteration order, even in access-order mode. In an access-order dictionary the last entry is the most recently used.

Exceptions

InvalidOperationException

The dictionary is empty.

Values

Gets an ICollection<T> containing the values in the IDictionary<TKey, TValue>.

public ICollection<TValue> Values { get; }

Property Value

ICollection<TValue>

An ICollection<T> containing the values in the object that implements IDictionary<TKey, TValue>.

Remarks

Returns a live, order-preserving view of the dictionary's values. The collection is cached per instance, so repeated reads of Values do not allocate; enumeration follows the dictionary's iteration order.

Methods

Add(KeyValuePair<TKey, TValue>)

Adds the specified key/value pair to the dictionary, appending it to the end of the iteration order.

public void Add(KeyValuePair<TKey, TValue> item)

Parameters

item KeyValuePair<TKey, TValue>

The key/value pair to add to the dictionary.

Exceptions

ArgumentNullException

item.Key is null.

ArgumentException

An element with the same key already exists in the dictionary.

Add(TKey, TValue)

Adds the specified key and value to the dictionary, appending the new entry to the end of the iteration order.

public void Add(TKey key, TValue value)

Parameters

key TKey

The key of the element to add.

value TValue

The value to associate with key.

Remarks

This method follows the strict Add(TKey, TValue) contract and throws on a duplicate key. To insert or overwrite without throwing, assign through the indexer.

Exceptions

ArgumentNullException

key is null.

ArgumentException

An element with the same key already exists in the dictionary.

Clear()

Removes all entries from the dictionary.

public void Clear()

Contains(KeyValuePair<TKey, TValue>)

Determines whether the ICollection<T> contains a specific value.

public bool Contains(KeyValuePair<TKey, TValue> item)

Parameters

item KeyValuePair<TKey, TValue>

The object to locate in the ICollection<T>.

Returns

bool

true if item is found in the ICollection<T>; otherwise, false.

ContainsKey(TKey)

Determines whether the IDictionary<TKey, TValue> contains an element with the specified key.

public bool ContainsKey(TKey key)

Parameters

key TKey

The key to locate in the IDictionary<TKey, TValue>.

Returns

bool

true if the IDictionary<TKey, TValue> contains an element with the key; otherwise, false.

Remarks

This method never changes the iteration order, even in access-order mode.

Exceptions

ArgumentNullException

key is null.

CopyTo(KeyValuePair<TKey, TValue>[], int)

Copies the elements of the ICollection<T> to an Array, starting at a particular Array index.

public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)

Parameters

array KeyValuePair<TKey, TValue>[]

The one-dimensional Array that is the destination of the elements copied from ICollection<T>. The Array must have zero-based indexing.

arrayIndex int

The zero-based index in array at which copying begins.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

arrayIndex is less than 0.

ArgumentException

The number of elements in the source ICollection<T> is greater than the available space from arrayIndex to the end of the destination array.

GetEnumerator()

Returns an enumerator that iterates through the dictionary in iteration order.

public SequencedDictionary<TKey, TValue>.Enumerator GetEnumerator()

Returns

SequencedDictionary<TKey, TValue>.Enumerator

An SequencedDictionary<TKey, TValue>.Enumerator over the dictionary's entries.

Remarks

Entries are produced in insertion order, or access order when access ordering is enabled. Any mutation of the dictionary - including reads that reposition entries in access-order mode - invalidates the enumerator.

Remove(KeyValuePair<TKey, TValue>)

Removes the first occurrence of a specific object from the ICollection<T>.

public bool Remove(KeyValuePair<TKey, TValue> item)

Parameters

item KeyValuePair<TKey, TValue>

The object to remove from the ICollection<T>.

Returns

bool

true if item was successfully removed from the ICollection<T>; otherwise, false. This method also returns false if item is not found in the original ICollection<T>.

Exceptions

NotSupportedException

The ICollection<T> is read-only.

Remove(TKey)

Removes the element with the specified key from the IDictionary<TKey, TValue>.

public bool Remove(TKey key)

Parameters

key TKey

The key of the element to remove.

Returns

bool

true if the element is successfully removed; otherwise, false. This method also returns false if key was not found in the original IDictionary<TKey, TValue>.

Exceptions

ArgumentNullException

key is null.

NotSupportedException

The IDictionary<TKey, TValue> is read-only.

TryGetFirst(out KeyValuePair<TKey, TValue>)

Attempts to retrieve the first key/value pair in iteration order without removing it.

public bool TryGetFirst(out KeyValuePair<TKey, TValue> entry)

Parameters

entry KeyValuePair<TKey, TValue>

When this method returns, contains the entry at the head of the iteration order if the dictionary is non-empty; otherwise, the default value.

Returns

bool

true if the dictionary contains at least one entry; otherwise, false.

Remarks

This is an O(1) operation and never changes the iteration order, even in access-order mode.

TryGetLast(out KeyValuePair<TKey, TValue>)

Attempts to retrieve the last key/value pair in iteration order without removing it.

public bool TryGetLast(out KeyValuePair<TKey, TValue> entry)

Parameters

entry KeyValuePair<TKey, TValue>

When this method returns, contains the entry at the tail of the iteration order if the dictionary is non-empty; otherwise, the default value.

Returns

bool

true if the dictionary contains at least one entry; otherwise, false.

Remarks

This is an O(1) operation and never changes the iteration order, even in access-order mode.

TryGetValue(TKey, out TValue)

Attempts to retrieve the value associated with the specified key.

public bool TryGetValue(TKey key, out TValue value)

Parameters

key TKey

The key of the value to retrieve.

value TValue

When this method returns, contains the value associated with the specified key, if the key is found; otherwise, the default value for the type of the value parameter.

Returns

bool

true if the dictionary contains an element with the specified key; otherwise, false.

Remarks

In access-order mode a successful lookup counts as an access and moves the entry to the end of the iteration order; in insertion-order mode the lookup does not change the order.

TryRemoveFirst(out KeyValuePair<TKey, TValue>)

Attempts to remove and return the first key/value pair in iteration order.

public bool TryRemoveFirst(out KeyValuePair<TKey, TValue> entry)

Parameters

entry KeyValuePair<TKey, TValue>

When this method returns, contains the removed entry if the dictionary was non-empty; otherwise, the default value.

Returns

bool

true if an entry was removed; otherwise, false.

Remarks

This is an O(1) operation. In an access-order dictionary this removes the least recently used entry.

TryRemoveLast(out KeyValuePair<TKey, TValue>)

Attempts to remove and return the last key/value pair in iteration order.

public bool TryRemoveLast(out KeyValuePair<TKey, TValue> entry)

Parameters

entry KeyValuePair<TKey, TValue>

When this method returns, contains the removed entry if the dictionary was non-empty; otherwise, the default value.

Returns

bool

true if an entry was removed; otherwise, false.

Remarks

This is an O(1) operation. In an access-order dictionary this removes the most recently used entry.

Explicit Interface Implementations

IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()

Returns

IEnumerator<KeyValuePair<TKey, TValue>>

An enumerator that can be used to iterate through the collection.

IReadOnlyDictionary<TKey, TValue>.Keys

Gets an enumerable collection that contains the keys in the read-only dictionary.

IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys { get; }

Returns

IEnumerable<TKey>

An enumerable collection that contains the keys in the read-only dictionary.

IReadOnlyDictionary<TKey, TValue>.Values

Gets an enumerable collection that contains the values in the read-only dictionary.

IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values { get; }

Returns

IEnumerable<TValue>

An enumerable collection that contains the values in the read-only dictionary.

ICollection.CopyTo(Array, int)

Copies the elements of the ICollection to an Array, starting at a particular Array index.

void ICollection.CopyTo(Array array, int index)

Parameters

array Array

The one-dimensional Array that is the destination of the elements copied from ICollection. The Array must have zero-based indexing.

index int

The zero-based index in array at which copying begins.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

index is less than zero.

ArgumentException

array is multidimensional.

-or-

The number of elements in the source ICollection is greater than the available space from index to the end of the destination array.

-or-

The type of the source ICollection cannot be cast automatically to the type of the destination array.

ICollection.IsSynchronized

Gets a value indicating whether access to the ICollection is synchronized (thread safe).

bool ICollection.IsSynchronized { get; }

Returns

bool

true if access to the ICollection is synchronized (thread safe); otherwise, false.

ICollection.SyncRoot

Gets an object that can be used to synchronize access to the ICollection.

object ICollection.SyncRoot { get; }

Returns

object

An object that can be used to synchronize access to the ICollection.

IDictionary.Add(object, object)

Adds an element with the provided key and value to the IDictionary object.

void IDictionary.Add(object key, object value)

Parameters

key object

The object to use as the key of the element to add.

value object

The object to use as the value of the element to add.

Exceptions

ArgumentNullException

key is null.

ArgumentException

An element with the same key already exists in the IDictionary object.

NotSupportedException

The IDictionary is read-only.

-or-

The IDictionary has a fixed size.

IDictionary.Contains(object)

Determines whether the IDictionary object contains an element with the specified key.

bool IDictionary.Contains(object key)

Parameters

key object

The key to locate in the IDictionary object.

Returns

bool

true if the IDictionary contains an element with the key; otherwise, false.

Exceptions

ArgumentNullException

key is null.

IDictionary.GetEnumerator()

Returns an IDictionaryEnumerator object for the IDictionary object.

IDictionaryEnumerator IDictionary.GetEnumerator()

Returns

IDictionaryEnumerator

An IDictionaryEnumerator object for the IDictionary object.

IDictionary.IsFixedSize

Gets a value indicating whether the IDictionary object has a fixed size.

bool IDictionary.IsFixedSize { get; }

Returns

bool

true if the IDictionary object has a fixed size; otherwise, false.

IDictionary.IsReadOnly

Gets a value indicating whether the IDictionary object is read-only.

bool IDictionary.IsReadOnly { get; }

Returns

bool

true if the IDictionary object is read-only; otherwise, false.

IDictionary.Item[object]

Gets or sets the element with the specified key.

object? IDictionary.Item[object key] { get; set; }

Parameters

key object

The key of the element to get or set.

Returns

object

The element with the specified key, or null if the key does not exist.

Remarks

Following the Dictionary<TKey, TValue> contract for this[object], the getter throws ArgumentNullException for a null key and returns null for a non-null key of an incompatible type.

Exceptions

ArgumentNullException

key is null.

NotSupportedException

The property is set and the IDictionary object is read-only.

-or-

The property is set, key does not exist in the collection, and the IDictionary has a fixed size.

IDictionary.Keys

Gets an ICollection object containing the keys of the IDictionary object.

ICollection IDictionary.Keys { get; }

Returns

ICollection

An ICollection object containing the keys of the IDictionary object.

IDictionary.Remove(object)

Removes the element with the specified key from the IDictionary object.

void IDictionary.Remove(object key)

Parameters

key object

The key of the element to remove.

Exceptions

ArgumentNullException

key is null.

NotSupportedException

The IDictionary object is read-only.

-or-

The IDictionary has a fixed size.

IDictionary.Values

Gets an ICollection object containing the values in the IDictionary object.

ICollection IDictionary.Values { get; }

Returns

ICollection

An ICollection object containing the values in the IDictionary object.

IDictionary.get_Item(object) 

object IDictionary.get_Item(object key)

Parameters

key object

Returns

object

IDictionary.set_Item(object, object) 

void IDictionary.set_Item(object key, object value)

Parameters

key object
value object

IEnumerable.GetEnumerator()

Returns an enumerator that iterates through a collection.

IEnumerator IEnumerable.GetEnumerator()

Returns

IEnumerator

An IEnumerator object that can be used to iterate through the collection.

Applies to

ProductVersions
.NET8, 10