Subscripting in String extension to access substrings and characters with Int types

Evolution Pitches
17

You have to go through the entire string from the beginning. There is no alternative. Either:

  • You start from the beginning and go until you hit the index. Avg. O(0.5(count))
  • You start from the beginning and go all the way to the end in order to figure out where the end is. From that you know which end of the string is closer so you can walk from there again until you hit the index. Avg. O(1.5(count))

Your new implementation successfully defers the initial computation of the count out of the method, but you still require the client to compute it in order to give it to you. So the extra complexity is still there, it is just in someone else’s hands.

The unusual handling of invalid indices results in some very surprising behaviour:

XCTAssert(cadena[..<100].elementsEqual(cadena))
// Fails: “A long time ago in a galaxy far far awa”

XCTAssertEqual(cadena[100], cadena.last!)
// Passes as is, but fix the first test and instead, BOOM!

There is another solution out there that efficiently handles all except the tolerance of out‐of‐bounds indices, without any need for extensions. Walk the string once creating an array.* Then after that you are dealing with a random access collection with integer indices:

let cadena = Array("A long time ago in a galaxy far far away") // O(n)

// O(1) from here on:
cadena[5...25]

cadena[5...]

cadena[..<25]

cadena[1...]

cadena[...30]

cadena[10...]

cadena[..<30]

*This will bloat the memory footprint, which is why String does not work this way by default. The array also will not correctly merge characters, mishandling Unicode equivalence if you start mutating it.

1 Like