4 ms·
As with all things, it's a balance of several competing interests. If the string is stored in a contiguous array of memory, you can maintain a pointer to the s
by ModernMech 6y ago
As with all things, it's a balance of several competing interests.
If the string is stored in a contiguous array of memory, you can maintain a pointer to the start of the string and then do some pointer arithmetic to get char n. This is an O(1) operation.
If you store the string as a linked list of characters, then to access the nth character you have to follow a bunch of pointers until you get to that char. This is an O(n) operation, and it's going to take up more memory (4/8bytes per pointer, plus a byte for each character). Also it can make your memory fragmented. The upside is that you can grow and shrink the string. Adding chars to the front or end will be O(1). Adding chars in the middle will be O(n).
In the array case, if you want to modify the string you'd likely have to allocate a new block of memory for the larger string and copy all chars over. That will be an O(n) operation.
Null terminated strings are annoying because you don't know how big the string is without reading it. So getting the length of the string is an O(n) operation. The plus side is you don't have to carry around an extra byte(s) to hold the string length.
So it really depends on what you're doing with the string. Are you reading the string and accessing random characters often? Then an array is better. Are you mutating the string often? Then probably a linked list is better. Do you need to know how large your string is? Then keeping a byte around to indicate that is useful. But if you often read the entire string until the NULL character, then that extra memory dedicated to its length is wasted.
- mannerheim 6y agoFor cases like strings as lists of chars and null-terminated strings, I think the reasons why they're generally considered mistakes is because the tradeoffs don't make sense, at least not compared to their downsides. Null-terminated strings save a constant number of bytes, at the expense of expensive length-checking, potential complications, and liability for generating footgun mistakes (I believe they've been the cause of many a CVE over the years). Most systems aren't generally memory-starved enough that you can't spare the constant number of bytes for keeping track of string lengths. As for linked lists, I believe the times where they're more performant are fairly rare, and unlikely to occur at the level of a data structure for individual characters, which is reflected in String's poor performance in practice. Pretty much the only advantage you get from using string-as-a-list-of-chars is that you get to use List's Functor and Monad instances, but that probably should be avoided in any case.
- userbinator 6y agoMost systems aren't generally memory-starved enough that you can't spare the constant number of bytes for keeping track of string lengths. That's the sort of thinking that gave us instant messaging applications which take gigabytes of memory and can saturate several year-old CPU cores trying to render some text... That said, null termination + length is usually a good string representation. Instant length retrieval with the ability to ignore it when your algorithm needs to read to the end anyway.
- catlifeonmars 6y agoAll of the above! And also there needs to be a way of dealing with variable length characters. This is the problem that language designers need to solve for.
- Akronymus 6y ago> If the string is stored in a contiguous array of memory, you can maintain a pointer to the start of the string and then do some pointer arithmetic to get char n. This is an O(1) operation. Pretty sure that only works 100% when in pure ascii. In UTF there is the possibility of characters being more than 1/2/4 bytes.