Повернуть строку в C ++?

Question

Я ищу способ поворота строки в C ++. Я провожу все свое время в Python, поэтому мой C ++ очень ржавый.

Вот что я хочу сделать: если у меня есть строка 'abcde', я хочу, чтобы она была заменена на 'bcdea' (первый символ перемещается в конец). Вот как я это сделал в python:

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

Я не уверен, как это сделать в cpp. Может быть, использовать массив символов?

Answer 1

Я рекомендую std::rotate:

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

Answer 2

Вот решение, которое «плавает» от первого символа до конца строки, вроде как одна итерация сортировки пузырьков.

#include <algorithm>

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

если вы хотите, чтобы функция вращала строку на месте:

#include <algorithm>

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

Answer 3

В заголовке алгоритма найдена стандартная функция rotate .
Если вы хотите сделать это самостоятельно, вы можете попробовать следующее:

#include <iostream>
#include <string>

std::string rotate_string( std::string s ) {
    if (s.empty()) return 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;
}

Но, конечно, здесь предпочтительнее использовать стандартную библиотеку, и в большинстве случаев.

РЕДАКТИРОВАТЬ # 1 Я только что видел ответ Литба. Удар снова!
EDIT # 2 Я просто хочу упомянуть, что функция rotate_string завершается ошибкой для строк длиной 0. Вы получите ошибку std :: out_of_range. Вы можете исправить это с помощью простого блока try / catch или использовать std :: rotate: -)
EDIT # 3 Вернуть ту же строку, если длина строки равна 0.

Answer 4

Вот относительно простой способ:

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;
}

Обратите внимание, что это изменит буфер на месте.

Answer 5

Вот код на C, который не использует никаких внешних функций: Он вращает строку на месте как вперед, так и назад на любое значение независимо от его размера.

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;
  }

Вращать строку как вперед, так и назад было бы немного утомительно, поэтому лучше делать только вращение вперед и вычислять правильное значение для назад. Также, если значение вращения больше длины строки, тогда мы можем просто обрежьте его, так как результат все равно будет таким же.

value = length - ((0 - value)% length): означает, что если значение поворота является отрицательным, тогда установите значение равным длине строки минус положительный результат от остатка от деления значения на длину строки. Например: поворот строки длиной 10 на -9 позиций будет таким же, как поворот на +1. Вращение одной и той же струны на -19 позиций также будет равно вращению на плюс один. значение = значение% длины: означает, что если положительное значение больше длины строки, то разделите на длину строки и возьмите остаток. Результат был бы таким же, как если бы мы просто проделали долгий путь.

Чтобы сделать вращение на месте, нам нужно будет перейти по значению вращения, чтобы поменять местами символы, которые находятся так далеко друг от друга. Мы начинаем с нулевой позиции, продвигаемся вперед на величину вращения и продолжаем прыгать на эту величину. если мы пройдем через конец строки, мы просто вернемся к началу. Проблема в том, что если значение является четным числом, мы окажемся там, где мы начали, и пропустим все нечетные символы. Переменная index0 там, чтобы указать, откуда мы начали. Если мы вернемся к этому индексу, то нам нужно продвинуться на одну позицию индекса и продолжить прыжок. Мы продолжаем делать это, пока все персонажи не поменяются местами На данный момент нам нужны две временные переменные, чтобы выполнить замену на месте. J - начальная позиция. Мы перемещаем символ с индексом J к первой временной переменной. Теперь мы зациклились на длине строки. K - индекс назначения, J плюс значение поворота, завернутое вокруг конца, если необходимо. Переместите символ с индексом K во вторую временную переменную. Поместите символ из индекса J в индекс K, используя первую временную переменную. Кстати, причина, по которой мы не просто перемещаем символ непосредственно из индекса J в индекс K, заключается в том, что из-за последней части цикла индексы могут меняться между циклами, но символы в temp1 не должны. Теперь мы обмениваем temp1 с temp2. Эта последняя часть для того, где значение является четным числом, и мы вернулись к тому, с чего начали. Это будет происходить в разы, значение вращения минус один. увеличить индекс J на ​​единицу и сбросить начальные значения. Цикл до конца.

Видеозапись можно посмотреть здесь: https://www.youtube.com/watch?v=TMzaO2WzR24

Answer 6

В какой-то момент я был одержим идеей «разделяй и властвуй» и использовал следующее

, поскольку это «делит» проблему на более мелкие проблемы, я думаю, что это работает лучше. Комментарии экспертов по сложности и поведению доступа к памяти приветствуются:).

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 7

Если вам не нужны эти решения на месте, тогда ваш код на python может быть напрямую переведен на C ++ с небольшим количеством дополнительного кода, чтобы справиться с тем фактом, что индексирование за пределами границ - это плохая новость в C ++. *

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

Итак,

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

Это не самый эффективный метод: он почти наверняка создаст больше строк, чем это возможно. Но обычно вам не требуется самый эффективный способ, и у вас есть reserve и append, если вы хотите выполнить конкатенацию без ненужного выделения.

Answer 8

Требуется ли сделать это на месте?

Если нет, то вам, вероятно, лучше всего взять подстроку всего, кроме первого символа, а затем добавить первый символ в конец.