Reverse a String

[arnuld]

PURPOSE: This program asks the user to input words and then it
prints all of them in the same order but each word is reversed. e.g.
INPUT -> C++ Bjarne
OUTPUT -> ++C enrajB
*/

PROBLEM: I am not able to reverse the individual strings :-(

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>


int main()
{
std::vector<std::string> svec;

std::copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter( svec ) );



/* prints the vector to standard output */
std::cout << "\n------------------------------------\n";
std::copy( svec.begin(), svec.end(),
std:stream_iterator<std::string>( std::cout, "\n" ) );

return 0;
}

========= OUTPUT ==============
~/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra reverse-input.cpp
~/programming/c++ $ ./a.out
C++ Bjarne

------------------------------------
C++
Bjarne
~/programming/c++ $


I tried to use "reverse_copy" in place of 1st std::copy:

std::reverse_copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter(svec ) );


but it raises compile-time error:

~/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra reverse-input.cpp
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/stl_algo.h:
In function ‘_OutputIterator std::reverse_copy(_BidirectionalIterator,
_BidirectionalIterator,
:_OutputIterator) [with _BidirectionalIterator =
std::istream_iterator<std::basic_string<char, std::char_traits<char>,
std::allocator<char> >, char, std::char_traits<char>, long int>,
_OutputIterator =
std::back_insert_iterator<std::vector<std::basic_string<char,
std::char_traits<char>, std::allocator<char> >,
std::allocator<std::basic_string<char, std::char_traits<char>,
std::allocator<char> > > > >]’:
reverse-input.cpp:22: instantiated from here
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/stl_algo.h:1722:
error: no match for ‘operato\ r--’ in ‘--__last’ ~/programming/c++
$


-- arnuld
http://lispmachine.wordpress.com

 

[Barry]

I tried to use "reverse_copy" in place of 1st std::copy:

std::reverse_copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter(svec ) );

reverse_copy need the input to be BidirectionalIterator, while
istream_iterator is of ForwardIterator

 

[Gianni Mariani]

PURPOSE: This program asks the user to input words and then it
prints all of them in the same order but each word is reversed. e.g.
INPUT -> C++ Bjarne
OUTPUT -> ++C enrajB
*/

PROBLEM: I am not able to reverse the individual strings :-(

Why not use std::reverse() ?

 

[Guest]

PURPOSE: This program asks the user to input words and then it
prints all of them in the same order but each word is reversed. e.g.
INPUT -> C++ Bjarne
OUTPUT -> ++C enrajB
*/

PROBLEM: I am not able to reverse the individual strings :-(

You can always iterate over the characters in each string using a
reverse iterator, unless you actually reverse the words read in as
Gianni Mariani suggested.

 

[arnuld]

Why not use std::reverse() ?

tried that but that raises an error:


int main()
{
std::vector<std::string> svec;

std::reverse_copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter( svec ) );


std::reverse( svec.begin(), svec.end() );

/* prints the vector to standard output */
std::cout << "\n------------------------------------\n";
std::copy( svec.begin(), svec.end(),
std:stream_iterator<std::string>( std::cout, "\n" ) );

return 0;
}


~/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra reverse-input.cpp
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/stl_algo.h: In function ‘_OutputIterator std:\
:reverse_copy(_BidirectionalIterator, _BidirectionalIterator, _OutputIterator) [with _BidirectionalIterator = std::istream_i\
terator<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, char, std::char_traits<char>, long int>, _Ou\
tputIterator = std::back_insert_iterator<std::vector<std::basic_string<char, std::char_traits<char>, std::allocator<char> >,\
std::allocator<std::basic_string<char, std::char_traits<char>, std::allocator<char> > > > >]’:
reverse-input.cpp:22: instantiated from here
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/stl_algo.h:1722: error: no match for ‘operato\
r--’ in ‘--__last’
~/programming/c++ $



-- arnuld
http://lispmachine.wordpress.com

 

[Jerry Coffin]

[ ... ]

PROBLEM: I am not able to reverse the individual strings :-(

Yet!

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>


int main()
{
std::vector<std::string> svec;

std::copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter( svec ) );

Now you have a vector of strings. The next step is to step through the
vector and reverse each one.

/* prints the vector to standard output */
std::cout << "\n------------------------------------\n";
std::copy( svec.begin(), svec.end(),
std:stream_iterator<std::string>( std::cout, "\n" ) );

return 0;
}

[ ... ]

I tried to use "reverse_copy" in place of 1st std::copy:

The two iterators specifying the input to reverse_copy are required to
be bidirectional iterators, and an istream_iterator isn't a
bidirectional iterator. In C++ 0x, when we get concepts, it'll be
possible to encode requirements like this directly, to allow a much more
informative error message (interestingly, as I understand things, this
problem with error messages was one of the original motivations for the
work that resulted in the concepts proposal).

In any case, it wouldn't really do any good if it did work. You could
(for example) use reverse_copy in place of the _second_ copy quite
easily (vector iterators are random-access iterators, which are a
superset of bidirectional iterators) but it would just copy the strings
in reverse order, leaving each individual string unaffected.

I'd carry out the operation in three steps: read in the strings, then
reverse them, then write them out. You've got the reading and writing
done. The obvious way to reverse them (at least to me) would be a
functor that produces a reversed copy of an individual string, and
std::transform to apply that to the whole vector.

 

[arnuld]

The two iterators specifying the input to reverse_copy are required to
be bidirectional iterators, and an istream_iterator isn't a
bidirectional iterator. In C++ 0x, when we get concepts, it'll be
possible to encode requirements like this directly, to allow a much more
informative error message (interestingly, as I understand things, this
problem with error messages was one of the original motivations for the
work that resulted in the concepts proposal).

got that

In any case, it wouldn't really do any good if it did work. You could
(for example) use reverse_copy in place of the _second_ copy quite
easily (vector iterators are random-access iterators, which are a
superset of bidirectional iterators) but it would just copy the strings
in reverse order, leaving each individual string unaffected.

yes, I knew that and that is why I did not even try to write that one.

I'd carry out the operation in three steps: read in the strings, then
reverse them, then write them out. You've got the reading and writing
done. The obvious way to reverse them (at least to me) would be a
functor that produces a reversed copy of an individual string, and
std::transform to apply that to the whole vector.

I have created a function that does that thing and it works :

/* a function to reverse the string */
void rev_str( std::string& in_str )
{
std::string out_str;
for( std::string::const_reverse_iterator iter = in_str.rbegin();
iter != in_str.rend(); ++iter)
{
out_str.push_back( *iter );
}

in_str = out_str;
}



then I added this for reversing each string:

std::transform( svec.begin(), svec.end(), svec.begin(), rev_str )


and it raised a new mysterious error. 3rd argument to std::transform is
again svec.begin(), as I just want to put the result back into the same
vector and 4th argument is the function. I have tested the function and it
reverses a single string without any problem at all.


~/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra reverse-input.cpp
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/stl_algo.h:
In function ‘_OutputIterator std::transform(_InputIterator,
_InputIterator, _OutputIterator, _UnaryOperation) [with _InputIterator =
__gnu_cxx::__normal_iterator<std::basic_string<char,
std::char_traits<char>, std::allocator<char> >*,
std::vector<std::basic_string<char, std::char_traits<char>,
std::allocator<char> >, std::allocator<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > > > >, _OutputIterator =
__gnu_cxx::__normal_iterator<std::basic_string<char,
std::char_traits<char>, std::allocator<char> >*,
std::vector<std::basic_string<char, std::char_traits<char>,
std::allocator<char> >, std::allocator<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > > > >, _UnaryOperation =
void (*)(std::string&)]’: reverse-input.cpp:36: instantiated from here
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/stl_algo.h:936:
error: no match for ‘operator=’ in ‘__result.
__gnu_cxx::__normal_iterator<_Iterator, _Container>:perator* [with
_Iterator = std::basic_string<char, std::char_traits<char>,
std::allocator<char> >*, _Container = std::vector<std::basic_string<char,
std::char_traits<char>, std::allocator<char> >,
std::allocator<std::basic_string<char, std::char_traits<char>,
std::allocator<char> > > >]() =
__unary_op(((std::string&)((std::string*)__first.
__gnu_cxx::__normal_iterator<_Iterator, _Container>:perator* [with
_Iterator = std::basic_string<char, std::char_traits<char>,
std::allocator<char> >*, _Container = std::vector<std::basic_string<char,
std::char_traits<char>, std::allocator<char> >,
std::allocator<std::basic_string<char, std::char_traits<char>,
std::allocator<char> > > >]())))’
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/basic_string.h:490:
note: candidates are: std::basic_string<_CharT, _Traits, _Alloc>&
std::basic_string<_CharT, _Traits, _Alloc>:perator=(const
std::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = char, _Traits
= std::char_traits<char>, _Alloc = std::allocator<char>]
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/basic_string.h:498:
note: std::basic_string<_CharT, _Traits, _Alloc>&
std::basic_string<_CharT, _Traits, _Alloc>:perator=(const _CharT*) [with
_CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]
/usr/lib/gcc/x86_64-unknown-linux-gnu/4.2.1/../../../../include/c++/4.2.1/bits/basic_string.h:509:
note: std::basic_string<_CharT, _Traits, _Alloc>&
std::basic_string<_CharT, _Traits, _Alloc>:perator=(_CharT) [with _CharT
= char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>]
~/programming/c++ $



-- arnuld
http://lispmachine.wordpress.com

 

[arnuld]

I have created a function that does that thing and it works :

/* a function to reverse the string */
void rev_str( std::string& in_str )
{
std::string out_str;
for( std::string::const_reverse_iterator iter = in_str.rbegin();
iter != in_str.rend(); ++iter)
{
out_str.push_back( *iter );
}

in_str = out_str;
}

OOPS!, I overlooked these words of Stroustrup (page-532, section 18.6.2):

"I didn't really want to produce a return value from move_shape().
However, transform() insists on assigning the result of its operation."


Hence I corrected my function and the whole program work fine now. any
advice on improving the code ?

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

/* a function to reverse the string */
std::string rev_str( std::string& in_str )
{
std::string out_str;
for( std::string::const_reverse_iterator iter = in_str.rbegin(); iter != in_str.rend(); ++iter)
{
out_str.push_back( *iter );
}

return in_str = out_str;
}


int main()
{
std::vector<std::string> svec;

/* asks user for input & copied that into a vector of strings */
std::copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter( svec ) );

/* reverses each string (which is actually each element of the vector) */
std::transform( svec.begin(), svec.end(), svec.begin(), rev_str );

/* prints to std. out. */
std::cout << "\n------------------------------------\n";
std::copy( svec.begin(), svec.end(),
std:stream_iterator<std::string>( std::cout, "\n" ) );

return 0;
}

=========== OUTPUT ============
~/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra reverse-input.cpp
~/programming/c++ $ ./a.out
amit
arnuld
sardar

------------------------------------
tima
dlunra
radras
~/programming/c++ $





-- arnuld
http://lispmachine.wordpress.com

 

[Barry]

got that



yes, I knew that and that is why I did not even try to write that one.



I have created a function that does that thing and it works :

/* a function to reverse the string */
void rev_str( std::string& in_str )

string& rev_str

{
std::string out_str;
for( std::string::const_reverse_iterator iter = in_str.rbegin();
iter != in_str.rend(); ++iter)
{
out_str.push_back( *iter );
}

in_str = out_str;

std::reverse(in_str.begin(), in_str,end()); // do all the work

return in_str;

}



then I added this for reversing each string:

std::transform( svec.begin(), svec.end(), svec.begin(), rev_str )

put the return of rev_str to
svec

actually, transform here is not a good idea, as it do call operator=,
though it do check on "this != &rhs".

you can simply write:

for (std::vector<std::string>::iterator iter = svec.begin();
iter != svec.end(); ++iter)
{
std::reverse(iter->begin(), iter->end());
}

 

[arnuld]

actually, transform here is not a good idea, as it do call operator=,
though it do check on "this != &rhs".

you can simply write:

for (std::vector<std::string>::iterator iter = svec.begin();
iter != svec.end(); ++iter)
{
std::reverse(iter->begin(), iter->end());
}

your idea looks fine:


void rev_svec( std::vector<std::string>& svec)
{
for(std::vector<std::string>::iterator iter = svec.begin();
iter != svec.end(); ++iter )
{
std::reverse( iter->begin(), iter->end() );
}

}


but then I have to call the function independently, in main(), like this:

rev_svec( svec );


In my view, the std::transform looks clearer and reflects that we are
actually modifying the vector of strings but I am a newbie, So poke me
in the eye, if I am wrong.




-- arnuld
http://lispmachine.wordpress.com

 

[Jerry Coffin]

[ ... ]

/* a function to reverse the string */
std::string rev_str( std::string& in_str )
{
std::string out_str;
for( std::string::const_reverse_iterator iter = in_str.rbegin(); iter != in_str.rend(); ++iter)
{
out_str.push_back( *iter );
}

Look through string's ctor's and I'm pretty sure you can find a cleaner
way of producing the reversed string.

 

[Barry]

In my view, the std::transform looks clearer and reflects that we are
actually modifying the vector of strings but I am a newbie, So poke me
in the eye, if I am wrong.

The for (...) suggests that you should use for_each rather than transform,

as for_each is mutating the InputIterator one by one,
while transform means that you reconstruct new object from the
InputIterator into OutputIterator, that's why the Operation need a
return value.

 

[arnuld]

Look through string's ctor's and I'm pretty sure you can find a cleaner
way of producing the reversed string.

not sure what you mean by saying: string's ctor's but as suggested by
"Barry" and You, I came up with this:



/* a function to reverse the string */
std::string rev_str( std::string& in_str )
{
std::string out_str( in_str.rbegin(), in_str.rend() );

return out_str;
}


int main()
{
std::vector<std::string> svec;

/* asks user for input & copied that into a vector of strings */
std::copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter( svec ) );

/* reverses each string (which is actually each element of the vector) */
std::for_each( svec.begin(), svec.end(), rev_str);



/* prints to std. out. */
std::cout << "\n------------------------------------\n";
std::copy( svec.begin(), svec.end(),
std:stream_iterator<std::string>( std::cout, "\n" ) );

return 0;
}


it runs fine. Is it really necessary to create a function like "rev_str" ?
Don't we have some Std. Lib. algorithm to do that for us ?




-- arnuld
http://lispmachine.wordpress.com

 

[arnuld]

The for (...) suggests that you should use for_each rather than transform,

as for_each is mutating the InputIterator one by one,
while transform means that you reconstruct new object from the
InputIterator into OutputIterator, that's why the Operation need a
return value.

So using for_each() is more efficient than transform() because transform
will incur extra run-time cost ?

or you mean

In this particular exercise, using for_each() rather than transform(), is
a better coding practice ?



-- arnuld
http://lispmachine.wordpress.com

 

[Kai-Uwe Bux]

not sure what you mean by saying: string's ctor's but as suggested by
"Barry" and You, I came up with this:



/* a function to reverse the string */
std::string rev_str( std::string& in_str )
{
std::string out_str( in_str.rbegin(), in_str.rend() );

return out_str;
}

That function looks weird: it takes in_str by reference (indicating that it
might want to modify it) Then, however, it never does that. Instead, it
returns the reverted string. Either, you should do:

void revert ( std::string & str ) {
some code;
}

or

std::string reverted_string ( std::string const & in_str ) {
your code from above;
}

int main()
{
std::vector<std::string> svec;

/* asks user for input & copied that into a vector of strings */
std::copy( std::istream_iterator<std::string>( std::cin ),
std::istream_iterator<std::string>(),
std::back_inserter( svec ) );

/* reverses each string (which is actually each element of the vector)
*/ std::for_each( svec.begin(), svec.end(), rev_str);

That for_each will do nothing since rev_str does not actually modify the
parameter. You will want to use the version

void revert ( std::string & );

from above.

/* prints to std. out. */
std::cout << "\n------------------------------------\n";
std::copy( svec.begin(), svec.end(),
std:stream_iterator<std::string>( std::cout, "\n" ) );

Another idea would be to use transform here with the rev_str() function you
provided.

return 0;
}


it runs fine.

Yes, but it does not revert anything. :-(

Is it really necessary to create a function like "rev_str" ?
Don't we have some Std. Lib. algorithm to do that for us ?

All STL algorithms take ranges by pairs of iterators. If you want to pass a
container, you have to write a small wrapper around the algorithm.



Best

Kai-Uwe Bux

 

[Barry]

So using for_each() is more efficient than transform() because transform
will incur extra run-time cost ?

or you mean

In this particular exercise, using for_each() rather than transform(), is
a better coding practice ?

I think both

and from the semantic point of view
transform and for_each are different as I mentioned already.

As in your case, the source and target of /transform/ are the same
(/svec/), so it's more straightforward to say, I'm mutating /svec/
/for_each/

 

[arnuld]

That function looks weird: it takes in_str by reference (indicating that
it might want to modify it) Then, however, it never does that. Instead,
it returns the reverted string. Either, you should do:

...[SNIP]....

Yes, but it does not revert anything. :-(

ok, think I have understood it now. for_each() should be used with a
function that actually reverses a string:

void revert_string( std::string& in_str )
{
return std::reverse( in_str.begin(), in_str.end() );
}


whereas, transform(), is good for using a function that returns a copy of
the input string.

RIGHT ?

All STL algorithms take ranges by pairs of iterators. If you want to
pass a container, you have to write a small wrapper around the
algorithm.

wrapper around the algorithm ?

I did not understand that, did you mean like what we did here, by
creating a separate function ?



-- arnuld
http://lispmachine.wordpress.com

 

[Jerry Coffin]

That function looks weird: it takes in_str by reference (indicating that
it might want to modify it) Then, however, it never does that. Instead,
it returns the reverted string. Either, you should do:

...[SNIP]....

Yes, but it does not revert anything. :-(

ok, think I have understood it now. for_each() should be used with a
function that actually reverses a string:

void revert_string( std::string& in_str )
{
return std::reverse( in_str.begin(), in_str.end() );
}


whereas, transform(), is good for using a function that returns a copy of
the input string.

RIGHT ?

Yes -- a copy of the input string after reversing it, of course. I'm not
sure, but he may also have been referring to the fact that "revert" is
the wrong word here -- "revert" refers to returning something to its
previous state, so it really has little or nothing to do with reversing
something.

The reason I didn't recommend using std::for_each (and still don't) is
that for_each is defined as a non-modifying sequence algorithm, which
seems to me means it shouldn't be used to modify the sequence. Others
take it to mean only that for_each itself doesn't modify the sequence,
but what it invokes can do so.

wrapper around the algorithm ?

I did not understand that, did you mean like what we did here, by
creating a separate function ?

Yes, I'm pretty sure that's what he meant. It's worth noting that quite
a few people find these small "wrapper" types of functions rather
annoying, and have done various things to eliminate the requirement for
them, at least a large part of the time. There have been a number of
iterations on a proposal to add lambda expressions to C++ 0x. IIRC, the
proposal has been accepted (at least in principle) though there are
probably still details being worked out.

Even now, the Boost library allows you to use lambda expressions for
some situations, so (for example) if you prefer to print the container
out with for_each instead of std::copy, you could do something like:

#include <boost/lambda/lambda.hpp>

using namespace boost::lambda;

// ...

std::for_each(svec.begin(), svec.end(), std::cout << _1 << '\n');

 

[James Kanze]

it takes in_str by reference (indicating that
it might want to modify it) Then, however, it never does that. Instead,
it returns the reverted string. Either, you should do:
...[SNIP]....
Yes, but it does not revert anything. :-(

ok, think I have understood it now. for_each() should be used with a
function that actually reverses a string:

void revert_string( std::string& in_str )
{
return std::reverse( in_str.begin(), in_str.end() );
}

whereas, transform(), is good for using a function that returns a copy of
the input string.

RIGHT ?

No. Transform is used when you want to modify each element of
the sequence, independently of the other elements. Reverse is
used when you want to reverse the order of the elements, without
modifying any of them. Both have there uses, but neither is
what one would call frequent (particularly on strings---I've
never found a real use for either on a string).

wrapper around the algorithm ?
Yes.

I did not understand that, did you mean like what we did here, by
creating a separate function ?

Exactly.

 

[jkherciueh]

it takes in_str by reference (indicating
that it might want to modify it) Then, however, it never does that.
Instead, it returns the reverted string. Either, you should do:
...[SNIP]....
Yes, but it does not revert anything. :-(

ok, think I have understood it now. for_each() should be used with a
function that actually reverses a string:

void revert_string( std::string& in_str )
{
return std::reverse( in_str.begin(), in_str.end() );
}

whereas, transform(), is good for using a function that returns a copy of
the input string.

RIGHT ?

No.

I think, arnuld is essentially correct.

Transform is used when you want to modify each element of
the sequence, independently of the other elements. Reverse is
used when you want to reverse the order of the elements, without
modifying any of them.

I think, you slightly misunderstood the question. He did not ask about
transform vs reverse, but about transform vs for_each (the use of
std::reverse in the implementation of the functor is really immaterial to
his question).

The algorithm transform() uses a functor that yields a result and assigns
those results to the elements in the target range whereas for_each()
ignores possible results of the functor and operates on a single range.
That is the difference arnuld wanted to reconfirm.

Both have there uses, but neither is
what one would call frequent (particularly on strings---I've
never found a real use for either on a string).

In the problem from which this discussion arose, he does not want to use
either algorithm on std::string but on std::vector< std::string >. (The
task is to reverse each string in the vector.)


Best

Kai-Uwe Bux