14

What's the most Swiftian way to iterate backwards through the Characters in a String? i.e. like for ch in str, only in reverse?

I think I must be missing something obvious, because the best I could come up with just now was:

    for var index = str.endIndex; 
            index != str.startIndex; 
            index = index.predecessor() {
        let ch = str[index.predecessor()]
        ...
    }

I realise "what's the best..." may be classed as subjective; I suppose what I'm really looking for is a terse yet readable way of doing this.

Edit: While reverse() works and is terse, it looks like this might be quite inefficient compared to the above, i.e. it seems like it's not actually iterating backwards, but creating a full reverse copy of the characters in the String. This would be much worse than my original if, say, you were looking for something that was usually a few characters from the end of a 10,000-character String. I'm therefore leaving this question open for a bit to attract other approaches.

Matt Gibson
  • 37,886
  • 9
  • 99
  • 128
  • Your code is probably the best way since it actually iterates only once. I suspect that `reverse` is also going to have to iterate the entire string in order to reverse it with something like `index.successor ` and then iterating the reversed string is going to have to again use something like `index.successor`. It is messy because it has to deal with multi UTF-16 code units. – zaph Aug 10 '14 at 11:56
  • 1
    I tested with full unicode strings with length up to 300,000 UTF16 units. Using the OP code as the base the reverse implementation took 3.4 times longer and the lazy reverse implementation and took 1.6 longer. All methods have the same O(N) cost and the range of performance was at most 3.4x which is probably not a noticeable difference in an app with string lengths of under 10k characters given that some work will be done in the enumeration and the slowest enumeration took ~0.12 sec (for 10k) – zaph Aug 10 '14 at 13:01
  • @Zaph Thanks for the testing work, especially for testing the difference with lazy. – Matt Gibson Aug 10 '14 at 13:46

5 Answers5

30

The reversed function reverses a C: CollectionType and returns a ReversedCollection:

for char in "string".characters.reversed() {
  // ...
}

If you find that reversed pre-reverses the string, try:

for char in "string".characters.lazy.reversed() {
  // ...
}

lazy returns a lazily evaluated sequence (LazyBidirectionalCollection) then reversed() returns another LazyBidirectionalCollection that is visited in reverse.

Matt Gibson
  • 37,886
  • 9
  • 99
  • 128
pNre
  • 5,376
  • 2
  • 22
  • 27
  • Thanks! I thought I'd tried this, but had missed the fact that the error message I got was because my String was actually an implicitly-unwrapped Optional (which *doesn't* conform to CollectionType, so apparently needs to be explicitly unwrapped for reverse() to work, even though it's already implicitly unwrapped. Gah!) – Matt Gibson Aug 10 '14 at 10:37
  • Is this actually reversing the whole string before things get going, as opposed to iterating from endIndex backwards? i.e. if you're iterating to search for a character that might be a few characters from the end of a 10K string, will this be inefficient? – Matt Gibson Aug 10 '14 at 10:49
  • What do you mean? Just tested and `"ƒ¥"` is correctly iterated. – pNre Aug 10 '14 at 12:03
  • 2
    Interesting—I didn't know about `lazy`. Thanks! – Matt Gibson Aug 10 '14 at 13:46
  • 1
    @ThomasKilian Updated. – Matt Gibson Dec 13 '16 at 16:03
  • 1
    this can be updated to "string".reversed() now. It's also worth noting that `ReversedCollection` is a view into the same data as the input string but in reverse order, meaning that no new memory is allocated by calling it. So to answer @MattGibson's comment, no. It is efficient because it does not actually reverse anything. – grego Feb 17 '20 at 00:52
5

As of December 2015 with Swift version 2.1, the proper way to do this is

for char in string.characters.reverse() {
    //loop backwards
}

String no longer conforms to SequenceType<T> but its character set does.

pbush25
  • 5,228
  • 2
  • 26
  • 35
4

Not sure about efficiency, but I will suggest

for ch in reverse(str) {
    println(ch)
}
Alexey Globchastyy
  • 2,175
  • 1
  • 15
  • 19
  • Thanks for the point about the efficiency; I hadn't considered that reverse() might actually reverse the whole string first, rather than providing a reversed Range/iterator. Hmm... – Matt Gibson Aug 10 '14 at 10:51
  • If you're looking for efficiency then String isn't suitable anyway. You'll want to be working with NSData to get performance. – Abhi Beckert Aug 10 '14 at 12:07
  • @AbhiBeckert I'm not that concerned with efficiency; it just seemed like there should be a shorter way of expressing the code I already had without *reducing* the efficiency. – Matt Gibson Aug 10 '14 at 15:19
  • @MattGibson are you sure you are actually reducing the efficiency though? I just tested Alexey's code without the `println()` (so an empty for loop), and just iterating the string is two full orders of magnitude slower than reversing it. As I said, if you want performance use NSData. Iterating over a swift String is extremely slow. I don't think reverse actually touches the data in memory, it likely sets a flag to change invert the direction of future string operations. – Abhi Beckert Aug 10 '14 at 23:50
  • @Abhi Well, the reverse() returns an array with all the characters, reversed, rather than an iterator. I'll maybe do some benchmarking later. – Matt Gibson Aug 11 '14 at 06:08
  • @MattGibson From my testing anything you do has shockingly bad performance. Iterating over a 10 byte string takes about as long as I'd expect a 100MB string to take based on past experience I have with large NSString objects. However I didn't use proper production compile settings, I was just in the playground, and there are definitely performance bugs in playground. – Abhi Beckert Aug 11 '14 at 06:11
1

Here is a code for reversing a string that doesn't use reverse(str)

  // Reverse String

func myReverse(str:String) -> String {

    var buffer = ""

    for character in str {

        buffer.insert(character, atIndex: buffer.startIndex)
    }

    return buffer
}

myReverse("Paul")  // gives “luaP”

Just a little experiment. For what its worth.

Ok, leant how to read the question....

Would this work Matt?

func ReverseIteration(str:String) {

    func myReverse(str:String) -> String {

        var buffer = ""

        for character in str {

            buffer.insert(character, atIndex: buffer.startIndex)
        }

        return buffer
    }

    // reverse string then iterate forward.

    var newStr = myReverse(str)

    for char in newStr {

        println(char)
        // do some  code here

    }
Paul Tervit
  • 11
  • 3
  • Well, that certainly produces a reversed string, but that's not actually what I was wanting to do in the question. And I'm not sure why you'd want to reverse a string without using Swift's provided reverse(str)..? – Matt Gibson Nov 29 '14 at 23:25
  • Me neither. Does't reverse(str) put the string into a array e.g. ["l","u","a","P"] rather than getting "luaP"? Still learning. – Paul Tervit Nov 29 '14 at 23:46
-3

this?

extension String {
    var reverse: String {
        var reverseStr = ""
        for character in self {
            reverseStr = String(character) + reverseStr
        }
        return reverseStr
    }
}
Phil
  • 1