Как выполнить инверсию отдельных слов в объекте класса std::string

Форум » C/C++ для начинающих (C/C++ for beginners) » Как выполнить инверсию отдельных слов в объекте класса std::string » Ответить

Как выполнить инверсию отдельных слов в объекте класса std::string

Сыроежка: Для начала следует определить, что является словом в объекте класса std::string. Будем считать словом набор символов, ограниченных символом пробела - ' ' и символом табуляции - '\t'. Например, в следующем объекте s класса std::string, определенным как [pre2] std::string s( "one two three" ); [/pre2] имеется три слова: "one", "two" и "three". Нужно изменить строку таким образом, чтобы она имела вид "eno owt eerht". Ниже представлена демонстрационная программа, которая показывает соответствующую функцию, выполняющую требуемую задачу: [pre2] #include <iostream> #include <iomanip> #include <string> #include <algorithm> #include <iterator> std::string & reverse_words( std::string &s ) { const char *blank = " \t"; for ( std::string::size_type last = 0, first = s.find_first_not_of( blank, last ); first != std::string::npos; first = s.find_first_not_of( blank, last ) ) { last = s.find_first_of( blank, first ); if ( last == std::string::npos ) last = s.size(); std::reverse(std::next( std::begin( s ), first ), std::next( std::begin( s ), last ) ); } return s; } int main() { std::string s( "one two three" ); std::cout << std::quoted( s ) << '\n'; std::cout << std::quoted( reverse_words( s ) ) << '\n'; } [/pre2] Вывод программы на консоль: [pre2] "one two three" "eno owt eerht"[/pre2] Из результирующей строки, которую построила функция, легко получить строку вида "three two one". Для этого достаточно применить стандартный алгоритм std::reverse к результирующей строке. Например, [pre2] #include <iostream> #include <iomanip> #include <string> #include <algorithm> #include <iterator> std::string & reverse_words( std::string &s ) { const char *blank = " \t"; for ( std::string::size_type last = 0, first = s.find_first_not_of( blank, last ); first != std::string::npos; first = s.find_first_not_of( blank, last ) ) { last = s.find_first_of( blank, first ); if ( last == std::string::npos ) last = s.size(); std::reverse(std::next( std::begin( s ), first ), std::next( std::begin( s ), last ) ); } return s; } int main() { std::string s( "one two three" ); std::cout << std::quoted( s ) << '\n'; std::cout << std::quoted( reverse_words( s ) ) << '\n'; std::reverse( std::begin( s ), std::end( s ) ); std::cout << std::quoted( s ) << '\n'; } [/pre2] Вывод программы на консоль: [pre2] "one two three" "eno owt eerht" "three two one"[/pre2] Если в строке имеются ведущие и "хвостовые" пробелы, то чтобы сохранить их положение в строке неизменным, для этого достаточно заменить в предложение [pre2] std::reverse( std::begin( s ), std::end( s ) );[/pre2] начальный и конечный итераторы, которые будут указывать на первый не пробельный символ и последний пробельный символ в строке. Например, [pre2] #include <iostream> #include <iomanip> #include <string> #include <algorithm> #include <iterator> std::string & reverse_words( std::string &s ) { const char *blank = " \t"; for ( std::string::size_type last = 0, first = s.find_first_not_of( blank, last ); first != std::string::npos; first = s.find_first_not_of( blank, last ) ) { last = s.find_first_of( blank, first ); if ( last == std::string::npos ) last = s.size(); std::reverse(std::next( std::begin( s ), first ), std::next( std::begin( s ), last ) ); } return s; } int main() { std::string s( "\tone\ttwo\tthree " ); std::cout << std::quoted( s ) << '\n'; std::cout << std::quoted( reverse_words( s ) ) << '\n'; const char *blank = " \t"; auto first = std::next( std::begin( s ), s.find_first_not_of( blank ) ); auto last = std::next( std::begin( s ), s.find_last_not_of( blank ) + 1 ); std::reverse( first, last ); std::cout << std::quoted( s ) << '\n'; } [/pre2] Вывод программы на консоль: [pre2] " one two three " " eno owt eerht " " three two one "[/pre2] Функцию можно сделать более обобщенной, вынеся ограничители слов из тела функции в список параметров. Например, [pre2] #include <iostream> #include <iomanip> #include <string> #include <string_view> #include <iterator> #include <algorithm> std::string & reverse_words( std::string &s, const std::string_view &delimeter = " \t" ) { for ( std::string::size_type last = 0, first = s.find_first_not_of( delimeter, last ); first != std::string::npos; first = s.find_first_not_of( delimeter, last ) ) { last = s.find_first_of( delimeter, first ); if ( last == std::string::npos ) last = s.size(); std::reverse(std::next( std::begin( s ), first ), std::next( std::begin( s ), last ) ); } return s; } int main() { std::string s( "\tone\ttwo\tthree " ); std::cout << std::quoted( s ) << '\n'; std::cout << std::quoted( reverse_words( s ) ) << '\n'; const char *blank = " \t"; auto first = std::next( std::begin( s ), s.find_first_not_of( blank ) ); auto last = std::next( std::begin( s ), s.find_last_not_of( blank ) + 1 ); std::reverse( first, last ); std::cout << std::quoted( s ) << '\n'; } [/pre2] Вывод программы на консоль будет таким же, как и при запуске предыдущей демонстрационной программы [pre2] " one two three " " eno owt eerht " " three two one " [/pre2]

Ответов - 6

Сыроежка: Данную тему я создал в виду обсуждения вопроса Зачем просят перевернуть строку на интервью? на форуме RSDN в разделе "О работе". Вот это сообщение и сколько времени можно на это потратить у доски? Условие было такое: строка «один два три». Написать функцию на доске, чтобы поменять порядок символов внутри этой строки, не выделяя новой памяти (кроме временных переменных). Принимается ли решение через 15 минут? Изначально я воспринял задание в исходном сообщении темы как требование выполнить инверсию отдельных слов в строке в программе на C++. Почему на C++? Потому что автор темы последнее время создает темы про C++ из-за своего желания перейти в своей профессии на программирование на этом языке. Однако, как оказалось, задание на самом деле значительно проще. Нужно написать функцию, которая выполняет инверсию обычной символьной C-строки. Сначала я покажу возможные решения этого задания. Во-первых, сразу же отмечу, что лучше всего эту функцию писать как C-функцию, так как очень часто в проектах на C++ используется и C-код, в котором такая функция может пригодиться. То есть написав такую функцию на C вы значительно расширяете ее область применения. При этом никаких побочных нежелательных эффектов для кода на C++ эта функция иметь не будет. Например, функцию можно реализовать следующим образом, как это показано в демонстрационной программе, написанной на C. [pre2] #include <stdio.h> #include <string.h> char * str_reverse( char *s ) { for ( size_t i = 0, n = strlen( s ); i < n / 2; i++ ) { char c = s[ i ]; s = s[ n - i - 1]; s[ n - i - 1 ] = c; } return s; } int main( void ) { char s[] = "Hello World!"; puts( s ); puts( str_reverse( s ) ); } [/pre2] Вывод программы на консоль: [pre2] Hello World! !dlroW olleH[/pre2] Отметим важные моменты реализации этой функции. Во-первых, такой функции следует возвращать указатель на исходную строку. Это следует общему соглашению стандартных строковых C-функций. Во-вторых, в функции не должно быть проверки на то, что переданный указатель не является равным NULL. Это также вытекает из соглашения о строковых функциях в C. Эта функция - функция низкого уровня, и она не должна делать лишних проверок. Это задача клиента - обеспечить передачу в функцию в качестве аргумента указателя не равного NULL. Если пользователь передаст указатель равный NULL, то функция будет иметь неопределенное поведение. Такая реализация функции делает общим подход к использованию строковых функций в C низкого уровня и дисциплинирует программистов. То есть поведение функции в точности соответствует поведению других стандартных строковых C-функций низкого уровня. Как известно, оператор индексации, то есть выражение E1[E2], определяется следующим образом как выражение (*((E1)+(E2))). Поэтому вместо использования оператора индексирования в функции ее можно переписать с использованием указателей. Например, [pre2] #include <stdio.h> #include <string.h> char * str_reverse( char *s ) { size_t n = strlen( s ); if ( !( n < 2 ) ) { for ( char *first = s, *last = s + n; first < --last; ++first ) { char c = *first; *first = *last; *last = c; } } return s; } int main( void ) { char s[] = "Hello World!"; puts( s ); puts( str_reverse( s ) ); } [/pre2] Вывод программы будет аналогичен, показанному выше: [pre2] Hello World! !dlroW olleH [/pre2] А теперь рассмотрим те ошибки, которые допускали программисты в обсуждении этой темы. Вот, к примеру в сообщении этой темы от CreatorCray предлагаются такие решения Первое [pre2] #include <algorithm> void revert(char* first, char* last) { while ((first != last) && (first != --last)) { std::iter_swap (first++, last); } }[/pre2] Сразу же заметим, что для строковых функций следует возвращать указатель на результирующую строку. как было сказано выше, потому что это, фактически, C-функция низкого уровня. Второе. Указатели являются итераторами произвольного доступа, а потому условие цикла (first != last) && (first != --last) явно перегружено. Этот фрагмент кода с циклом можно было бы переписать следующим образом [pre2] if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } [/pre2] То есть проверка условия first != last делается только один раз перед циклом. И для большей читаемости кода лучше заменить цикл while на цикл for. Второе решение от CreatorCray выглядит следующим образом #include <stddef.h> [pre2] void revert(char* s, size_t n) { for (auto i=0; i<n/2; i++) { auto c = s; s = s[n-1-i]; s[n-1-i] = c; } } [/pre2] Данная функция вообще имеет неопределенное поведение, так как тип переменной i является int. А так как ранг типа int очевидно меньше ранга типа size_t, то объект типа int может в общем случае не содержать все значения объекта типа size_t. В результате, например, можно получить бесконечный цикл. То есть левый операнд в выражении i<n/2 может быть всегда меньше правого операнда. Вот еще пример реализации от AleksandrN [pre2] void reverse( char *s ) { if ( !s ) return; char *e = s + strlen( s ) - 1; while ( s < e ) { *e ^= *s; *s ^= *e; *e-- ^= *s++; } }[/pre2] Еще раз обращу внимание на то, что функция должна возвращать указатель на результирующую строку, а не иметь тип возврата void, а также не должна делать проверку аргумента на равенство NULL.. Кстати сказать, замечу, что даже POSIX функция strdup не делает такой проверки, хотя было бы вполне логично возвращать NULL, если функции был передан в качестве аргумента null-указатель. Но даже если игнорировать эти замечания, тем не менее функция имеет неопределенное поведение. Пользователь функции может передать в качестве аргумента пустую строку. В этом случае объявление char *e = s + strlen( s ) - 1; эквивалентно объявлению char *e = s - 1;, в результате чего значение указателя e имеет не действительное значение, так как нельзя выходить за пределы начала массива.. Подытоживая, хочу сказать следующее. Если в организации таким образом проводят интервью, то те, кто ответственен за набор новых сотрудников, является некомпетентными. На собеседование, если вам требуются квалифицированные программисты, следует приглашать тех, о квалификации которых у вас уже имеется твердое мнение. Квалифицированный программист - это публичный человек. Его можно найти, например, на специализированных форумах, например, на форуме по обсуждению C++ стандарта, или на таком форуме, как Stackoverflow, и посмотреть его сообщения, статьи, его репутацию и его ответы, чтобы достаточно полно сложилось мнение о нем, как о программисте. После этого и следует приглашать на собеседование, а не на экзамен. А когда приглашают человека с улицы, не имея о его квалификации никакого представления, то чаще всего это выливается в пустую трату времени как тех, кто проводит интервью, так и тех кто проходит такое интервью. Обычно такие организации, которые таким образом проводят интервью, так как они не компетентны, то ориентируются на написанное в резюме. Как говорится, без бумажки ты - букашка, а с бумажкой человек. Это известный факт, что чем ниже квалификация, тем больше требуется какой-нибудь документ, которому можно доверять, так как сам интервьирующий не в состоянии самостоятельно оценить квалификацию. Именно поэтому и даются тестовые задания подобного рода, как в указанной теме по ссылке. А чем менее квалифицированный программист, тем он больше старается красочно расписать свое резюме. А на деле оказывается, что такой программист не умеет писать простой код. С другой стороны, забавно, как данное простое тестовое задание вызвало бурю эмоций и определенные сложности у участников форума. Кстати сказать, в продолжение этой темы для расширения кругозора, думаю, будет интересно ознакомиться с моим предложением по изменению стандарта C++ относительно алгоритма reverse. Смотрите тему "Предложение по включению в стандарт C++ новых обобщенных функций std::reverse и std::sort" по ссылке Предложение по включению в стандарт C++ новых обобщенных функций std::reverse и std::sort

Сыроежка: Практически, почти одновременно встретил аналогичный вопрос начинающего программиста относительно написания функции инверсии символьной C-строки на сайте Stackoverflow Error in checking if pointer reaches end-of-string. Похоже, что автору вопроса требуется написать такую функцию без использования других стандартных строковых функций таких, как функция strlen. Вот реализация функции, представленная автором вопроса в его исходном вопросе: [pre2] void reverse(char* p){ char* start = p; char* end = p; char tmp; int length =0; while(*end!='\0'){ end+=1; length+=1; } printf("%c\n",*end); // problem line int c; for (c = 0; c < length/2; c++) { tmp = *start; *start = *end; *end = tmp; start++; end--; } //printf("%s\n",p); }[/pre2] Как уже неоднократно говорилось мною ранее в этой теме такой функции следует возвращать указатель на результирующую строку. Другое замечание относительно реализации функции состоит в том. как все начинающие программисты, он использует в теле функции совершенно излишнюю переменную length для хранения длины строки.Если уже имеются в распоряжении указатели на начало и конец строки, то этого вполне достаточно для перестановки символов строки. Очевидно, что реализация функции содержит к тому же баг, так как необходимо декрементировать указатель end перед перестановкой символов в строке, так как изначально он указывает на завершающий ноль строки. Но прежде, чем это делать, нужно убедиться, что строка не пустая. Вот как может выглядеть реализация этой функции без использования стандартной функции strlen. [pre2] #include <stdio.h> char * str_reverse( char *s ) { char *first = s, *last = s; while ( *last ) ++last; if ( first != last ) { for ( ; first < --last; ++first ) { char c = *first; *first = *last; *last = c; } } return s; } int main(void ) { char s[] = "Hello World!"; puts( s ); puts( str_reverse( s ) ); } [/pre2] Вывод программы на консоль: [pre2] Hello World! !dlroW olleH [/pre2]

Сыроежка: Возвращаясь к стандартному алгоритму std::reverse в С++, который использовали многие в вышеуказанной теме "Зачем просят перевернуть строку на интервью?" вместо того, чтобы написать C-функцию, как мною было показано, хотел бы отметить, что этот алгоритм специализирован как для двусторонних итераторов, так и для итераторов произвольного доступа. Классический способ выполнить такую специализацию заключается в вызове в общей шаблонной функции std::reverse соответствующей специализации, которая имеет третий дополнительный параметр типа std::bidirectional_iterator_tag или std::random_access_iterator_tag в зависимости от того, какую специализацию функции следует вызвать. Ниже представлена демонстрационная программа, которая показывает, как реализовать такой подход. [pre2] #include <iostream> #include <iterator> #include <list> #include <vector> template <typename Iterator> void reverse( Iterator first, Iterator last, std::bidirectional_iterator_tag ) { std::cout << "reverse with a bidirectional iterator is called\n"; for ( ; first != last && first != --last; ++first ) { std::iter_swap( first, last ); } } template <typename Iterator> void reverse( Iterator first, Iterator last, std::random_access_iterator_tag ) { std::cout << "reverse with a random access iterator is called\n"; if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } } template <typename Iterator> void reverse( Iterator first, Iterator last ) { reverse( first, last, typename std::iterator_traits<Iterator>::iterator_category() ); } int main() { std::list<int> lst = { 1, 2, 3, 4, 5 }; std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( lst ), std::end( lst ) ); std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; std::vector<int> v = { 1, 2, 3, 4, 5 }; std::cout << "\nstd::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( v ), std::end( v ) ); std::cout << "std::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; } [/pre2] Вывод программы на консоль: [pre2] std::list<int>: 1 2 3 4 5 reverse with a bidirectional iterator is called std::list<int>: 5 4 3 2 1 std::vector<int>: 1 2 3 4 5 reverse with a random access iterator is called std::vector<int>: 5 4 3 2 1 [/pre2] То же самое можно проделать с функцией std::reverse, но уже используя ограничения на шаблонные параметры, появившиеся в C++17. Вот как будет выглядеть демонстрационная программа в этом случае. [pre2] #include <iostream> #include <type_traits> #include <iterator> #include <list> #include <vector> template <typename Iterator> requires std::is_base_of_v<std::bidirectional_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category> && std::is_base_of_v<typename std::iterator_traits<Iterator>::iterator_category, std::bidirectional_iterator_tag> void reverse( Iterator first, Iterator last ) { std::cout << "reverse with a bidirectional iterator is called\n"; for ( ; first != last && first != --last; ++first ) { std::iter_swap( first, last ); } } template <typename Iterator> requires std::is_base_of_v<std::random_access_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category> && std::is_base_of_v<typename std::iterator_traits<Iterator>::iterator_category, std::random_access_iterator_tag> void reverse( Iterator first, Iterator last ) { std::cout << "reverse with a random access iterator is called\n"; if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } } int main() { std::list<int> lst = { 1, 2, 3, 4, 5 }; std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( lst ), std::end( lst ) ); std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; std::vector<int> v = { 1, 2, 3, 4, 5 }; std::cout << "\nstd::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( v ), std::end( v ) ); std::cout << "std::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; } [/pre2] Вывод программы аналогичен выводу, показанному выше: [pre2] std::list<int>: 1 2 3 4 5 reverse with a bidirectional iterator is called std::list<int>: 5 4 3 2 1 std::vector<int>: 1 2 3 4 5 reverse with a random access iterator is called std::vector<int>: 5 4 3 2 1 [/pre2] В этом случае достаточно объявить лишь две функции вместо трех, как это было в предыдущем примере. Условие требований на шаблонный аргумент алгоритма std::reverse можно записать проще, используя структуру std::is_same, объявленную в заголовке <type_traits>, как это показано в нижеследующей демонстрационной программе. [pre2] #include <iostream> #include <type_traits> #include <iterator> #include <list> #include <vector> template <typename Iterator> requires std::is_same_v<std::bidirectional_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category> void reverse( Iterator first, Iterator last ) { std::cout << "reverse with a bidirectional iterator is called\n"; for ( ; first != last && first != --last; ++first ) { std::iter_swap( first, last ); } } template <typename Iterator> requires std::is_same_v<std::random_access_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category> void reverse( Iterator first, Iterator last ) { std::cout << "reverse with a random access iterator is called\n"; if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } } int main() { std::list<int> lst = { 1, 2, 3, 4, 5 }; std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( lst ), std::end( lst ) ); std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; std::vector<int> v = { 1, 2, 3, 4, 5 }; std::cout << "\nstd::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( v ), std::end( v ) ); std::cout << "std::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; } [/pre2] Вывод программы на консоль: [pre2] std::list<int>: 1 2 3 4 5 reverse with a bidirectional iterator is called std::list<int>: 5 4 3 2 1 std::vector<int>: 1 2 3 4 5 reverse with a random access iterator is called std::vector<int>: 5 4 3 2 1[/pre2] Данные программы можно протестировать с помощью он-лайнового компилятора по адресу https://wandbox.org. Следует не забыть указать опцию компилятора -fconcepts.

Сыроежка: Вообще говоря, в настоящее время имеется три подхода по определению алгоритма std::reverse. (Если вы знаете еще один способ, то обнародуйте его в этой теме:)). Первый подход - это классический подход с использованием перегруженных функций, как уже было показано в предыдущем сообщении. [pre2] #include <iostream> #include <iterator> #include <list> #include <vector> template <typename Iterator> void reverse( Iterator first, Iterator last, std::bidirectional_iterator_tag ) { std::cout << "reverse with a bidirectional iterator is called\n"; for ( ; first != last && first != --last; ++first ) { std::iter_swap( first, last ); } } template <typename Iterator> void reverse( Iterator first, Iterator last, std::random_access_iterator_tag ) { std::cout << "reverse with a random access iterator is called\n"; if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } } template <typename Iterator> void reverse( Iterator first, Iterator last ) { reverse( first, last, typename std::iterator_traits<Iterator>::iterator_category() ); } int main() { std::list<int> lst = { 1, 2, 3, 4, 5 }; std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( lst ), std::end( lst ) ); std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; std::vector<int> v = { 1, 2, 3, 4, 5 }; std::cout << "\nstd::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( v ), std::end( v ) ); std::cout << "std::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; } [/pre2] Второй подход состоит в использовании ограничений (или требований) на шаблонные аргументы. [pre2] #include <iostream> #include <type_traits> #include <iterator> #include <list> #include <vector> template <typename Iterator> requires std::is_same_v<std::bidirectional_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category> void reverse( Iterator first, Iterator last ) { std::cout << "reverse with a bidirectional iterator is called\n"; for ( ; first != last && first != --last; ++first ) { std::iter_swap( first, last ); } } template <typename Iterator> requires std::is_same_v<std::random_access_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category> void reverse( Iterator first, Iterator last ) { std::cout << "reverse with a random access iterator is called\n"; if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } } int main() { std::list<int> lst = { 1, 2, 3, 4, 5 }; std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( lst ), std::end( lst ) ); std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; std::vector<int> v = { 1, 2, 3, 4, 5 }; std::cout << "\nstd::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( v ), std::end( v ) ); std::cout << "std::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; } [/pre2] И, наконец, третий подход состоит в использовании требований на шаблонные аргументы, а также предложения if с constexpr условием. [pre2] #include <iostream> #include <type_traits> #include <iterator> #include <list> #include <vector> template <typename BidirectionalIterator> requires std::is_base_of_v<std::bidirectional_iterator_tag, typename std::iterator_traits<BidirectionalIterator>::iterator_category> void reverse( BidirectionalIterator first, BidirectionalIterator last ) { if constexpr( std::is_same_v<std::random_access_iterator_tag, typename std::iterator_traits<BidirectionalIterator>::iterator_category> ) { std::cout << "reverse with a random access iterator is called\n"; if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } } else { std::cout << "reverse with a bidirectional iterator is called\n"; for ( ; first != last && first != --last; ++first ) { std::iter_swap( first, last ); } } } int main() { std::list<int> lst = { 1, 2, 3, 4, 5 }; std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( lst ), std::end( lst ) ); std::cout << "std::list<int>: "; for ( int x : lst ) std::cout << x << ' '; std::cout << '\n'; std::vector<int> v = { 1, 2, 3, 4, 5 }; std::cout << "\nstd::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; reverse( std::begin( v ), std::end( v ) ); std::cout << "std::vector<int>: "; for ( int x : v ) std::cout << x << ' '; std::cout << '\n'; } [/pre2] Как видно из приведенных демонстрационных программ, при первом подходе требуется написать три перегруженные функции. При втором подходе - две перегруженные функции, а при третьем подходе достаточно написать лишь одну функцию.:)

Сыроежка: Вот еще один аналогичный вопрос на Stackoverflow относительно инверсии отдельных слов в символьном массиве. На этот раз требуется выполнить задачу на языке программирования C Reverse a string without strtok in C Ниже представлена демонстрационная программа, в которой показано, как можно выполнить поставленную задачу. [pre2] #include <stdio.h> #include <string.h> static char * reverse( char *s, size_t n ) { for ( size_t i = 0; i < n / 2; i++ ) { char c = s[ i ]; s[ i ] = s[ n - i - 1 ]; s[ n - i - 1 ] = c; } return s; } char * reverse_by_words( char *s ) { const char *delim = " \t"; char *p = s; while ( *p ) { p += strspn( p, delim ); if ( *p ) { char *q = p; p += strcspn( p, delim ); reverse( q, p - q ); } } return reverse( s, p - s ); } int main(void) { char s[] = "5 60 +"; puts( s ); puts( reverse_by_words( s ) ); return 0; }[/pre2] Вывод программы на консоль: [pre2] 5 60 + + 60 5[/pre2] Если нужно сохранить ведущие и замыкающие пробелы в строке в том виде, как они присутствуют в исходной строке, то это можно сделать следующим образом.,как показано в демонстрационной программе ниже. [pre2] #include <stdio.h> #include <string.h> static char *reverse( char *s, size_t n ) { for ( size_t i = 0; i < n / 2; i++ ) { char c = s; s = s[n - i -1 ]; s[n - i - 1] = c; } return s; } char * reverse_by_words( char *s ) { const char *delim = " \t"; char *first = s, *last = s; for ( char *p = s; *p; ) { p += strspn( p, delim ); if ( last == s ) first = last = p; if ( *p ) { char *q = p; p += strcspn( p, delim ); last = p; reverse( q, p - q ); } } reverse( first, last - first ); return s; } int main(void) { char s[] = "\t\t\t5 60 +"; printf( "\"%s\"\n", s ); printf( "\"%s\"\n", reverse_by_words( s ) ); return 0; } [/pre2] Вывод программы на консоль: [pre2] " 5 60 +" " + 60 5"[/pre2]

Сыроежка: Похоже, российским программистам не под силу справиться с этой простой задачей: перевернуть (реверсировать) строку и каждое отдельное слово в ней. Вот еще одна такая попытка российского программиста, которая попалась мне на глаза на сайте Stackoverflow ambiguous call to function template (reverse) Чтобы разговор был предметный, приведу представленный в вопросе код. [pre2]#include <string> template <typename Iter> void reverse(Iter begin, Iter end){ if (std::distance(begin, end) == 0) return; auto left = begin, right = std::prev(end); while (left < right) std::swap(*left++, *right--); } std::string reverseWordsInString(std::string str) { reverse(str.begin(), str.end()); // ambiguous call // reverse(str.data(), str.data() + str.size()); size_t wordLength = 0; for (size_t i = 0; i < str.size(); ++i) { if (str != ' ') { ++wordLength; continue; } const size_t offset = i - wordLength; reverse(str.data() + offset, str.data() + i); wordLength = 0; } // reverse(std::prev(str.end(), wordLength), str.end()); // ambiguous reverse(str.data() + str.size() - wordLength, str.data() + str.size()); return str; } [/pre2] Причиной появления вопроса явился неоднозначный вызов функции с именем reverse. Как известно, имеется стандартный алгоритм std::reverse, объявленный в заголовке <algorithm> Стандарт C++ указывает, какие стандартные заголовки обязаны быть включены в другие стандартные заголовки. Реализациям библиотек разрешается включать и другие стандартные заголовки в стандартные заголовки помимо обязательных заголовков. В данном случае ошибка неоднозначного вызова функции с именем reverse послужило то, что в отличии от компилятора gcc компилятор C++ Microsoft, похоже, каким-то образом через цепочку включаемых заголовков опосредованно включает заголовок <algorithm> в заголовок <string>, или, по крайней мере, объявляет алгоритм reverse. Так как используется не квалифицированный поиск имен, то происходит неоднозначность между пользовательской функцией reverse и стандартным алгоритмом std::reverse. Для разрешения проблемы достаточно использовать квалифицированные имена. Но рассмотрим предложенное решение. Во-первых, функция reverseWordsInString объявлена некорректно. [pre2]std::string reverseWordsInString(std::string str) [/pre2] Что я имею в виду? Строка передается в функцию по значению. Это значит, что функция в таком виде неэффективна. Будет происходить полное копирование исходной строки, используемой в качестве аргумента. Имеется два варианта. Либо функция изменяет исходную строку, переданную ей в качестве аргумента, и тогда функцию следует объявить как [pre2]std::string & reverseWordsInString(std::string &str) [/pre2] Либо функция строит новую строку на основе переданной строки, и тогда функцию следует объявить как [pre2]std::string reverseWordsInString(const std::string &str) [/pre2] То есть в обоих случаях параметр функции должен иметь ссылочный тип. В первом случае строка передается по не константной ссылке, и функция возвращает ссылку на исходную строку, которая изменяется внутри функции, а во втором случае - по константной ссылке, так как строится новая строка на основе переданной строки в качестве аргумента. Далее, разделителями слов в строке могут быть не только символы пробела, но и символы табуляции '\t'. Когда строка, содержащая символы табуляции, выводится на консоль, то символы табуляции заменяются символами пробелов. Внутри функции переменную wordLength следует обьявить внутри цикла for [pre2] for (size_t i = 0; i < str.size(); ++i) { size_t wordLength = 0; //... [/pre2] а не перед ним, как это сделано в функции [pre2] size_t wordLength = 0; for (size_t i = 0; i < str.size(); ++i) [/pre2] так как эта переменная используется только внутри цикла for. Следует всегда объявлять переменные в наименьшей области объявления, где они используются. Использование предложение continue является излишним и в общем случае плохим стилем программирования [pre2] if (str != ' ') { ++wordLength; continue; } [/pre2] Цикл вполне можно написать без использования предложения continue. Кроме того, раз автор пишет программу на C++ и использует стандартный класс std::string, то следует использовать методы этого класса такие, как, уже показано в сообщениях выше, find_first_of и find_first_not_of. И нет никакой необходимости самому переписывать алгоритм std::reverse и, в частности, использовать данное if предложение [pre2] if (std::distance(begin, end) == 0) return;[/pre2] так как последующий цикл while учитывает это условие. [pre2] while (left < right) std::swap(*left++, *right--); [/pre2] То есть можно было бы написать [pre2] if ( begin != end ) { //... [/pre2] без использования избыточного предложения return. Также нет никакой необходимости вводить новые переменные [pre2] auto left = begin, right = std::prev(end); [/pre2] Вполне модно было бы обойтись переменными begin и end. Хотя выбор этих имен, которые совпадают с именами стандартных функций, является неудачным. Лучше использовать имена first и last, которые используются в описание стандартного алгоритма std::reverse в стандарте C++. Вместо вызова функции swap [pre2] std::swap(*left++, *right--); [/pre2] было бы лучше использовать другую стандартную функцию std::iter_swap [pre2] std::iter_swap( left++, right-- ); [/pre2] Таким образом функция reverse могла бы быть определена соедующим образом: [pre2] template <typename Iter> void reverse( Iter first, Iter last ) { if ( first != last ) { for ( ; first < --last; ++first ) { std::iter_swap( first, last ); } } } [/pre2] P.S. С любопытством жду следующую очередную попытку российского программиста реверсировать строку. Может быть она будет более успешной? Хотелось бы на это надеяться.

полная версия страницы