具有定義的鍵的順序的字典類型

我想使用類似於作爲字典的[(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

具有定義的鍵的順序的字典類型

回答

相關問題