雙鏈表與文本編輯器中的數組

我使用ncurses開始了一個實驗性代碼編輯器。我正在使用雙鏈表來存儲/解析/打印文本。儘管我對實現有很大的瞭解，但我還沒有確定是否使用雙鏈表是最好的主意（與使用數組相反）。雙鏈表與文本編輯器中的數組

請注意，當我的意思是數組，我的意思是每行字符數組 - 不是一個線性數組。

以下是我權衡了利弊：

雙鏈表：

更快的字符和行插入
更快的代碼摺疊

陣列：

使用更少的內存
更快的解析
更快的打印我有權使用鏈接列表嗎？或者，他們是這樣做的更好方法嗎？

注：

數組更快的打印，因爲只爲一個呼叫printw，打印一整行。而不是每個角色調用printw。

來源

2013-06-19 tay10r

這可能是有用的：http://en.wikipedia.org/wiki/Rope_%28computer_science%29 – Blender

你確定陣列打印速度更快嗎？我認爲他們會以同樣的速度。此外，如果你使用數組，每個字符必須具有相同的長度，作爲鏈接列表允許混合長度（當'i'佔用與'W'相同的空間時，它很奇怪] –

@Blender謝謝，這很有用。 – tay10r

轉移註釋到一個答案，因爲沒有其他人在被碎裂。

爲什麼不使用字符串（雙向鏈表）列表，其中列表中的每個產品線，這樣你就可以調用printw()每行一次與數組一樣？你也會大大減少存儲需求;在64位機器上，雙字節單字符列表可能使用每字符24字節，這是相當高的開銷。

我其實剛開始這樣做。這似乎是一個相當不錯的妥協（我有一個預感，這是納米使用）。我可能會刪除這個問題，因爲我認爲這是我將與之合作的解決方案。另外，在每次插入/刪除時使用realloc()是一個壞主意嗎？

我可能會設計出列表中的節點的線沿線的：

struct Line 
{ 
    struct Line *next; 
    struct Line *prev; 
    char  *line; 
    size_t  line_len; 
    size_t  line_max; 
};

與line_len記錄當前行的長度，並line_max記錄分配的空間。

刪除某個字符時，我不會撥打realloc();除非實際大小和最大大小之間存在一些相當大的（256字節？）差異，否則我可能不會這樣做。

對於插入，我只會在沒有空間的時候重新分配（當line_len == line_max，但要小心），我會以至少16個字符的增量進行分配（因爲這可能是最小的數量無論如何，malloc()等實際上分配，加上當用戶插入一個字符，他們通常插入幾個）。因此，您希望避免每個字符更改內存分配（調用realloc()），而不必擔心在必要時重新分配內存。

來源

2013-06-19 16:41:03

處分配'16'字節謝謝。如果我移植到'cpp'並使用'std :: string'，那麼呢？這會使用更多的內存嗎？我正在考慮它，只是因爲字符串插入和刪除已經用'string'類完成了。而且，它還可以輕鬆地在「n-byte」塊中調整字符串大小。 – tay10r

雙鏈表與文本編輯器中的數組

回答

相關問題