CODEWITHSUNDEEP
c#
McPolu
McPolu

Reputation: 43

Are the .Values and .Keys in a ImmutableSortedDictionary guaranteed to be sorted?

In C#, are the .Values and .Keys in a ImmutableSortedDictionary guaranteed to be sorted, please?

The following code:

var dict = new Dictionary<long, string>
        {
            {3, "Three"},
            {1, "One"},
            {2, "Two"}
        }.ToImmutableSortedDictionary();

        foreach (var p in dict)
        {
            System.Console.WriteLine($"{p.Key} - {p.Value}");
        }

        System.Console.WriteLine();

        foreach (var k in dict.Keys)
        {
            System.Console.WriteLine(k);
        }

        System.Console.WriteLine();

        foreach (var v in dict.Values)
        {
            System.Console.WriteLine(v);
        }

Behaves as I was expecting, it prints all in order. Are there any guarantees that it will always do so? I checked online documentation and it does not say anything one way or the other.

Thank you.

EDIT: Neither https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablesorteddictionary-2.keys?view=netcore-3.1 nor https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablesorteddictionary-2.values?view=netcore-3.1 say one way or the other, from what I understand, the documentation only guarantees that a .GetEnumerator() on the dictionary will be sorted. So it seems that the first loop in the code above will always be sorted, but I am not sure about the second and third.

Upvotes: 0

Views: 1458

Answers (2)

Han Zhao
Han Zhao

Reputation: 2062

Well, when document is not clear, source code talks (as @404 pointed out).

Conclusion

I agree with @mjwills. Since current documents (.NET Core 3.1) do not specify what the order of returned objects is, we cannot safely assume anything.

Keys:

Gets the keys in the immutable sorted dictionary.

Values:

Gets the values in the immutable sorted dictionary.

Warning

Method behaviors below are based on current implementation (.NET Core 3.1) of ImmutableSortedDictionary. Those behaviors are subject to change, please see conclusion aforementioned.

  • Keys will return sorted results
  • Values will not return sorted results

That is easy to verify by running OP's code. The result for Values is not sorted.

One
Two
Three

Reason

Both Keys and Values are the result of enumeration of Node which implements IEnumerable<KeyValuePair<TKey, TValue>>.

/// <summary>
/// Gets the keys.
/// </summary>
internal IEnumerable<TKey> Keys
{
    get { return Linq.Enumerable.Select(this, p => p.Key); }
}

/// <summary>
/// Gets the values.
/// </summary>
internal IEnumerable<TValue> Values
{
    get { return Linq.Enumerable.Select(this, p => p.Value); }
}

Node is an implementation of AVL tree, which adds/removes Node always based on key (not value) comparison IComparer<TKey> keyComparer. That is why Keys are always sorted, while Values are not sorted by itself.

/// <summary>
/// Adds the specified key. Callers are expected to have validated arguments.
/// </summary>
/// <param name="key">The key.</param>
/// <param name="value">The value.</param>
/// <param name="keyComparer">The key comparer.</param>
/// <param name="valueComparer">The value comparer.</param>
/// <param name="overwriteExistingValue">if <c>true</c>, an existing key=value pair will be overwritten with the new one.</param>
/// <param name="replacedExistingValue">Receives a value indicating whether an existing value was replaced.</param>
/// <param name="mutated">Receives a value indicating whether this node tree has mutated because of this operation.</param>
/// <returns>The new AVL tree.</returns>
private Node SetOrAdd(TKey key, TValue value, IComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer, bool overwriteExistingValue, out bool replacedExistingValue, out bool mutated)

/// <summary>
/// Removes the specified key. Callers are expected to validate arguments.
/// </summary>
/// <param name="key">The key.</param>
/// <param name="keyComparer">The key comparer.</param>
/// <param name="mutated">Receives a value indicating whether this node tree has mutated because of this operation.</param>
/// <returns>The new AVL tree.</returns>
private Node RemoveRecursive(TKey key, IComparer<TKey> keyComparer, out bool mutated)

Upvotes: 2

NotFound
NotFound

Reputation: 6157

Seemingly it just uses a linq Select statement to get an Enumerator for the Keys and Values as found in the implementation source. So that would garantuee all 3 statements to be sorted as one also would expect from its class name.

Upvotes: 0

Related Questions