C-string as linked list?

Question

In c-strings we need to allocate reasonable size of memory. To avoid reallocations in string operations, we can use something like Stringbuilder in C# or Java or - in C - just allocate more memory for string. But still it can be a problem if we don't know the memory requirement in advance. Do we have some implemetation like linked list? I mean to allocate list of blocks of memory and method c_str() which creates c-string from its nodes

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";

Or do we use another approach if we want to avoid reallocations? Please explain if it is bad idea.

When you invoke c_str(), you will need to put the string into a contiguous memory buffer anyway, so it's generally held that it's a good idea to do so from the start. Using a linked list of fixed sized blocks also means that building up a long string will spend O(n) in allocations, whereas the usual exponential increase allocation strategy for strings spends O(log(n)) at the cost of wasting more memory. — Russell Borogove
– Russell Borogove, Commented Feb 23, 2012 at 19:48
But if we want to append many times and we don't know how many and what size, we may allocate too few bytes (so need to reallocate) or too many (waste of memory). — Jan Turoň
– Jan Turoň, Commented Feb 23, 2012 at 19:53
There are an algorithm guarantees not to use memory more than four times of string length and each reallocate takes O(1) time on average. If the current size of buffer is n and the length of the string is out of buffer, then buffer of 2*n size should be reallocated. If it became less then n / 4 then buffer of n / 2 size should be reallocated. — citxx
– citxx, Commented Feb 23, 2012 at 20:01

AShelly · Accepted Answer · 2012-02-23 19:52:42Z

3

See the article on Ropes for a data structure that keeps strings as trees. It is similar to your idea.

answered Feb 23, 2012 at 19:52

AShelly

35.9k17 gold badges98 silver badges163 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

citxx · Accepted Answer · 2012-02-23 19:54:00Z

0

There are no standard ways to do this. But you can implement your own linked list of chars and conversion to C string.

answered Feb 23, 2012 at 19:54

citxx

2,54517 silver badges42 bronze badges

Comments

ZunTzu · Accepted Answer · 2012-02-23 19:54:26Z

0

I am assuming you meant C++, not C.

The standard class for string manipulation in C++ is std::string.

String classes in Java or .NET are immutable. std::string on the other hand is mutable, so it is behaving exactly like StringBuilder.

answered Feb 23, 2012 at 19:54

ZunTzu

7,8483 gold badges35 silver badges40 bronze badges

2 Comments

Jan Turoň Over a year ago

No, I mean C, but C++ would be also fine. std::string does not provide the functionality I want. Or does it?

ZunTzu Over a year ago

Probably not, as all implementations I know are contiguous in memory. See AShelly's answer: it is what you're looking for.

Collectives™ on Stack Overflow

C-string as linked list?

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related