¿Girar una cadena en C++?

Question

Estoy buscando una manera de rotar una cadena en C++. Paso todo mi tiempo en Python, entonces mi C++ es muy oxidado.

Esto es lo que quiero que haga: si tengo una cadena 'abcde' quiero que cambie a 'bcdea' (primer carácter movido hasta el final). Aquí es cómo lo hice en Python:

def rotate(s): 
    return s[1:] + s[:1] 

No estoy seguro de cómo hacerlo en el CPP. Tal vez usar una variedad de caracteres?

Answer 1

recomiendo std::rotate:

std::rotate(s.begin(), s.begin() + 1, s.end()); 

Answer 2

Aquí hay una solución que "flota" el primer carácter al final de la cadena, algo así como una única iteración de tipo burbuja.

#include <algorithm> 

string rotate(string s) { 
    for (int i = 1; i < s.size(); i++) 
    swap(s[i-1], s[i]); 
    return s; 
} 

si desea que la función para girar la cadena en el lugar:

#include <algorithm> 

void rotate(string &s) { 
    for (int i = 1; i < s.size(); i++) 
    swap(s[i-1], s[i]); 
} 

Answer 3

Aquí está una manera relativamente simple:

void RotateStringInPlace(char buffer[]) 
{ 
    // Get the length of the string. 

    int len = strlen(buffer); 
    if (len == 0) { 
     return; 
    } 

    // Save the first character, it's going to be overwritten. 

    char tmp = buffer[0]; 

    // Slide the rest of the string over by one position. 

    memmove(&buffer[0], &buffer[1], len - 1); 

    // Put the character we saved from the front of the string in place. 

    buffer[len - 1] = tmp; 
    return; 
} 

Tenga en cuenta que esto va a modificar el búfer en su lugar.

Answer 4

¿Lo está haciendo en su lugar un requisito?

Si no, probablemente sea mejor que tome una subcadena de todas las carátulas excepto la primera, y luego añada la primera carátula hasta el final.

Answer 5

Hay una rotate función estándar que se encuentra en la cabecera del algoritmo.
Si desea hacerlo usted mismo, puede probar lo siguiente:

#include <iostream> 
#include <string> 

std::string rotate_string(std::string s) { 
    char first = s[0]; 

    s.assign(s, 1, s.size() - 1); 
    s.append(1, first); 

    return s; 
} 

int main() { 
    std::string foo("abcde"); 

    std::cout << foo << "\t" << rotate_string(foo) << std::endl; 

    return 0; 
} 

Pero, por supuesto, el uso de la biblioteca estándar es preferible aquí, y en la mayoría de los casos.

EDIT: Acabo de ver la respuesta de litb. ¡Vence otra vez!
EDIT # 2: Solo quiero mencionar que la función rotate_string falla en cadenas de 0 de longitud. Obtendrá un error std :: out_of_range. Puede remediar esto con un simple bloque try/catch, o use std :: rotate :-)

Answer 6

Si no quiere estas soluciones in situ, entonces su código python se puede traducir directamente a C++, con un Un poco de código adicional para lidiar con el hecho de que el índice fuera de límites es una mala noticia en C++.

s[1:] --> s.substr(1); 
s[:1] --> s[0]; // s[0] is a char not a string, but that's good enough 

Así,

std::string rotate(const std::string &s) { 
    if (s.size() > 0) return s.substr(1) + s[0]; 
    return s; 
} 

Este no es el más eficiente: es casi seguro que hacer más creación cadena que el mínimo posible. Pero generalmente no necesita la más eficiente, y tiene reserve y append si desea realizar la concatenación sin asignación innecesaria.

Answer 7

En algún momento yo estaba obsesionado con dividir y conquistar, y se utiliza la siguiente

ya que 'Divide' el problema de los problemas más pequeños mi conjetura es que esto tiene un mejor rendimiento. Comentarios de expertos sobre la complejidad y el comportamiento de acceso a la memoria son bienvenidos :).

Initial Call: 
rotate_about(rots_g, 0, i, j - 2); 


void rotate_about(char *str, int start, int pivot, int end) 
{ 
    if(pivot == start) 
    { 
     return ; 
    } 
    else if((pivot - start) <= (end - pivot)) 
    { 
     int move_bytes = pivot-start; 
     swap_bytes(&str[start], &str[pivot],move_bytes); 
     rotate_about(str,pivot,pivot+move_bytes,end); 
    } 
    else 
    { 
     int move_bytes = end - pivot + 1; 
     swap_bytes(&str[start], &str[pivot],move_bytes); 
     rotate_about(str, start+move_bytes ,pivot,end); 
    } 
} 

Answer 8

Aquí está el código en C que no utiliza ningún funciones externas: Se gira la cadena en el lugar tanto hacia delante y hacia atrás por cualquier valor no importa lo grande.

int stringRotate(int value) 
    { 
    unsigned long I,J,K; 
    unsigned long index0; 
    unsigned long temp1,temp2; 
    unsigned long length; 

    length = stringLength; 

    if (value < 0) 
    value = length - ((0 - value) % length); 

    if (value > length) 
    value = value % length; 

    J = 0; 
    index0 = J; 
    temp1 = stringData[J]; 

    for (I = 0;I < length;I++) 
    { 
    K = (J + value) % length; 
    temp2 = stringData[K]; 
    stringData[K] = temp1; 

    J = K; 

    temp1 = temp2; 

    if (J == index0) 
     { 
     J++; 
     index0 = J; 
     temp1 = stringData[J]; 
     } 
    } 

    return 1; 
    } 

Para girar la cuerda hacia adelante y hacia atrás sería un poco tedioso por lo que es mejor hacer sólo hacia adelante rotar y calcular el valor correcto para backwards.Also si el valor de rotación es mayor que la longitud de la cuerda , entonces podemos simplemente cortarlo ya que el resultado sería el mismo de todos modos.

value = length - ((0 - value)% length): significa que si el valor de rotación es negativo, establezca el valor en la longitud de la cadena, menos el resultado positivo del resto dividiendo el valor por longitud de la cuerda. Por ejemplo: rotar una cuerda de longitud 10 por -9 posiciones sería lo mismo que rotar por +1. Girar la misma cuerda por posiciones -19 también sería lo mismo que rotar por más uno. value = value% length: significa si el valor positivo es mayor que la longitud de la cadena, luego divida por la longitud de la cadena y tome el resto. El resultado sería el mismo que si lo hiciéramos por el camino más largo.

Para hacer la rotación en su lugar, vamos a necesitar saltar por el valor de la rotación para intercambiar caracteres que están muy separados. Comenzamos en la posición cero, avanzamos por el valor de rotación y continuamos saltando en esa cantidad. si pasamos el final de la cadena, simplemente volvemos al principio. El problema es que si el valor es un número par, terminaremos justo donde comenzamos y perderemos todos los caracteres impares. La variable index0 está ahí para indicar de dónde empezamos. Si terminamos de nuevo en este índice, tenemos que avanzar en una posición de índice y seguir saltando. Continuamos haciendo esto hasta que todos los caracteres se intercambien En este punto necesitamos dos variables temporales para realizar el intercambio en su lugar. J es la posición inicial. Movemos el personaje en el índice J a la primera variable temporal. Ahora hacemos un bucle I a la longitud de la cadena. K es el índice de destino, J más el valor de rotación Envuelto alrededor del final si es necesario. Mueva el carácter en el índice K a la segunda variable temporal. Coloque el carácter del índice J en el índice K usando la primera variable temporal. Por cierto, la razón por la que no solo movemos al personaje directamente del índice J al índice K es debido a la última parte del ciclo, los índices pueden cambiar entre bucles, pero los caracteres en temp1 no deberían moverse. Ahora intercambiamos temp1 con temp2. Esta última parte es para donde el valor es un número par y estamos de vuelta donde comenzamos. Esto sucederá por el valor de rotación menos uno. incremente el índice J en uno y restablezca los valores iniciales. Bucle hasta que esté hecho.

Un video de demostración se puede encontrar aquí: https://www.youtube.com/watch?v=TMzaO2WzR24