如何管理內存插入和刪除內容？

爲了方便起見，我只是使用純文本的示例。例如，對於句子I have a cat，我需要malloc變量的char 13個插槽，以便它將所有字母與最終的\0一起存儲。如何管理內存插入和刪除內容？

但是，如果現在我想在cat之前插入lovely？看起來我必須創建一個足夠大的新陣列並複製所有內容。

更糟糕的是，由於計算機上添加了多少東西是不可預知的，因此似乎我必須在每次添加一個新字母時重做malloc和複製東西，也就是說，對於每個字母lovely，結果不是一個聰明的解決方案。（電腦提前不知道'可愛'這個詞，呃？）

「更好」的解決方案似乎是在第一個地方創建了一個足夠大的數組，這樣每次插入一個新的字母時，程序只複製並移動它後面的所有內容。但是，這仍然是低效率的，特別是當文檔很長時，我從一開始就添加了一些東西。

這同樣適用於'刪除'，每次刪除一個字母時，我必須複製一切後面的所有內容並縮小數組大小。

使用節點而不是數組來存儲內容似乎是一個同樣糟糕的解決方案，就像現在每次我想在內容中間做一些事情一樣，我必須從頭開始一直走路。

那麼在這種情況下管理內存的正確或有效的方法是什麼？我想要在C這樣的低級別編程的答案，這需要直接內存分配和解除分配，而不需要「魔術」功能或庫，它們已經可以爲您處理所有事情。

來源

2013-07-26 OneZero

如果你問十個人，你會得到十個不同的答案。我們需要更多關於您的場景的信息。什麼是關鍵因素？性能有多重要，您是否知道整個流程或空間需要的內存總量？你多久會期望這些東西成長等等。人們寫下PH。D在這個問題上。這就是說一些經典的想法是循環緩衝區，指數增長。如果連續內存不是問題，那麼您可以查看其他表示，例如鏈接列表和樹......但這取決於您的要求。 – UpAndAdam

我認爲關鍵因素是能夠快速插入/刪除內容。內存總量可能無法預測，因爲容量應根據需要增長。你可以將它想象成類似於文檔編輯器的東西，你可以快速進入段落中的任何地方並在那裏插入/刪除東西，而且你不知道用戶的文字會是多長時間，對吧？這是一個類似的場景。 – OneZero

一個有效的解決方案是使用循環數組列表。

http://en.wikipedia.org/wiki/Circular_buffer

在預分配陣列的一些大小，還跟蹤指針到列表中的「開始」（在「C」的第一個索引，然後「L」的指數）。這樣，要在開始處插入或刪除，您可以添加到內存的物理端並更改指針。

要索引到數組中，只需索引到數組[（開始指針+索引）％大小]。

如果字母數量變得太大，您仍然需要複製到一個新的數組。就預先分配的數量而言，一個不佔用太多時間的系統是在數組每次變滿時將其大小加倍。這不會增加太多的開銷。

編輯：如果您需要將數據插入列表中間，則循環數組列表將不會有用。但是，將數據添加到列表的開始和結尾以及修改或訪問中間數據很有用。

來源

2013-07-26 14:27:07

數組列表要求每個元素彼此相鄰，那麼它如何允許在數組中間插入操作？或者如果我使用鏈表（可能是圓形），那麼似乎沒有辦法隨機索引列表，我想。另外，我不認爲我可以控制malloc實際內存的位置，那麼如何將內存添加到「內存的物理結束」？由於內容的編輯可能是絕對不可預知的，因此我想要解決方案，在任何隨機編輯之後（例如記事本），不會弄亂整個數據結構。 – OneZero

使用鏈接的內存塊列表聽起來像是一個很好的中間解決方案。每個節點將成爲一定大小的「頁面」。爲了加快修改中間頁面的內容，你可以使用一個索引數組，這個索引數組可以在整個文檔中包含指向絕對位置的頁面指針。

缺失應該只是進行時和整個頁面是空的。在那一刻，你應該這樣做：

prevPage->next = nextPage; 
pageFree(page_to_delete);

來源

2013-07-26 14:31:27 user2553780

如果你想輕鬆地處理字符插入和刪除操作，不重的malloc一遍又一遍，我認爲最好的辦法是雙向鏈表。

檢查出在這裏：DoublyLinkedListExample（我學到了在學校，但我認爲這個政黨成員解釋了很簡單，它是如何工作以及如何使用它），你的數據

這些只是結構（節點），一指向前一個元素的指針和指向下一個元素的指針。如果你不明白它是如何工作的，那麼只需查看簡單鏈接列表的教程，然後它就會更容易。

只是練習它beceause其相當開頭難明白。繼續培訓，你會達到它:)

來源

2013-07-26 14:33:48 Jackyto

我很猶豫是否使用鏈表，因爲它不允許隨機訪問。如何快速進入列表的中間位置，而不必每次都從列表的最後選擇一條路徑？ – OneZero

如果你想進入中間，我認爲你將不得不遍歷你的名單。之前，如果您想快速瀏覽清單，您可以對其進行排序，但是在我的腦海中，更快的方式去做 – Jackyto

我很困惑。爲什麼我需要在這種情況下排序列表？我排序一個句子的清單是沒有意義的。這不是簡單數字的數組/列表。 – OneZero

鑑於你在評論中的迴應澄清你的用例，我的建議是考慮內容的鏈接列表，在你的純文本例子的隱喻中，元素鏈表是單詞或段落或頁面，而單詞本身是連續的數組。

雖然它們之間的導航是不是超級快，它似乎是你的表現必須是快速的插入和刪除。通過使用小的連續字，通過控制小的n來最小化重新分配/收縮和複製東西的成本。這是通過具有許多鏈接列表元素的n來實現的。

這從具有內容的空間局部性的「個人」作品，同時讓你挑一個上級列表/樹狀結構，以幫助獲得的時間局部性利益融合性能改進在一起。

的一件事這真的沒有解決是需要事實的處理之後要做這個數據是什麼，和什麼級別的性能確實是可以容忍的。常量malloc調用對於延遲是不利的，因爲它阻塞了系統調用;所以你可以進一步考慮使用已經提到的另一個解決方案，例如循環緩衝區或者管理你自己更大的內存塊，以將自己分配給這些元素。這樣，當你需要更大容量的內存來處理時，你只需要malloc，並且不一定需要重新複製頁面之間的所有內容，而只是一小塊不適合的內容。

再次正如我在我的評論說，人們寫論文這個有點兒事，和它的OS設計和系統的理解的重要組成部分。所以把這一切都用一粒鹽。有很多事情需要考慮，不能在這裏介紹。

來源

2013-07-26 15:05:16 UpAndAdam

這是不完全清楚你的用例是什麼。

既然你提到文本操作，並有高效的插入，刪除和隨機訪問操作，我想你可以使用rope data structure，這是一個基本上在其節點（粗略）存儲短字符串片段的二叉樹。有關詳細信息，請參閱鏈接的文章。

來源

2013-10-23 20:49:20

如何管理內存插入和刪除內容？

回答

相關問題