Is String's subscript O(n) when given a lot of combining code points?

[Karl]

That's right. I mentioned that in the other thread about startIndex in standard library collections:

@Karl

Another Collection complexity requirement I find myself having to break from time to time is the O(1) subscripting requirement. It doesn't really work if you need to transform/copy the underlying data in order to produce the result.

For instance, LazyMapCollection obviously cannot meet these requirements unless its transform closure is O(1).

I wonder if we could loosen the requirement, and say that the complexity of accessing a Collection's element via a subscript should not depend on the length of the collection (i.e. O(1) WRT length), but that it can depend on other things such as the size of the element being accessed.

As you say, Character needs to copy its underlying data, and there can be a varying amount of data from character to character, so not all characters will take the same amount of time to access via the subscript.

However, it is still independent of the length of the entire string; the same character won't take more time to access if it were part of a longer string. That's what (I think) we mean by O(1) in this context.