c++ - What is the fastest way to reverse a c-string, in place in c++?

Question

What's the fastest way to reverse a c-string, in place in c++ using only the library? In particular, are there any methods that require less than O(strlen) time?

Answer 1

There cannot possibly be a method to reverse a string of length n in less than O(n) time. By definition of "reversing", every character has to be read at least once.

Answer 2

各キャラクターに少なくとも1回は触れる必要があるため、O（n）時間よりも早くそれを行う方法はありません。

だから次のようなもの：

void reverseString (char *s) {
    char t, *d = &(s[strlen (s) - 1]);
    while (d > s) {
        t = *s;
        *s++ = *d;
        *d-- = t;
    }
}

おそらく、標準のC++で取得するのとほぼ同じくらい効率的です。

アクセスパターンに応じて、コストをO（n）未満に償却できるようになるまで、追加情報を課すことが許可されている場合は、これを改善する方法があります。

つまり、元の文字列と一緒に逆の文字列とダーティフラグを保持することを意味します。

• フラグがダーティのときに反転された文字列にアクセスしようとした場合は、反転を計算し、フラグをクリーンに設定して、計算/保存された反転を返します。コストはO（n）です。
• フラグがクリーンなときに反転された文字列にアクセスしようとした場合は、計算/保存された反転を返すだけです。コストはO（1）です。
• 元の文字列を変更する場合は、フラグをダーティに設定してください。コストはO（1）です。

元の文字列を変更するよりも頻繁に反転文字列にアクセスする場合、コストは単純な「毎回反転文字列を計算する」方法よりも低くなります。

Answer 3

O(N) 未満の複雑さで可能であるとは思えません。C 文字列がどのように定義されているか (NUL で終了) を考えると、O(N) 未満の複雑さで文字列の最後の要素を見つけることさえできないため、より低い複雑さで実際に何かを行うことを想像するのは困難です。

方法に関しては、通常は最初の要素を最後の要素と交換し、2 番目の要素を最後から 2 番目の要素と交換します。

線形よりも高速に処理するには、おそらく文字列の長さを格納することから始める必要があります。次に、実際にそれをまったく逆にする代わりに、(たとえば)フラグを設定して、最後から開始するように指定します。これにより、一定の複雑さの「逆転」が可能になります。これは、ストレージを「保護」し、演算子をオーバーロードして、必要な方向へのアクセスを提供できる C++ で管理するのはかなり簡単です。