Why is String not a RandomAccessCollection of Character? Why is string[i + 1] not O(1)?
Predict first
What does this print?
let s = "cafe\u{301}" // e + combining accent
print(s.count, s.unicodeScalars.count)- 4 4
- 4 5
- 5 5
Mental model. A sentence is not an array of letters — a letter can be an “é” made of two code points, or a family emoji made of seven. You have to read forward to know where the next “character” starts.
A Character is an extended grapheme cluster: a user-perceived character that may be composed of many Unicode scalars — flags (two regional indicators), emoji with skin tones, or a family joined by zero-width joiners.
To find the next Character, the string must scan forward and apply grapheme-breaking rules. That makes indexing O(n) from the start, which is incompatible with RandomAccessCollection. Indices are String.Index, not Int, precisely so the compiler stops you from doing arithmetic that would be wrong.
When you do need random access, drop to a view: utf8, utf16, or unicodeScalars.
The accent is its own scalar, but it merges with the e into one Character. Finding character boundaries means walking the string, which is why indexing is not O(1).
Common traps
- “
countis O(1).” It is O(n) in the general case because grapheme boundaries must be computed. - “
string.countis the byte size.” It is the number of Characters — wildly different fromutf8.countfor emoji and non-ASCII text. - Converting String.Index to Int. You can via
distance(from:to:), but that is O(n) and you are usually solving the wrong problem.
They might follow up with
- Why is
String.Indexnot an Int? To encode the “this index is only valid in this string after this edit” invariant and prevent out-of-bounds arithmetic. - When is indexing actually cheap? Over
utf8— that is a plain byte collection with O(1) offsets.