Как поменять местами строку в C или C++?
Ответы 19
#include <cstdio>
#include <cstdlib>
#include <string>
void strrev(char *str)
{
if ( str == NULL )
return;
char *end_ptr = &str[strlen(str) - 1];
char temp;
while( end_ptr > str )
{
temp = *str;
*str++ = *end_ptr;
*end_ptr-- = temp;
}
}
int main(int argc, char *argv[])
{
char buffer[32];
strcpy(buffer, "testing");
strrev(buffer);
printf("%s\n", buffer);
strcpy(buffer, "a");
strrev(buffer);
printf("%s\n", buffer);
strcpy(buffer, "abc");
strrev(buffer);
printf("%s\n", buffer);
strcpy(buffer, "");
strrev(buffer);
printf("%s\n", buffer);
strrev(NULL);
return 0;
}
Этот код производит такой вывод:
gnitset
a
cba
Если строка пуста, strlen вернет 0, и вы будете индексировать за пределами массива, что недопустимо в C (вы можете адресовать один элемент за концом массива, но не на один элемент раньше).
strcpy совершенно безопасен, если программист может отслеживать размер своих массивов, многие будут утверждать, что strncpy менее безопасен, поскольку он не гарантирует, что результирующая строка будет завершена нулем. В любом случае, здесь нет ничего плохого в том, что uvote использует strcpy.
@Onorio Catenacci, strcpy не опасен, если вы знаете, что исходная строка поместится внутри целевого буфера, как в случаях, указанных в приведенном выше коде. Кроме того, strncpy заполняет нулями до количества символов, указанного в параметре размера, если остается свободное место, что может быть нежелательно.
Я считаю, что strcpy относится к тому же классу потенциально опасных языковых функций, что и перегрузка оператора - это нормально и безопасно, если кто-то знает, как его правильно использовать, но большинство разработчиков не знают, как правильно его использовать. Следовательно, этого следует просто избегать. Я верю своему совету.
Любой, кто не может правильно использовать strcpy, не должен программировать на C.
@ Роберт Гэмбл, я согласен. Однако, поскольку я не знаю способа удержать людей от программирования на C, независимо от их компетенции, я обычно не рекомендую этого делать.
@Robert Gamble: Теперь есть непонятное правило C (индексирование одного перед массивом). Теперь, когда вы упомянули об этом, я это запомнил, и это хороший улов. Но, конечно, это работает в gcc на x86, как показывает мой тест. (и я в порядке с использованием strcpy)
@OnorioCatenacci Мусор. Это совершенно безопасно, если вы следите за вещами. Это черно-белое отношение возникает из-за небезопасного программирования и / или повторения того, что они прочитали / услышали. Это просто неправда. И точно так же, как указывает Роберт, некоторые - в том числе и я - считают strncpy() менее безопасным. Вы не знаете лучшего способа, чем рекомендовать это? Почему бы не рекомендовать вместо этого действительно проверять наличие ошибок и т. д.? Это гораздо ценнее, чем занесение чего-либо в черный список, потому что некоторые люди используют это неправильно.
@Pryftan Я бы сказал, что если SEI считает, что осторожность с strcpy - это хорошо, то я согласен: wiki.sei.cmu.edu/confluence/display/c/…. Strcpy полагается на дисциплину программиста и потенциально полагается на знания, которыми программист может просто не обладать. Есть более безопасная альтернатива - почему бы не использовать ее?
@OnorioCatenacci Может быть, это не всегда безопаснее? Кто-то уже указал на это. Дело в том, что вы можете сделать что угодно небезопасным, если захотите. Но если вы знаете правильный размер, угадайте, что? Вы также можете правильно провести тестирование. Это здравый смысл. Быть осторожным с strcpy, как вы говорите, - это не то же самое, что и ваш предыдущий Не используйте strcpy. Всегда.. Большая разница. Огромная разница. Ваш предыдущий комментарий черно-белый. Быть в безопасности - это не одно и то же. Черно-белое редко бывает хорошей идеей. Жизнь не так проста. strncpy также может создавать незавершенные строки. Небезопасно.
#include <algorithm>
std::reverse(str.begin(), str.end());
Это самый простой способ в C++.
В C++ строка представлена строковым классом. Он не просил «звездочку» или «скобки». Оставайся стильным, С.
@fredsbend, «смехотворно длинная» версия выбранного ответа обрабатывает случай, которого нет в этом простом ответе - ввод UTF-8. Это показывает важность полного определения проблемы. Кроме того, вопрос был о коде, который также будет работать на C.
Этот ответ обрабатывает случай, если вы используете класс строк, поддерживающий UTF-8 (или, возможно, класс символов utf-8 с std :: basic_string). Кроме того, в вопросе говорилось «C или C++», а не «C и C++». Только C++ - это «C или C++».
Это полностью сломает многобайтовые строки UTF-8 и в наши дни полностью не запускается.
Стандартный алгоритм состоит в том, чтобы использовать указатели на начало / конец и обходить их внутрь, пока они не встретятся или не пересекутся посередине. Меняйте местами на ходу.
Обратная строка ASCII, то есть массив с завершающим нулем, в котором каждый символ помещается в 1 char. (Или другие не многобайтовые наборы символов).
void strrev(char *head)
{
if (!head) return;
char *tail = head;
while(*tail) ++tail; // find the 0 terminator, like head+strlen
--tail; // tail points to the last real char
// head still points to the first
for( ; head < tail; ++head, --tail) {
// walk pointers inwards until they meet or cross in the middle
char h = *head, t = *tail;
*head = t; // swapping as we go
*tail = h;
}
}
// test program that reverses its args
#include <stdio.h>
int main(int argc, char **argv)
{
do {
printf("%s ", argv[argc-1]);
strrev(argv[argc-1]);
printf("%s\n", argv[argc-1]);
} while(--argc);
return 0;
}
Тот же алгоритм работает для целочисленных массивов известной длины, просто используйте tail = start + length - 1 вместо цикла поиска конца.
(Примечание редактора: в этом ответе изначально использовался XOR-swap и для этой простой версии. Исправлено в интересах будущих читателей этого популярного вопроса. XOR-swap высоко не рекомендуется; трудно читать, и ваш код компилируется менее эффективно. Вы можете увидеть в обозревателе компилятора Godbolt, насколько больше усложняет тело цикла asm, когда xor-swap компилируется для x86-64 с помощью gcc -O3.)
Хорошо, хорошо, давайте исправим символы UTF-8 ...
(Это XOR-замена. Обратите внимание, что вы меняете должен избегать на self, потому что, если *p и *q находятся в одном месте, вы обнуляете его с помощью ^ a == 0. XOR-замена зависит от наличия двух разных местоположений , используя каждый из них как временное хранилище.)
Примечание редактора: вы можете заменить SWP на безопасную встроенную функцию, используя переменную tmp.
#include <bits/types.h>
#include <stdio.h>
#define SWP(x,y) (x^=y, y^=x, x^=y)
void strrev(char *p)
{
char *q = p;
while(q && *q) ++q; /* find eos */
for(--q; p < q; ++p, --q) SWP(*p, *q);
}
void strrev_utf8(char *p)
{
char *q = p;
strrev(p); /* call base case */
/* Ok, now fix bass-ackwards UTF chars. */
while(q && *q) ++q; /* find eos */
while(p < --q)
switch( (*q & 0xF0) >> 4 ) {
case 0xF: /* U+010000-U+10FFFF: four bytes. */
SWP(*(q-0), *(q-3));
SWP(*(q-1), *(q-2));
q -= 3;
break;
case 0xE: /* U+000800-U+00FFFF: three bytes. */
SWP(*(q-0), *(q-2));
q -= 2;
break;
case 0xC: /* fall-through */
case 0xD: /* U+000080-U+0007FF: two bytes. */
SWP(*(q-0), *(q-1));
q--;
break;
}
}
int main(int argc, char **argv)
{
do {
printf("%s ", argv[argc-1]);
strrev_utf8(argv[argc-1]);
printf("%s\n", argv[argc-1]);
} while(--argc);
return 0;
}
- Почему да, если вход заборчен, то бодро поменяется вне места.
- Полезная ссылка при вандализме в UNICODE: http://www.macchiato.com/unicode/chart/
- Кроме того, UTF-8 более 0x10000 не протестирован (поскольку у меня, похоже, нет для него шрифта, а также терпения использовать шестнадцатеричный редактор)
Примеры:
$ ./strrev Räksmörgås ░▒▓○◔◑◕●
░▒▓○◔◑◕● ●◕◑◔○▓▒░
Räksmörgås sågrömskäR
./strrev verrts/.
Нет веских причин использовать замену XOR вне конкуренции с обфусцированным кодом.
Почему не «* p ^ = * q, * q ^ = * p, * p ^ = * q»?
Я бы сказал, что если вы собираетесь попросить «на месте», не вдаваясь в подробности, это ДОЛЖНО быть предметом xor. Все остальное не на своем месте. Тем не менее, это не имеет никакого отношения к производственному коду где-либо. если у вас даже возникнет искушение использовать его, бросьте разработку прямо сейчас.
Вы думаете, что «на месте» означает «без дополнительной памяти», даже без памяти O (1) для временных файлов? Как насчет места в стеке для str и адреса возврата?
@Bill, это не то, что означает обычное определение «на месте». Алгоритмы на месте май используют дополнительную память. Однако объем этой дополнительной памяти не должен зависеть от ввода - т.е. он должен быть постоянным. Таким образом, замена значений с использованием дополнительного хранилища полностью на месте.
О нет, Раксморгос! Теперь мне нужно пойти к холодильнику и приготовить себе один. :П
Возможно, вы захотите проверить этот вопрос, который я задал конкретно о том, как справиться с этой задачей со строками UTF8 (хотя это не универсальное решение). stackoverflow.com/questions/199260/…
Не голосовать за это, пока не исчезнет своп xor.
Замена XOR выполняется медленнее, чем замена через регистр на современных вышедших из строя процессорах.
Я погуглил "переворот строки на месте" конкретно, чтобы найти реализацию трюка XOR. Ненавистники возненавидят, но я нашел то, что искал, так +1 от меня.
Я провел несколько тестов, и мне кажется, что тест «while (q && * q)» нужно изменить. Это должно быть «while (* q)» или быть заменено отдельным «if (! Q) {return;}» (если намерение состояло в том, чтобы перехватывать указатели NULL). Проблема в случае NULL, следующий оператор for (- q; p <q; ++ p, --q) заставляет q переходить на 0xFFFFFFFFFFFFFFFF (по крайней мере, на 64-битной машине CentOS я был тестирование включено), что приведет к выполнению цикла for (поскольку 0 меньше 0xFFFFFFFFFFFFFFFF, а первый «* p = * p ^ * q;» затем вызовет отмену ссылки на нулевой указатель и отключение ссылка 0xFFFFFFFFFFFFFFFF ...
Ребята, большинство из вас ошибается насчет определения in-place. У него есть строгое определение: алгоритм на месте использует память O (logn). Пример Fox: вы рассматриваете быструю сортировку на месте? Он есть и использует логарифмическую память для хранения данных в стеке рекурсии.
@ sasha.sochka Вы ошибаетесь. На месте означает одно и только одно: память постоянный, а не O (logn). И вы получили это: быстрая сортировка не на месте. Тот, кто утверждает, что это неправ. Фактически, многие (якобы «на месте») реализации быстрой сортировки даже используют O (n) дополнительной памяти в худшем случае (поскольку они не гарантируют логарифмическую глубину рекурсии. Но, как я уже сказал, быстрая сортировка на самом деле не работает). место для начала.
@KonradRudolph, да, я понял. Возможно, некоторое время назад я прочитал эту статью en.wikipedia.org/wiki/In-place_algorithm (раздел «По вычислительной сложности») и забыл, что этот log n применялся там в несколько ином контексте.
@AndersEurenius, не могли бы вы пояснить, зачем использовать while(q && *q) ++q; для поиска eos? Разве это не то же самое, что и while(*q) ++q;, поскольку q никогда не будет 0? Как вы можете быть уверены, что q или * q будут равны 0?
"вы должны избегать подкачки с self, потому что a^a==0" - неверно. a ^ a == 0, но это не проблема, потому что тогда вы будете использовать a ^ (a ^ a), то есть a ^ 0, то есть a. Таким образом, обмен XOR работает, даже если два обмена (есть такое слово) равны.
char *q = p; while(q && *q) ++q; for(--q; p < q; ++p, --q) для обнаружения NULL проблематичен. Для продвижения кода до --q, когда q имеет значение NULL и в лучшем случае это самый большой допустимый указатель, в худшем - это может быть UB. Тогда цикл for() будет повторяться очень долго. Подскажите простой if (q != NULL) { do the rest of code }.
Как интервьюер, я док указывает на использование старого трюка xor-swap. Он менее эффективен на современных процессорах, и любой, кто его использует, потому что он «аккуратный», является нет отличным программистом - возможно, «хорошо», но не «великим».
Вау, каждый раз, когда я думаю, что не могу найти более уродливый код, чем в прошлый раз, я нахожу более уродливый.
@ChrisConway: Да, и как участник и победитель я также могу сказать, что это не собьет многих людей с толку. Там он может найти свое применение, но это тоже не сбивает с толку. Я могу придумать множество способов, которыми это могло бы быть полезно в статье, но в целом это настолько неоригинально, что не имеет отношения к делу. Им нужны более сбалансированные записи. Тем не менее, есть моменты вне конкурса, когда я мог бы рассмотреть это, хотя это тоже очень ограничено - и не в обычном коде.
Что касается while(q && *q) ++q;, почему бы просто не использовать strchr(q, '\0');? Наверное, не имеет значения, но кажется более естественным. Конечно, есть и другие способы. Возможно, вы просто не хотели даже включать string.h.
Не злой C, предполагающий общий случай, когда строка представляет собой массив char с завершающим нулем:
#include <stddef.h>
#include <string.h>
/* PRE: str must be either NULL or a pointer to a
* (possibly empty) null-terminated string. */
void strrev(char *str) {
char temp, *end_ptr;
/* If str is NULL or empty, do nothing */
if ( str == NULL || !(*str) )
return;
end_ptr = str + strlen(str) - 1;
/* Swap the chars */
while( end_ptr > str ) {
temp = *str;
*str = *end_ptr;
*end_ptr = temp;
str++;
end_ptr--;
}
}
Вместо использования цикла while для поиска конечного указателя нельзя использовать что-то вроде end_ptr = str + strlen (str); Я знаю, что это будет практически то же самое, но я нахожу это более ясным.
Справедливо. Я пытался (и у меня не получалось) избежать одной ошибки в ответе @ uvote.
Помимо улучшения производительности потенциал, возможно, с int temp, это решение выглядит лучше всего. +1
@ chux-ReinstateMonica Да. Это прекрасно. Лично я бы удалил () из !(*str).
@ PeterKühne Yes или strchr() ищет '\0'. Я думал об обоих. Не нужна петля.
В интересах полноты следует отметить, что существуют представления строк на различных платформах, в которых количество байтов на символ варьируется зависит от символа. Программисты старой закалки назвали бы это DBCS (двухбайтовый набор символов). Современные программисты чаще сталкиваются с этим в UTF-8 (а также UTF-16 и других). Есть и другие такие кодировки.
В любой из этих схем кодирования с переменной шириной простые алгоритмы, размещенные здесь (зло, не злой или иначе), не будут работать правильно! Фактически, они могут даже привести к тому, что строка станет неразборчивой или даже станет недопустимой в этой схеме кодирования. См. Ответ Хуана Пабло Калифано для некоторых хороших примеров.
std :: reverse () потенциально может работать и в этом случае, если реализация стандартной библиотеки C++ на вашей платформе (в частности, строковые итераторы) должным образом учитывает это.
std :: reverse НЕ принимает это во внимание. Он меняет значение типа value_type на противоположное. В случае std :: string он переворачивает char. Не персонажи.
Скорее скажем, что мы, программисты старой школы, знаем о DBCS, но также знаем о UTF-8: поскольку все мы знаем, что программисты похожи на наркоманов, когда они говорят «Еще одна строчка, и я уйду!» Я уверен, что некоторые программисты в конечном итоге бросают, но, честно говоря, программирование действительно похоже на зависимость для меня ; Я получаю отказ от программирования. Это хороший момент, который вы добавили сюда. Мне не нравится C++ (я действительно очень старался, чтобы он понравился, даже написав немало, но он все еще для меня эстетически непривлекателен, мягко говоря), поэтому я не могу там комментировать, но вы все равно делаете хорошее замечание, так что иметь +1.
Обратите внимание, что прелесть std :: reverse заключается в том, что он работает со строками char * и std::wstring так же хорошо, как с std::string.
void strrev(char *str)
{
if (str == NULL)
return;
std::reverse(str, str + strlen(str));
}
Если вы ищете реверсирование буферов с нулевым завершением, большинство решений, размещенных здесь, подходят. Но, как уже указывал Тим Фарли, эти алгоритмы будут работать только в том случае, если допустимо предположить, что строка семантически представляет собой массив байтов (то есть однобайтовые строки), что, я думаю, является неправильным предположением.
Возьмем, к примеру, строку «año» (год на испанском языке).
Кодовые точки Unicode: 0x61, 0xf1, 0x6f.
Рассмотрим некоторые из наиболее часто используемых кодировок:
Latin1 / iso-8859-1 (однобайтовая кодировка, 1 символ равен 1 байту и наоборот):
Original:
0x61, 0xf1, 0x6f, 0x00
Reverse:
0x6f, 0xf1, 0x61, 0x00
The result is OK
UTF-8:
Original:
0x61, 0xc3, 0xb1, 0x6f, 0x00
Reverse:
0x6f, 0xb1, 0xc3, 0x61, 0x00
The result is gibberish and an illegal UTF-8 sequence
UTF-16 с прямым порядком байтов:
Original:
0x00, 0x61, 0x00, 0xf1, 0x00, 0x6f, 0x00, 0x00
The first byte will be treated as a NUL-terminator. No reversing will take place.
UTF-16 Little Endian:
Original:
0x61, 0x00, 0xf1, 0x00, 0x6f, 0x00, 0x00, 0x00
The second byte will be treated as a NUL-terminator. The result will be 0x61, 0x00, a string containing the 'a' character.
std :: reverse будет работать для двухбайтовых типов Unicode, если вы используете wstring.
Я не очень знаком с C++, но предполагаю, что любая уважаемая стандартная библиотечная функция, работающая со строками, сможет обрабатывать различные кодировки, поэтому я согласен с вами. Под «этими алгоритмами» я имел в виду специальные реверсивные функции, размещенные здесь.
К сожалению, в стандартном C++ нет такой вещи, как «респектабельная функция, работающая со строками».
@Eclipse Если он меняет суррогатную пару, результат больше не будет правильным. Юникод на самом деле не является кодировкой с фиксированной шириной
Что мне нравится в этом ответе, так это то, что он показывает фактический порядок байтов (хотя порядок байтов может быть чем-то вроде - а, я вижу, вы действительно его учли) и то, насколько он правильный или неправильный. Но я думаю, что ответ был бы лучше, если бы вы включили некоторый код, демонстрирующий это.
Прочтите Керниган и Ричи
#include <string.h>
void reverse(char s[])
{
int length = strlen(s) ;
int c, i, j;
for (i = 0, j = length - 1; i < j; i++, j--)
{
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
Проверено на моем iphone, примерно на 15% медленнее, чем при использовании адресов необработанных указателей.
Разве переменная "c" не должна быть char вместо int?
@Lesswire - в C всякий раз, когда символьная константа или переменная используется в выражении в C, она автоматически преобразуется и обрабатывается как целое число. Если у вас есть терминал linux, вы можете увидеть коды ascii, набрав man ascii
В этом примере важно отметить, что строка s должна быть объявлена в виде массива. Другими словами, char s[] = "this is ok", а не char *s = "cannot do this", потому что последний приводит к строковой константе, которую нельзя изменить.
length, i, j должен быть size_t, но тогда возникнут проблемы, когда length == 0.
@PsychoDad Вы включали оптимизацию, когда выполняли тест iPhone для доступа к массиву по сравнению с указателем ??
@brandin Надеюсь, я сделал это в режиме выпуска, но я не помню.
С извинениями перед «Крестным отцом» .... «Оставь оружие, принеси K&R». Как фанат C, я бы использовал указатели, поскольку они проще и понятнее для решения этой проблемы, но код будет менее переносимым на C#, Java и т. д.
Я не понимаю, почему это не принятый ответ. Это самое простое и надежное решение, работающее в пространстве O (1). Он также работает за время O (log (n)), что замечательно.
@Eric Это не выполняется за время O (log (n)). Он выполняется за O (n), если вы имеете в виду количество замен символов, выполняемых кодом, для n длины строки выполняется n замен. Если вы говорите о количестве выполненных циклов, то это все еще O (n) - хотя и O (n / 2), но вы отбрасываете константы в нотации Big O.
@Eric В дополнение к тому, что говорит Стивен, как также говорит user1527227, он требует, чтобы он был в форме массива. Это будет еще одна веская причина, по которой это не принято.
@jjxtra Значит, у вас плохой компилятор
Если вы используете GLib, у него есть две функции для этого: g_strreverse () и g_utf8_strreverse ().
Мне нравится ответ Евгения K&R. Однако приятно видеть версию с использованием указателей. В остальном, по сути, то же самое:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *reverse(char *str) {
if ( str == NULL || !(*str) ) return NULL;
int i, j = strlen(str)-1;
char *sallocd;
sallocd = malloc(sizeof(char) * (j+1));
for(i=0; j>=0; i++, j--) {
*(sallocd+i) = *(str+j);
}
return sallocd;
}
int main(void) {
char *s = "a man a plan a canal panama";
char *sret = reverse(s);
printf("%s\n", reverse(sret));
free(sret);
return 0;
}
Прошло некоторое время, и я не помню, в какой книге меня научили этому алгоритму, но я подумал, что он довольно гениальный и простой для понимания:
char input[] = "moc.wolfrevokcats";
int length = strlen(input);
int last_pos = length-1;
for(int i = 0; i < length/2; i++)
{
char tmp = input[i];
input[i] = input[last_pos - i];
input[last_pos - i] = tmp;
}
printf("%s\n", input);
Визуализация этого алгоритма любезно предоставлена слэшдоттир:
Да, это интересный вариант. Хотя технически это должен быть size_t.
Рекурсивная функция для переворота строки на месте (без дополнительного буфера, malloc).
Короткий, сексуальный код. Плохое, неправильное использование стека.
#include <stdio.h>
/* Store the each value and move to next char going down
* the stack. Assign value to start ptr and increment
* when coming back up the stack (return).
* Neat code, horrible stack usage.
*
* val - value of current pointer.
* s - start pointer
* n - next char pointer in string.
*/
char *reverse_r(char val, char *s, char *n)
{
if (*n)
s = reverse_r(*n, s, n+1);
*s = val;
return s+1;
}
/*
* expect the string to be passed as argv[1]
*/
int main(int argc, char *argv[])
{
char *aString;
if (argc < 2)
{
printf("Usage: RSIP <string>\n");
return 0;
}
aString = argv[1];
printf("String to reverse: %s\n", aString );
reverse_r(*aString, aString, aString+1);
printf("Reversed String: %s\n", aString );
return 0;
}
Это довольно забавное решение, вы должны добавить трассировку, например printf ("% * s> [% d] reverse_r ('% c',% p = \"% s \ ",% p = \"% s \ ") \ n ", глубина," ", глубина, val, s, (s? s:" null "), n, (n? n:" null ")); в начале и <в конце.
Помещение каждого char в стек не считается «на месте». Особенно, когда вы фактически нажимаете 4 * 8B на символ (на 64-битной машине: 3 аргумента + адрес возврата).
Исходный вопрос: «Как вы перевернете строку в C или C++, не требуя отдельного буфера для хранения перевернутой строки?» - не требовалось менять местами. Кроме того, в этом решении с самого начала упоминается неправильное использование стека. Я проиграл голосование из-за плохого понимания прочитанного другими людьми?
Я бы не назвал это «сексуальным», но сказал бы, что это демонстративно и поучительно. Если рекурсия используется правильно, она может быть очень ценной. Однако следует отметить, что - последнее, что я знал - C даже не требует стека как такового; однако он делает рекурсию. В любом случае это пример рекурсии, которая при правильном использовании может быть очень полезной и ценной. Я не думаю, что когда-либо видел, как он использовался для переворота строки.
Еще один:
#include <stdio.h>
#include <strings.h>
int main(int argc, char **argv) {
char *reverse = argv[argc-1];
char *left = reverse;
int length = strlen(reverse);
char *right = reverse+length-1;
char temp;
while(right-left>=1){
temp=*left;
*left=*right;
*right=temp;
++left;
--right;
}
printf("%s\n", reverse);
}
Это демонстрирует арифметику указателей, как и мой ответ, но объединяет ее с Swap. Я считаю, что этот ответ на самом деле многое добавляет. Вы должны быть в состоянии понять этот тип кода, прежде чем добавлять миллиард библиотек в качестве зависимостей, просто чтобы получить простое текстовое поле (что я слишком часто вижу в современных приложениях, с которыми мне приходится работать)
Другой способ C++ (хотя я бы, наверное, сам использовал std :: reverse () :) как более выразительный и быстрый)
str = std::string(str.rbegin(), str.rend());
Способ C (более или менее :)) и, пожалуйста, будьте осторожны с трюком XOR для подкачки, компиляторы иногда не могут это оптимизировать.
В таком случае это обычно намного медленнее.
char* reverse(char* s)
{
char* beg = s, *end = s, tmp;
while (*end) end++;
while (end-- > beg)
{
tmp = *beg;
*beg++ = *end;
*end = tmp;
}
return s;
} // fixed: check history for details, as those are interesting ones
Я бы использовал strlen, чтобы найти конец строки, если он потенциально длинный. Хорошая реализация библиотеки будет использовать векторы SIMD для поиска быстрее, чем 1 байт на итерацию. Но для очень коротких строк while (*++end); будет выполнен до того, как вызов библиотечной функции начнет поиск.
@PeterCordes хорошо, согласен, strlen в любом случае следует использовать для удобства чтения. В любом случае, для более длинной струны вы всегда должны сохранять длину в вариалбе. strlen на SIMD обычно приводится в качестве примера с этим заявлением об отказе от ответственности, это не реальное приложение, или, по крайней мере, это было 5 лет назад, когда был написан код. ;)
Если вы хотите, чтобы это работало быстро на реальных процессорах, вы должны использовать тасование SIMD, чтобы сделать обратное для блоков по 16 Байт. : P например на x86 _mm_shuffle_epi8 (PSHUFB) может изменить порядок вектора 16B, учитывая правый вектор управления тасованием. Вероятно, он может работать почти со скоростью memcpy при некоторой тщательной оптимизации, особенно с AVX2.
char* beg = s-1 имеет неопределенное поведение (по крайней мере, если s указывает на первый элемент массива, что является наиболее распространенным случаем). while (*++end); имеет неопределенное поведение, если s - пустая строка.
@pprzemek Что ж, вы утверждаете, что s-1 определил поведение, даже если s указывает на первый элемент массива, поэтому вы должны иметь возможность ссылаться на стандарт в поддержку.
@pprzemek В вашем коде не используется оператор --. Я никогда ничего не говорил о типах. Арифметика указателя в целом действительна только в том случае, если она перемещает указатель внутри того же массива (или на один элемент за конец). См. Также c-faq.com/aryptr/non0based.html, в котором явно указано, что то, что вы делаете, недопустимо.
@melpomene, вы действительно очень мудры, вы могли бы просто исправить ответ, как рекомендует SO. Тем не менее вы правы, я был неправ. Я удалю свои комментарии со стыдом и смирением, так как они больше не действительны.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
unsigned char * utf8_reverse(const unsigned char *, int);
void assert_true(bool);
int main(void)
{
unsigned char str[] = "mañana mañana";
unsigned char *ret = utf8_reverse(str, strlen((const char *) str) + 1);
printf("%s\n", ret);
assert_true(0 == strncmp((const char *) ret, "anãnam anañam", strlen("anãnam anañam") + 1));
free(ret);
return EXIT_SUCCESS;
}
unsigned char * utf8_reverse(const unsigned char *str, int size)
{
unsigned char *ret = calloc(size, sizeof(unsigned char*));
int ret_size = 0;
int pos = size - 2;
int char_size = 0;
if (str == NULL) {
fprintf(stderr, "failed to allocate memory.\n");
exit(EXIT_FAILURE);
}
while (pos > -1) {
if (str[pos] < 0x80) {
char_size = 1;
} else if (pos > 0 && str[pos - 1] > 0xC1 && str[pos - 1] < 0xE0) {
char_size = 2;
} else if (pos > 1 && str[pos - 2] > 0xDF && str[pos - 2] < 0xF0) {
char_size = 3;
} else if (pos > 2 && str[pos - 3] > 0xEF && str[pos - 3] < 0xF5) {
char_size = 4;
} else {
char_size = 1;
}
pos -= char_size;
memcpy(ret + ret_size, str + pos + 1, char_size);
ret_size += char_size;
}
ret[ret_size] = '\0';
return ret;
}
void assert_true(bool boolean)
{
puts(boolean == true ? "true" : "false");
}
Если вы используете ATL / MFC CString, просто позвоните CString::MakeReverse().
Если хранить его не нужно, можно сократить время, потраченное на это:
void showReverse(char s[], int length)
{
printf("Reversed String without storing is ");
//could use another variable to test for length, keeping length whole.
//assumes contiguous memory
for (; length > 0; length--)
{
printf("%c", *(s+ length-1) );
}
printf("\n");
}
Кажется, я единственный ответ, у которого нет буфера или временной переменной. Я использую длину строки, но другие, которые делают это, добавляют еще одну для головы (против хвоста). Я предполагаю, что стандартная обратная функция хранит переменную через своп или что-то в этом роде. Таким образом, у меня сложилось впечатление, если предположить, что математика указателя и тип UTF совпадают, что это, возможно, единственный ответ, который действительно отвечает на вопрос. Добавленные функции printf () можно убрать, я просто сделал это, чтобы результат выглядел лучше. Я написал это для скорости. Никаких дополнительных выделений или переменных. Наверное, самый быстрый алгоритм отображения обратного str ()
Многобайтовый реверсор C++ UTF-8
Я думаю, вы никогда не можете просто поменять местами концы, вы всегда должны двигаться от начала до конца, перемещаться по строке и искать «сколько байтов потребуется для этого символа?» Я прикрепляю символ, начиная с исходной конечной позиции, и удаляю символ из передней части строки.
void StringReverser(std::string *original)
{
int eos = original->length() - 1;
while (eos > 0) {
char c = (*original)[0];
int characterBytes;
switch( (c & 0xF0) >> 4 ) {
case 0xC:
case 0xD: /* U+000080-U+0007FF: two bytes. */
characterBytes = 2;
break;
case 0xE: /* U+000800-U+00FFFF: three bytes. */
characterBytes = 3;
break;
case 0xF: /* U+010000-U+10FFFF: four bytes. */
characterBytes = 4;
break;
default:
characterBytes = 1;
break;
}
for (int i = 0; i < characterBytes; i++) {
original->insert(eos+i, 1, (*original)[i]);
}
original->erase(0, characterBytes);
eos -= characterBytes;
}
}
void reverseString(vector<char>& s) {
int l = s.size();
char ch ;
int i = 0 ;
int j = l-1;
while(i < j){
s[i] = s[i]^s[j];
s[j] = s[i]^s[j];
s[i] = s[i]^s[j];
i++;
j--;
}
for(char c : s)
cout <<c ;
cout<< endl;
}
@uvote, не используйте strcpy. Всегда. Если вам нужно использовать что-то вроде strcpy, используйте strncpy. strcpy опасен. Между прочим, C и C++ - это два отдельных языка с разными возможностями. Я думаю, вы используете файлы заголовков, доступные только на C++, так что вам действительно нужен ответ на C?