Dictionary<比;总是按值排序,从键查找索引

本文关键字:排序 索引 查找 Dictionary | 更新日期: 2023-09-27 18:05:54

我需要一个字典(或任何其他集合),它始终保持按值排序,并可以按键索引。我的目的是实现一个缓存,其中对象具有唯一的键和与之关联的度量。当必须进行缓存替换时,将删除度量最小的对象。它需要尽可能快,所以每次更换完成时都要订购完整的订单并不是一个好的选择。什么好主意吗?Thx

Dictionary<比;总是按值排序,从键查找索引

像这样的东西应该可以正常工作(没有经过很多测试):

http://pastebin.com/eYeE33F5

似乎优先级队列是您正在寻找的。这个类有很好的使用二进制堆的实现。示例:http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

您可以将任何类型的快速优先队列(看这里:. net中的优先队列)与标准Dictionary结合到一个新的集合中。插入新元素时,在两个容器中都插入对该元素的引用。当通过"key"查找元素时,使用字典。当您要删除具有最低"度量"的元素时,使用优先级队列来查找它,从元素本身获取键,然后很容易从两个容器中删除元素引用。

你为什么不保留普通的字典呢?现在,无论何时你需要进行缓存替换,那是你选择具有"最小"值的元素并替换它的时刻。

编辑-这是如何获得最小值的KeyPair。只需在后面使用Key和Value属性:

var minValuePair = myDictionary.OrderBy(p => p .Value).First();

您想要一个按值排序但也按键索引的字典。您不能同时以两种方式排列数据,因此必须有两个集合,即基本键值字典和反向查找字典。第一个是标准字典,第二个是具有相同数据的SortedDictionary,键和值交换了。你必须使两者保持同步。

您也可以编写自己的Dictionary实现,将这两个集合封装为一个。