# String reverse method

Ah, I’d forgotten that it already accounts for the null.

But no, (end - start) would definitely not be right!
Mainly because TBH I’ve no idea what it would actually do - those are not pointers, they’re objects of a templated type, so if operator- is defined, then whatever it does probably won’t be something you expect. And also, String::CharPointerType could be UTF16 or 32, in which case you’re not dealing with bytes at all!

Ahhh darn, was hoping to give your algorithm a spin.

Wow, thanks @McMartin! I certainly will credit you, but I wouldn’t be too honored, I’m a 3rd year CS student with practically no accomplishments… lol.

Would you prefer to be credited by your username, or something else?

I would prefer my complete name: Alain Martin. Feel free to add a link to my GitHub profile: https://github.com/McMartin.

Ok great, I’ll use your full name and will supply the GitHub link.

If I could ask one more thing, can someone point out to me how it was obvious that my algorithm was O(n^2)? As mentioned before, I had a quick couple weeks of algorithm analysis, but not the full blown course, so I don’t easily see how it is O(n^2) by just looking at my code, as I didn’t use any nested loops. Does it have something directly to do with my code? Or the relationship between my code and the JUCE code I’m calling? I’m probably way off base, but my guess is it has something to do with the [] operator and maybe how the pointer must iterate through the characters every time the loop executes.

You are guessing right.
String::operator[] calls CharPointer_UTF8::operator[], or CharPointer_UTF16::operator[], or CharPointer_UTF32::operator[] depending on the string encoding. CharPointer_UTF32::operator[] is O(1) (i.e. constant), but CharPointer_UTF8::operator[] and CharPointer_UTF16::operator[] both call their operator+=, which increment a pointer in a while loop, so they are O(n) (see https://github.com/WeAreROLI/JUCE/blob/master/modules/juce_core/text/juce_CharPointer_UTF8.h#L201 for the UTF8 case).

Also beware that depending on the encoding format that the string is using internally, this
method may execute in either O(1) or O(n) time, so be careful when using it in your algorithms.

Great, glad to see I didn’t entirely make a fool out of myself! And it’s strange, I’m all over the JUCE documentation on the site, but haven’t seen big O pop up really anywhere… guess I need to read the comments more thoroughly… thanks for the help and tip!

Ok, here’s a simple solution for ya, thanks to @eyalamir :

String str {"A string"};
auto stdStr = str.toStdString();
std::reverse( stdStr.begin(), stdStr.end() );
DBG( str ); // gnirts A
1 Like

Awesome, using the std algorithms library. And I’m sure happy to see a professional developer who seems to have needed a string reversed… others here made me feel like I was totally deranged for needing it!

yeah, I needed to convert an int into a String, and include commas every 3 digits.
splitting the number into digits via modulo and /= 10 gave me a reversed string, so I needed to reverse it to get the digits in the correct order

…except that like all the posts in this thread explain, that won’t work because of UTF8.

I did post a correct solution above!

If you really want to use std::reverse then the only way to do it correctly would be to convert the string to an array of UTF32 ints, reverse that, and then convert it back to UTF8. Which would be a bit shorter to write than my solution above, but less efficient.

3 Likes

It sure prints out correctly in my project, so… I’m not sure why you think it doesn’t work when it clearly does… I must be only using characters that aren’t affected by the restriction you’re describing. Either way, it works, so I’m not complaining!

Did your test have multibyte characters?

In UTF-8 many characters are identical to the latin1 characters. Only characters >127 are encoded in multiple bytes. If the most significant bit is set (>127), several bytes have to be treated as a group, and if you reverse that string, you must not reverse the individual bytes of that one character.

That is also the reason, why String length() and getNumBytesAsUTF8() give different results. If in your test case they are the same, you will know, that there were no multi byte characters involved.

In that case, what is that doing in that thread…?

But I can tell you my favourite Banana Cake recipe, if that is of interest…

I’m confused. I said earlier in this thread that I needed to do that format conversion. It seems like you missed it when you asked if my test accounted for certain characters. I’m showing you what I needed this string reversal to do and I said how I was assembling my string with the commas earlier in this thread which explains why I needed string reversal. maybe Jules wants to write a function that converts an integer to string and includes commas for the thousands place holders as an addition to the string class…

Calm down, no harm done…

Just people looking at the thread are looking for how to reverse a string. If you want to tell the world, how you reversed your digit number, go ahead… it just doesn’t answer the topic of the thread, so maybe make a new thread?

#include <string>
#include <iostream>
#include <algorithm>
//====================================================
int main()
{
std::string str {"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"};
std::reverse( str.begin(), str.end() );
std::cout << str;
return 0;
}

prints out:

ZYXWVUTSRQPONMLKJIHGFEDCBAzyxwvutsrqponmlkjihgfedcba9876543210

https://coliru.stacked-crooked.com/a/6872bae64f4b3a62

A string of all alpha-numeric characters reversed.

What about my answer doesn’t answer the original topic of how to reverse a string?

Does someone need to mention multibyte characters again?

#include <string>
#include <iostream>
#include <algorithm>
//====================================================
int main()
{
std::string str {"âbčdëfghìjkłmńœpqrßtūvwxÿż"};
std::cout << "Forward : " << str << std::endl;
std::reverse( str.begin(), str.end() );
std::cout << "Backward : " << str << std::endl;
return 0;
}

That does not output the string in the reverse order. Each of the > 127 code points has its bytes reversed, which moves the code points and you end up with:

Forward : âbčdëfghìjkłmńœpqrßtūvwxÿż
Backward : \274ſ\303xwv\253\305t\237\303rqp\223ń\305m\202\305kj\254\303hgf\253\303d\215\304b\242\303

A string is not always ASCII

1 Like