連續可變有序列表

這可能存在也可能不存在，但我正在尋找一種方法來存儲內存中連續的整數的排序列表，合理緊湊並允許O（log n）分期插入和刪除。各種自平衡二叉搜索樹似乎都具有我想要的插入和刪除屬性，但是在各處都使用指針來實現，這與我的用例非常吻合。有任何想法嗎？連續可變有序列表

（實現語言將幾乎肯定是C，如果它很重要。如果有任何的你建議現有的實現，那就更好了，但我很好寫我自己的。）

來源

2013-06-11 Andrew Pendleton

數組的問題在於，您必須調整整個數組的大小，以便添加新元素，以便將'malloc'指向元素的新指針。這也意味着你將分配比你需要的更多的內存，這樣你就不會不必要地過度調整它。（例如，每當它滿滿時加倍）那麼，究竟是什麼原因讓你需要它？你是否已經知道初始化時需要的確切大小？ – GRAYgoose124

對不起，直到現在纔看到您的評論。他們是經常被壓縮和刷新到磁盤的列表，然後被應用程序的其他部分讀取。讀取不僅僅是寫入，而且讀取它們的任務需要能夠真正快速地反序列化，所以只需將文件內容解壓縮爲ram並按原樣使用即可，非常理想。一組單獨的任務會突變列表，並且在突變時，將從頭開始已知添加或刪除的整數數量，因此可以分配足夠大的緩衝區以適應當前列表和新整數。 –

一個binary search tree能使用array來實施。

來源

2013-06-11 17:05:27 Kninnug

這是真的，但我還沒有看到一種方法來實現一個數組-BST的BST平衡操作是O（log n），這意味着我不得不忍受它不平衡（這意味着它不會緊湊或高性能），或犧牲O（log n）插入和刪除。 –

考慮到「讀取發生的次數多於寫入次數」這一事實，您可以嘗試在其上使用dynamicaly-resized array + binary search。因此，您將獲得O(log n)時間訪問元素（讀取），但是您必須支付O(n)進行插入/刪除（O(log n) - 搜索陣列中的適當位置+ O(n) - 將元素向右或向左移動）。這有點慢，但這是如何解決問題的方法。試着想一想。

來源

2013-06-13 03:56:18

連續可變有序列表

回答

相關問題