作爲鏈表的C字符串？

在c字符串中，我們需要分配合理大小的內存。爲了避免在字符串操作中重新分配，我們可以在C＃或Java中使用類似Stringbuilder的東西，或者在C中 - 只爲字符串分配更多的內存。但是如果我們事先不知道內存需求，它仍然會成爲一個問題。我們有像鏈表一樣的實現嗎？我的意思是要分配的內存和方法c_str()塊列表，它從它的節點作爲鏈表的C字符串？

liststring a(4); // requested block size 
a.append("hello "); 
a.append("world"); 
// should create three nodes, 4 bytes allocated for each 
// "hell" -> "o wo" -> "rld" 
a.c_str(); // "hello world";

創建C-字符串或者我們用另一種方法，如果我們想避免重新分配？請說明這是不是個好主意。

來源

2012-02-23 Jan Turoň

當你調用c_str（）時，你需要將字符串放入連續的內存緩衝區，所以通常認爲從一開始就這樣做是個好主意。使用固定大小的塊的鏈表也意味着構建一個長字符串將花費O（n）進行分配，而通常的字符串指數增長分配策略花費O（log（n））的代價是浪費更多的內存。 – 2012-02-23 19:48:57

但是，如果我們想追加很多次，並且我們不知道有多少和多少大小，我們可能會分配太少的字節（因此需要重新分配）或太多（浪費內存）。 – 2012-02-23 19:53:53

有一種算法保證不使用超過四倍字符串長度的內存，每次重新分配平均需要'O（1）'次。如果緩衝區的當前大小爲「n」，並且字符串的長度超出緩衝區，則應該重新分配「2 * n」大小的緩衝區。如果它小於'n/4'，那麼'n/2'大小的緩衝區應該被重新分配。 – citxx 2012-02-23 20:01:08

有關將字符串保存爲樹的數據結構，請參閱Ropes的文章。這與你的想法很相似。

來源

2012-02-23 19:52:42 AShelly

非常好，這正是我一直在尋找的！ – 2012-02-23 20:04:23

有沒有標準的方法來做到這一點。但是你可以實現自己的chars鏈表和轉換爲C字符串。

來源

2012-02-23 19:54:00 citxx

我假設你的意思是C++而不是C。

C++中的字符串操作的標準類是std :: string。

字符串類Java或.NET是不可變的。 std :: string另一方面是可變的，所以它的行爲完全像StringBuilder。

來源

2012-02-23 19:54:26 ZunTzu

不，我的意思是C，但C++也可以。 std :: string不提供我想要的功能。還是呢？ – 2012-02-23 20:00:19

可能不是，因爲我知道的所有實現都是在內存中連續的。看到AShelly的答案：這就是你要找的。 – ZunTzu 2012-02-23 20:08:13

作爲鏈表的C字符串？

回答

相關問題