System.Collections.Generic.SortedList的SetByIndex等价方法是什么？

Question

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

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

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

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

19%（独占）总程序时间花费在System.String.CompareTo(string)中，其中几乎全部来自修改值的方法。

示例代码：

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
            }
    }
}

- Chris Smith

Answer 1

此功能请求于2021年9月10日作为https://github.com/dotnet/runtime/issues/58962提出，并在2021年11月15日由https://github.com/dotnet/runtime/pull/60520实现。它不包含在.NET 6.0或更早版本中。

- Chris Culter

Answer 2

使用 SortedList<TKey, TValue> 上的 Values 属性，以获取排序列表中所有值的 IList<TValue>。然后，您可以通过索引获取该值，这是一个 O(1) 操作，例如：mySortedList.Values[i]。

https://msdn.microsoft.com/en-us/library/ms132380(v=vs.110).aspx

如果您的值类型是结构体，您可以使用ref将其传递给方法，并使用新的属性值更新该属性。不过，不建议使用可变结构体，如此处所述：pass c# struct by reference?。

- ZippyZippedUp

---

是的，我可以按照您建议并在示例代码中说明的方式按索引获取值。问题是如何通过索引设置一个值。尝试通过IList.Values进行设置会引发“此操作不受支持，因为它需要修改原始SortedList嵌套类型”的错误。 - Chris Smith

我已经编辑了答案，并提供了一个可能的设置值的方法。这可能不是最理想的解决方案，但希望能够引发一些思考。 - ZippyZippedUp

通过 SortedList 的属性访问器获取结构体的值会复制该值，因此通过 ref 传递不会修改 SortedList 上的值，它只会修改检索到的副本。 - Orestis P.