具有定义的键的顺序的字典类型

我想使用类似于作为字典的[(a,b)]对的简单列表，将类型为a的键映射到类型为b的值，同时保持“用户-specified“，定义键的顺序。（即与普通列表一样 - 我希望能够“追加”一个项目，然后将其识别为“最后一个元素”）。但是，我希望按键的随机访问查找具有比线性更好的性能，即什么Data.Map提供。一种选择是只保持在另外一个普通的地图，它定义它们的顺序键列表：具有定义的键的顺序的字典类型

data OrderedDict a b = OrderedDict (Map a b) [a]

，然后定义append操作等是保持两个关键集合同步。虽然维护相同密钥的两个单独集合似乎很难看。是否有一种现成的数据类型，它已经将有序密钥与按键的高效随机访问查找相结合？

来源

2012-06-08 gcbenison

Java的[LinkedHashMap]（http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html）似乎做了类似的事情：通过地图线索密钥列表。 Python的OrderedDict只是一个对列表，所以他们在这里没有任何帮助。 –

“定义订单”是什么意思？给定两个键“a1”和“a2”，无论“a1”在“a2”之前还是在运行时确定的优先级，它都是先验的固定值？ – Peter

@peter我的意思是'定义顺序'与普通列表相同 - 如果在追加'a1'后追加'a2'，那么'a1'在'a2'之前 – gcbenison

除非我完全误解了你的问题，否则Data.Map完全是这样，使用键类型的Ord实例进行排序。因为它是一棵二叉树，所以实现也保持键的顺序。

Data.Map.keys为您提供地图按键的升序;因为Map的转换（例如map）是纯粹功能性的，所以遍历顺序无关紧要，并且从Map获取一系列键或键/值对的所有方法都会为您提供有序列表。

来源

2012-06-08 06:50:30 valderman

我相信gcbenison正在要求类似'Data .Map“，但增加了保留键插入顺序的属性。 – huon

如果您有自定义键类型，您可以让它定义自己的顺序。尽管如此，如果订单可以程序化地生成，那仍然是有效的。 – Evi1M4chine

如果你只是想除了有O至保存一些固定顺序（如插入时间）（log n）的查找/插入，你可以简单地使用多张地图，并同时更新它们：

Map a b用于存储实际数据，并且
Map Int a它给出了第i个键的顺序。（如果您还需要查询一个给定键的索引，你可以添加一个Map a Int）

来源

2012-06-08 07:29:02 Peter

在ixset图书馆看看 - 它可以让你通过a并通过Int维护组由多个列（索引你的案件）。这比保持地图一致性更可维护

来源

2012-06-08 09:05:19 nponeccop

谢谢 - 'ixset'很酷。在这种情况下，我认为它不符合法案，因为它可能允许不一致的状态（具有相同'Int'字段的多个条目），并且它将需要调用者执行“append”操作来明确指定索引 - 不是普通列表需要。 – gcbenison

具有定义的键的顺序的字典类型

回答

相关问题