C＃数据结构问题（要使用哪个集合？）

我需要实现一个Widget对象的大集合，每个对象都包含一个唯一的文件路径字符串（“FilePath”）。我需要能够做到以下几点：C＃数据结构问题（要使用哪个集合？）

检索Widget对象迅速给定的文件路径
改变一个构件而无需创建一个新的对象（其他多个对象可能包含一个单一的引用文件路径窗口小部件，并跟踪下来会影响性能）
发出的Widget参考，确定它的文件路径

我首先想到使用通用的排序列表使用文件路径作为重点，但复制路径的许多数以千计的物体可能会迅速吃掉你p内存。我考虑从对象中移除路径并仅将其存储在键列表中，但这会使上面的要求3很难完成。

我现在所倾向的是滚动我自己的类，它从列表<>中产生，它按排序顺序添加Widget对象，并通过二分搜索来检索它们。要求2可以简单地通过从列表中删除一个对象，更改它的文件路径并将其添加回列表来完成。

但是我对C＃比较陌生，我想在这里检查一下伟大的思想，看看我是否错过了另一个明显的解决方案。

谢谢！

来源

2009-04-11 Bill Brooks

“复制”的字符串将不会使用两倍的存储器：在词典中每个条目由于字符串是在c＃不变的对象，就会只存储另一个参考（即指针，4个或8 byts）：

Dictionary<string, Widget> dict = new Dictionary<string, Widget>(); 
Widget myWidget = GetSomeWidget(); 
dict.Add(myWidget.Name, myWidget);

您将始终使用窗口小部件属性中的字符串对象，所以继续使用字典并将路径作为属性存储在窗口小部件中。如果您不需要按排序顺序枚举窗口小部件，不要使用SortedList，它将比字典（O（n log n）插入/删除/检索与O（n）平均时间）

更改窗口小部件的路径将需要您从字典中删除它并将其添加到已更改的路径中，但这是一个平均常量时间操作，所以它应该非常快。

并且只是提及它：即使您需要花费一MB额外内存才能获得更高性能或使用更适合（且经过良好测试）的数据结构，我不认为这会是考虑到其他应用程序正在使用（浪费？）这些天的内存量的大问题...

来源

2009-04-11 17:19:18 MartinStettner

这个答案和其他人回答了这个问题的部分内容，但这是解决主要问题的答案，也是最简洁的答案。谢谢！ – 2009-04-11 20:26:38

“成千上万的物体”？你确定这个结构属于记忆么？听起来像是一种针对某种持久性存储的工作。

来源

2009-04-11 16:07:41

你不能使用2个字典吗？

Dictionary<string, Widget> WidgetsByPath; 
Dictionary<Widget, string> PathsByWidget;

处理，将会有更多一点的开销（如您需要更新两个字典时插入，修改或删除元素），但你可能只会插入一次查找很多次，所以应该进行足够多。

你甚至可以构造一个简单的类，它周围：

public class Widgets 
{ 
    public Widget Add(string Path, Widget wdg) 
    { 
    // Chek it doesn't already exits and all... 
    WidgetsByPath.Add(Path, wdg); 
    PathsByWidget.Add(wdg, Path); 
    } 

    public void Delete(string Path) 
    { 
    Widget w = WidgetsByPath[Path]; 
    PathsByWidget.Delete(w); 
    WidgetsByPath.Delete(Path); 
    } 
}

来源

2009-04-11 16:09:23

+1我只是打算发表这个。 – 2009-04-11 16:13:03

但是，如果每个Widget包含一个Path成员，那么我不需要第二个字典。我主要关心的是重复路径。如果我们假设每条路径平均为30个字节，并且我们正在处理（在极端情况下）30k个对象，那么大概是一个兆字节的重复。 – 2009-04-11 16:31:24

如果用户恰好在使用大量嵌套的文件，那可能会很快增长！ – 2009-04-11 16:37:31

如果你结束了一个自定义的数据结构中去，我会建议使用围堵，而非推导。将必要的接口定义为新类的一部分会更好，并将存储细节保留在内部。如果你是从List中派生出来的，那么强化这个类的正确使用将会困难得多，并且如果你后来改变了主意，那么改变事情就会变得更加困难。

来源

2009-04-11 16:15:58 Charlie

优秀的点。谢谢！ – 2009-04-11 16:25:13

我认为你只需要一个字典<Widget>和一个合适的Widget类，其中包含对其他Widgets的引用。这可能有助于将其定制为自定义词典，以便您可以简单地添加一个Widget并让它从Widget的FilePath属性派生出键。

public class WidgetDictionary : Dictionary<string,Widget> 
{ 
    ... provide suitable constructors ... 

    public void Add(Widget widget) 
    { 
     if (widget != null && !this.ContainsKey(widget.FilePath)) 
     { 
      this.Add(widget.FilePath, widget); 
     } 
    } 
} 

public class Widget 
{ 
     public string FilePath { get; set; } 

     private List<Widget> widgets = new List<Widget>(); 
     public IEnumerable<Widget> Widgets 
     { 
      get { return widgets; } 
     } 

     ...code to add/remove widgets from list... 
}

然后要做（1）你只需通过文件路径查看小部件存储库中的小部件。

var repository = new WidgetDictionary(); 
string filePath = ... 
var widget = repository[filePath];

要做（2）可以在更改文件路径后删除小部件并重新添加到存储库。对其他小部件所持有的小部件的引用仍然有效。

var widget = repository[filePath]; 
repository.Remove(filePath); 
widget.FilePath = newFilePath; 
repository.Add(widget); 

EDIT: this could probably be implemented as a method on the 
dictionary as well. 

    public void UpdatePath(Widget widget, string newPath) 
    { 
     if (string.IsNullOrEmpty(newPath)) 
      throw new ArgumentNullException("newPath"); 

     var widget = this.ContainsKey(widget.FilePath) 
          ? this[widget.FilePath] 
          : null; 

     if (widget != null) 
     {   
      this.Remove(widget.FilePath); 
     } 
     widget.FilePath = newPath; 
     this.Add(widget); 
    }

要做（3）只需引用属性。

var filePath = widget.FilePath;

如果你想自动拥有，当它被删除的其他部件删除其引用到窗口小部件（配置），你可能会想有Widget类实现IDisposable，不得不添加事件处理程序的能力一个dispose事件，以便感兴趣的小部件可以注册一个方法，该方法将从它们的相关小部件集合中移除正在部署的小部件。有关如何设置和使用事件处理程序，请参见this MSDN section。

来源

2009-04-11 16:37:15 tvanfosson

您是否考虑过使用Path类？内部路径是一个字符串，并且存在用于获得各种路径部分的精妙方法，即GetFullPath,GetFileName等等。

来源

2012-01-07 02:24:45 radarbob

C＃数据结构问题（要使用哪个集合？）

回答

相关问题