String reverse method


#1

I could’ve easily missed it, but after some searching around, I didn’t see a method to reverse a string in the string class, which has been something I have needed a few times in the past. Could something like this be implemented?

String String::reverse() const
{
    if (isNotEmpty())
    {
        String reversedString;
        
        for (unsigned long int i = text.length(); i > 0; --i)
            reversedString += text[(int) (i - 1)];
        
        return reversedString;
    }
    
    return *this;
}

I realize that this is not as efficient as other class methods, I initially tried to directly use the typedef CharPointer_UTF8 CharPointerType, but also didn’t see any methods in the CharPointer_UTF8 class that allowed me to swap around the string characters, so I wrote it this way, which isn’t as efficient.

Again, apologies in case I missed the method somewhere in the String class, its a very large class and I just searched for keywords like “reverse” etc.


#2

In 25 years as a professional developer, covering pretty much every possible subject area, I’ve never once needed to reverse a string!

And yes, that’s pretty much the least efficient way you could write it, probably O(n^2). Maybe this could be a challenge for anyone reading - who can write the most efficient implementation? I can think of a way to do it in O(n).

We won’t be adding a method to String to do it though, even a good one. If you really need this, it can just as easily be done with your own free function, there’d be no advantage in adding it to the String class.


#3

ha, reminds me that in-place string reverse was an interview question we used to ask :slight_smile:


#4

Alright. I originally used a swap function to swap first and last, then move inward by one element, then meet in the middle… but I didn’t want to include STD and I don’t think it was any more efficient…

Definetly odd that in the past month, I ran into two occasions where I needed to reverse a string (I won’t discuss that now, since it seems I’ve made a fool of myself).

Would be interested to see some more efficient ways, as I do intend to use a reverse string method in 2 of my applications.


#5

Not at all - I’m sure there are lots of valid reasons why people might need to do this, I’ve just never seen one!

Reversing an ASCII or UTF32 string would be easy. The tricky bit with the juce ones is that they’re UTF-8. I think it’s possible to write a very complicated optimal solution that can reverse such a string in-place without allocating, but there’s a much more practical approach that allocates a new string but still only takes O(n) to copy it.


#6

As of now, the only way I can think of to make an efficient method wouldn’t work in the String class. In my head, the method would involve a doubly linked list and a bool that would define whether the string is read from head to tail or tail to head, but that whole concept isn’t applicable to the current underlying structure of the String class and it isn’t truly reversing the string in a traditional manner, more of a hack than anything.

At any rate, I’ll continue to work on a more efficient method, and even post it up here afterwards, despite the fact it won’t be included and despite the fact it’ll probably be used as a means to get some laughs out, since I’m still not on a professional level of coding. I really want to push myself to make it great…

Would still love to see a professional algorithm, that follows your idea of an in-place method belonging to the linear family. I myself cannot figure out how to overwrite elements in the string to make it in-place.


#7

I suggest looking into ICU for a true string reversal, one that can handle multiple scripts: characters in a string don’t always map in a 1:1 fashion, as that is script and language dependant (specifically any character that is comprised of multiple codepoints or code units).


#8

Challenge accepted! :smiley:
Well, I don’t think I wrote the most efficient implementation, but it should be O(n).

juce::String reversed(const juce::String& in)
{
  juce::String out{in.getCharPointer()};

  const auto inBegin = in.getCharPointer();
  auto inPtr = in.getCharPointer().findTerminatingNull();
  auto outPtr = out.getCharPointer();

  while (inPtr != inBegin)
  {
    --inPtr;
    outPtr.write(*inPtr);
  }

  return out;
}

#9

This is mean, I was starting to try it, but UTF really messes things up… :slight_smile:
Is this even possible in O(n) without more than one char swap space?


#10

Maybe I’m being stupid, but isn’t this the same problem as reverse indexing an array? Here’s something that I just tested a bit and should work, only needing to iterate through half of the string and allocating one character.

String reverse (String s)
{
    for (int i = 0; i < s.length() / 2; i++)
    {
        auto tmp = arr[i];
        s [i] = arr [size - i - 1];
        s [size - i - 1] = tmp;
    }
    return s;
}

#11

Your compiler might ask, what arr is? You probably meant auto tmp = s[i]; But that’s the least problem.

The actual problem is, that there is no operator[] which is not const (at least I don’t see any in the docs). You cannot write into the array like that.
And that’s for good reason: operator[] const returns a juce_wchar = 32 bit. This can be 1, 2 or 4 byte in your string.
Reading is fine, but if you write there, you might need to move the whole middle block to make room for a multi byte character. boing.
You don’t want to reverse a multibyte character byte by byte.

But living in an English speaking country, you might get away with that for some time…

(that’s basically what jules already said…)


#12

˙ǝɯıʇ ǝɥʇ ןןɐ ʇı ǝsn ı ˙ʇnoqɐ uo ǝɹɐ ʇoן noʎ ʇɐɥʍ ʍouʞ ʇ,uop ı


#13

Wow, this method is much faster than mine. Great work. I tested the old fashion way with execution times. Took my algorithm around 0.406 seconds to reverse a 4 word sentence 100,000 times, but yours only took 0.073 seconds. I increased the text size to a paragraph and yours became about 20 times faster. My algorithm is definitely not linear, like Jules said, and yours most certainly is.

I only ever studied algorithm analysis for a few weeks, as an intro to the subject in my data structures class… so I haven’t taken the full blown course, though my school requires it. Apparently, its one of the hardest courses my school offers. I need to do some studying on my own before


#14

Thanks for the critique! I originally tested that with std::string on the command line so obviously a few copy-paste errors there. I didn’t consider multi-byte characters. To make that algorithm work I guess I could amend it by converting the string to an array of strings, but I wonder how much that impacts the memory complexity… I’ve been using a similar process for reversing arrays in some projects and it seems to be a decent enough way to go about it.


#15

@McMartin Not bad! I think you could probably squeeze a bit more out of it by only iterating the original string once to find its end point, then using that pointer to pre-allocate a new destination string using String::preallocateBytes()

The best in-place reverse I can think of would involve two pointers to the start and end, which you move towards each other swapping over the bytes like normal… BUT you’d need to give each pointer a 4-byte moving cache of the data that was there previously, so that if there’s an overlapping write it won’t mess up the next read. A bit fiddly to write, but yes, it could be done in O(n) with just 8 bytes of working space.


#16

Yes, that’s how I started. But I realised, whenever I find a multibyte character at the end and I swap it with a single character at the front pointer, I overwrite the subsequent character. Hence I have to move the whole memory block by one (or three if 4-byte character) to the back. That would make the solution O(n^2).

Another problem is, when I read the back pointer, I have to check, if the byte before actually marks a multi-byte character. That is nasty, but wouldn’t end up in the O-notation, as it is just a linear factor.

I can think of a recursive method, but in this case I have a stack swap space for each recursion. So that would be actually be cheating, as it doesn’t end up with one 4-byte swap space, but n/2 worst case.

Maybe I am missing something, but I doubt it is possible.
So much for weekends brain gymnastics… :wink:


#17

Ah, yes, good point. Yeah, you’d need a stack at each end rather than just 4 bytes, because if you had e.g many 1-bytes chars followed by many 4-byte chars you’d end up with more than 8 bytes needing to be cached.

Ah well. TBH an in-place reverse is an interesting puzzle but unlikely to actually ever be useful, as a real-world implementation would just return a new string, which is easy to do.


#18

Yep, this one is pretty awesome, and is pretty damn fast. Would you be ok with me using this @McMartin? I could include credits to you in the source file for that function, my app is GPL_v3.


#19

FWIW here’s how I’d do it (completely untested though!)

juce::String reversed (const juce::String& s)
{
    juce::String result;

    auto start = s.getCharPointer();
    auto end = start.findTerminatingNull();
    auto size = (size_t) juce::getAddressDifference (end.getAddress(), start.getAddress());

    if (size != 0)
    {
        result.preallocateBytes (size + sizeof (juce::String::CharPointerType::CharType));
        auto dest = result.getCharPointer();

        for (;;)
        {
            start.write (*--end);

            if (end == start)
                break;
        }

        dest.writeNull();
    }

    return result;
}

#20

preallocateBytes() already adds the extra byte for the null character, and both MSVC and gcc are fine with preallocateBytes(end - start) (I haven’t tested with clang). So here is my final solution:

juce::String reversed(const juce::String& in)
{
  auto inBegin = in.getCharPointer();
  auto inPtr = inBegin.findTerminatingNull();

  juce::String out;

  if (inPtr != inBegin)
  {
    out.preallocateBytes(inPtr - inBegin);

    auto outPtr = out.getCharPointer();

    while (inPtr != inBegin)
    {
      --inPtr;
      outPtr.write(*inPtr);
    }

    outPtr.writeNull();
  }

  return out;
}

@joe_04_04: feel free to take my first solution or this one. I would be honored to be credited.