SetByIndex 等效于 System.Collections.Generic.SortedList

Question

System.Collections.SortedList 有一个 SetByIndex 方法，由于数据结构的性质，它很便宜，O(1)。此类的通用版本没有 SetByIndex 方法。我正在寻找 System.Collections.Generic 中 SortedList 实现的等效操作。

这两个类都使用排序数组实现字典。由于底层结构是一个数组，因此可以通过索引有效地访问条目。非通用版本还提供了一个 GetByIndex 方法，该方法通过索引（而不是键）检索值。通用 SortedList 还支持通过 .Values 属性按索引检索。当我尝试通过 .Values 属性修改元素时，我收到一个异常，提示“SortedList 嵌套类型不支持此操作，因为它们需要修改原始 SortedList。”

我不是面向对象设计的专家，但为什么不让我通过 SortedList 返回的“嵌套类型”修改值呢？

对于这个项目，我使用 .NET 4.0。我需要 SortedList 以便我可以按排序顺序遍历项目。根据分析，程序中最昂贵的调用树涉及按索引（因此按键排序）遍历一堆小型 SortedLists 中的项目并修改某些值。目前要执行该值修改步骤，我必须使用键进行分配，这涉及 log(n) 字符串比较操作来定位正确的插槽，而不是简单地按索引（即 SetByIndex）分配值，这将是零比较。我没有更改键，因此不会影响数组中值的位置。

System.String.CompareTo(string) 花费的总程序时间的 19%（不包括），几乎所有时间都来自修改值的方法。

示例代码来说明：

class Container
{
    readonly System.Collections.Generic.SortedList<string, MapEntryValueType> map;
    void Merge(IncomingData data)
    {
        for(int i=0; i < map.Count; i++)
            if(data.ExamineKeyForMatch(map.Keys[i])) //O(1)
            {
                MapEntryValueType entry = map.Values[i]; //O(1)
                entry.something = data.something;
                //map.Values[i] = entry; //O(1) no can do, error "This operation is not supported..."
                //map.SetByIndex(i, entry); //O(1) no can do, no such method
                map[map.Keys[i]] = entry; //O(log n) yucky and slow but works
            }
    }
}

Answer 1

此功能请求于 2021 年 9 月 10 日以https://github.com/dotnet/runtime/issues/58962开放，并于 2021 年 11 月由https://github.com/dotnet/runtime/pull/60520实施15. 它不存在于 .NET 6.0 或更早版本中。