5

这是我在C#中反复遇到的一个问题，但一直没有找到通用的解决方案。在 C++/STL 中，可以使用迭代器在 O(n) 时间内更新映射中的所有值，而无需使用键来访问每个元素。有没有办法获得与任何 C# 集合（如 SortedList、SortedDictionary）类似的行为？

我可以做类似的事情

foreach (int key in list.Keys)
{
    list[key] *= 3;
}

但这需要 O(n * log(n))，因为使用键搜索每个元素需要 log(n)。

只是给出一个想法，我正在寻找类似的东西：

SortedList<int, double> list = new SortedList<int,double>();

// Add few values fist

// E.g. first try ...
IList<double> values = list.Values;
for (int i = 0; i < values.Count; i++)
{
    values[i] *= 3;
}

// E.g. second try
foreach (KeyValuePair<int, double> kv in list)
{
    kv.Value *= 3;
}

由于 List 已经排序，因此应该可以遍历它同时更新值（而不是键）。从实现的角度来看，这似乎没有问题，但由于某种原因，该功能似乎不可用。

这也不是一个简单的情况，因为可以使用相同的方法从已知位置迭代到该范围内的另一个修改值。

有没有办法在 C# 中使用 .NET 中的任何键控集合而不使用 3rd 方库来执行此操作？

谢谢

吉夫斯

4

3 回答 3

3

最简单的解决方案是将值包装在引用类型中。

class WrappedInt { public int Value; }
Dictionary<TKey, WrappedInt> dictionary = ...;
foreach (var wrappedVal in dictionary.Values)
{
    wrappedVal.Value *= 3;
}
// or 
foreach (var wrappedVal in dictionary)
{
    wrappedVal.Value.Value *= 3;
}

这种方法适用于任何集合（列表或字典）。为数不多的在没有包装的情况下通过设计做到这一点的集合之一是LinkedList.

当然，如果您有一个非常具体的集合（由某些外部组件创建），您总是可以回退到使用反射并直接在底层存储中更改值。

于 2012-10-30T17:06:25.210 回答
1 
SortedList<int, double> list = new SortedList<int,double>
{
    { 1, 3.14 },
    { 2, 1.618 },
};

var newList = new SortedList<int, double>(list.ToDictionary(kv => kv.Key, kv => kv.Value * 3)).Dump();

根据文档， SortedList 构造函数是 O(n) 。
.ToDictionary 在 Dictionary.Add 上循环。Dictionary.Add 是 O(1) 当容量足够时

O(n) * O(1) 仍然是 O(n) 所以你很好:-)

使用这种方法，空间需求当然会增加一倍。

于 2012-10-30T17:30:47.643 回答
0

在 C# 中，访问 Dictionary 元素的时间接近于 O(1) 的恒定时间。

您可以通过调用 Dictionary.Values 并更新它们来获取值列表：

foreach(var value in valuesDict.Values)
{
    // update value;
}

获取此属性 ( Dictionary.Values) 的值也是一个 O(1) 操作。.

于 2012-10-30T17:06:41.663 回答