search and replace

C++ers:

Here's an open ended STL question. What's the smarmiest most templated way
to use <string>, <algorithms> etc. to turn this:

" able search baker search charlie "

into this:

" able replace baker replace charlie "

Note that "replace" has one more letter than "search", so you can't do an
inplace substitution.

An alternate prize goes to whoever provides an efficient way (that doesn't
use simple things like character pointers and buffers and C things ;).

(We are aware several C++ Regexps are available; we just need to learn more
raw STL here.)

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!

re: search and replace

"Phlip" <phlipcpp@yahoo.com> wrote in message
news:hnycf.2524$p37.121@newssvr17.news.prodigy.com ...[color=blue]
> C++ers:
>
> Here's an open ended STL question. What's the smarmiest most templated way
> to use <string>, <algorithms> etc. to turn this:
>
> " able search baker search charlie "
>
> into this:
>
> " able replace baker replace charlie "
>
> Note that "replace" has one more letter than "search", so you can't do an
> inplace substitution.[/color]

The maximum number of chars in the resultant string in the
worst-case-scenario is

newLen = (oldLen/sizeOf(SearchString) )*sizeOf(ReplaceString);

so create a memory buffer with the above lenght, and keep inserting strings
from the source to this buffer, word by word, until you hit the searchword.
when you hit the searchword,
instead of inserting the searchword, insert the replace word.

hope you followd that, if you need code.. mail back to the group.

[color=blue]
>
> An alternate prize goes to whoever provides an efficient way (that doesn't
> use simple things like character pointers and buffers and C things ;).
>
> (We are aware several C++ Regexps are available; we just need to learn
> more raw STL here.)
>
> --
> Phlip
> http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
>[/color]

re: search and replace

These days every post here smells way too much like homework, but I'll
give you the benefit of the doubt :D.

Phlip wrote:[color=blue]
> Here's an open ended STL question. What's the smarmiest most templated way
> to use <string>, <algorithms> etc. to turn this:
>
> " able search baker search charlie "
>
> into this:
>
> " able replace baker replace charlie "[/color]

I'm not really sure why you would need either <algorithm> or templates
here. Unless you want to be able to replace an int inside a string or
similar. Hmmmm...
[color=blue]
> Note that "replace" has one more letter than "search", so you can't do an
> inplace substitution.[/color]

Why not? Watch me :D

#include <string>
#include <iostream>

using namespace std;

int main()
{
const string search = "search";
const string replace = "replace";

string text = " able search baker search charlie ";

string::size_type found_at = text.find( search );
while( string::npos != found_at )
{
text.replace( found_at, search.length(), replace );
found_at = text.find( search, found_at + search.length() );
}

cout << text << endl;
}

Cheers,
Andre

re: search and replace

Phlip wrote:
[color=blue]
> C++ers:
>
> Here's an open ended STL question. What's the smarmiest most templated way
> to use <string>, <algorithms> etc. to turn this:
>
> " able search baker search charlie "
>
> into this:
>
> " able replace baker replace charlie "
>
> Note that "replace" has one more letter than "search", so you can't do an
> inplace substitution.[/color]

Ok, it's not templated; but it is short:

#include <iostream>
#include <string>

void replace_all ( std::string & str,
std::string const & pattern,
std::string const & replacement ) {
std::string::size_type start = str.find( pattern, 0 );
while ( start != str.npos ) {
str.replace( start, pattern.size(), replacement );
start = str.find( pattern, start+replacement.size() );
}
}

int main ( void ) {
std::string banner = " able search baker search charlie ";
std::string pattern = "search";
std::string replacement = "replace";
std::cout << banner << '\n';
replace_all ( banner, pattern, replacement );
std::cout << banner << '\n';
}


Best regards

Kai-Uwe Bux

re: search and replace

int2str@gmail.com wrote:
[color=blue]
>
> These days every post here smells way too much like homework, but I'll
> give you the benefit of the doubt :D.
>
> Phlip wrote:[color=green]
>> Here's an open ended STL question. What's the smarmiest most templated
>> way to use <string>, <algorithms> etc. to turn this:
>>
>> " able search baker search charlie "
>>
>> into this:
>>
>> " able replace baker replace charlie "[/color]
>
> I'm not really sure why you would need either <algorithm> or templates
> here. Unless you want to be able to replace an int inside a string or
> similar. Hmmmm...
>[color=green]
>> Note that "replace" has one more letter than "search", so you can't do an
>> inplace substitution.[/color]
>
> Why not? Watch me :D
>
> #include <string>
> #include <iostream>
>
> using namespace std;
>
> int main()
> {
> const string search = "search";
> const string replace = "replace";
>
> string text = " able search baker search charlie ";
>
> string::size_type found_at = text.find( search );
> while( string::npos != found_at )
> {
> text.replace( found_at, search.length(), replace );
> found_at = text.find( search, found_at + search.length() );
> }
>
> cout << text << endl;
> }[/color]

Why not? here is why:

#include <string>
#include <iostream>

using namespace std;

int main()
{
const string search = "search";
const string replace = "devious_search_replacement";

string text = " able search baker search charlie ";

string::size_type found_at = text.find( search );
while( string::npos != found_at )
{
text.replace( found_at, search.length(), replace );
cout << text << endl;
found_at = text.find( search, found_at + search.length() );
}

cout << text << endl;
}


Best regards

Kai-Uwe Bux

re: search and replace

* int2str@gmail.com:[color=blue]
>
> These days every post here smells way too much like homework, but I'll
> give you the benefit of the doubt :D.[/color]

Unless this Phlip is someone else than the regular Phlip, we can safely
discount the possibility of a homework question.

What surprises me is that Phlip wants to do this in C++, not in Ruby...

Anyways, for efficiency, I think a two-pass approach is indicated: first
find number of occurrences of the search pattern to be replaced, then
allocate buffer, then copy over with search pattern replaced. For an
original string of length n, that reduces the time from O(n^2) to O(n).
Of course the real decider would be to measure, measure, measure,
because two-pass might much _slower_ for short (typical?) strings.

How to do the searching efficiently depends on what's known about the
data.

For a long string the skipping algorithm used in various grep's could be
employed, and likewise for doing the same replacement on a multitude of
strings, but for a single global replacement on a short string using
skipping might be counter-productive because of the setup time. And to
bring that back on-topic (namely, C++), Phlip might be well advised --
or not -- to check out the facilities of the first standard library
Technical Report, the TR1. As I recall there is some regexp in there.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

re: search and replace

Kai-Uwe Bux wrote:[color=blue]
> int2str@gmail.com wrote:[color=green][color=darkred]
> >> Note that "replace" has one more letter than "search", so you can't do an
> >> inplace substitution.[/color]
> >
> > Why not? Watch me :D
> >
> > #include <string>
> > #include <iostream>
> >
> > using namespace std;
> >
> > int main()
> > {
> > const string search = "search";
> > const string replace = "replace";
> >
> > string text = " able search baker search charlie ";
> >
> > string::size_type found_at = text.find( search );
> > while( string::npos != found_at )
> > {
> > text.replace( found_at, search.length(), replace );
> > found_at = text.find( search, found_at + search.length() );
> > }
> >
> > cout << text << endl;
> > }[/color]
>
> Why not? here is why:
>
> #include <string>
> #include <iostream>
>
> using namespace std;
>
> int main()
> {
> const string search = "search";
> const string replace = "devious_search_replacement";
>
> string text = " able search baker search charlie ";
>
> string::size_type found_at = text.find( search );
> while( string::npos != found_at )
> {
> text.replace( found_at, search.length(), replace );
> cout << text << endl;
> found_at = text.find( search, found_at + search.length() );[/color]

You spotted my mistake here. This should read:
found_at = text.find( search, found_at + replace.length() );
[color=blue]
> }
>
> cout << text << endl;
> }[/color]


Cheers,
Andre

re: search and replace

"Phlip" <phlipcpp@yahoo.com> wrote in message
news:hnycf.2524$p37.121@newssvr17.news.prodigy.com ...[color=blue]
> C++ers:
>
> Here's an open ended STL question. What's the smarmiest most templated way
> to use <string>, <algorithms> etc. to turn this:
>
> " able search baker search charlie "
>
> into this:
>
> " able replace baker replace charlie "
>
> Note that "replace" has one more letter than "search", so you can't do an
> inplace substitution.
>
> An alternate prize goes to whoever provides an efficient way (that doesn't
> use simple things like character pointers and buffers and C things ;).
>[/color]

heh this is in Haskell:

searchReplace srch rpls xs = unwords $ searchReplace' srch rpls $ words xs
searchReplace' _ _ [] = []
searchReplace' srch rpls (x:xs) | x==srch = rpls:searchReplace' srch rpls
xs
| otherwise = x:searchReplace' srch rpls xs


C++:
string searchReplace(string search,string replace,string xs)
{
istringstream is(xs);string tmp;
ostringstream os;
while(is>>tmp)if(tmp==search)os<<replace;else os<<tmp;
return os.str();
}

I don't know which STL algorithm is equialent of this.

Greetings, Bane.

re: search and replace

"Branimir Maksimovic" <bmaxa@eunet.yu> wrote in message
news:dkv6u9$jr2$1@news.eunet.yu...[color=blue]
>
> C++:
> string searchReplace(string search,string replace,string xs)
> {
> istringstream is(xs);string tmp;
> ostringstream os;
> while(is>>tmp)if(tmp==search)os<<replace;else os<<tmp;[/color]
while(is>>tmp)
{
if(tmp==search)os<<replace;else os<<tmp;
os<<' ';
}
[color=blue]
> return os.str();
> }
>[/color]

Of course this is only if spaces are not important.

Greetings, Bane.

re: search and replace

Kai-Uwe Bux wrote:
[color=blue]
> Ok, it's not templated; but it is short:[/color]

I kind'a meant "STL-obsessed". Not just templated.
[color=blue]
> void replace_all ( std::string & str,
> std::string const & pattern,
> std::string const & replacement ) {
> std::string::size_type start = str.find( pattern, 0 );
> while ( start != str.npos ) {
> str.replace( start, pattern.size(), replacement );
> start = str.find( pattern, start+replacement.size() );
> }
> }[/color]

Great; everyone posted a loop with a find!

My colleague came up with this. Somehow:

stringstream ss;
ostream_iterator<string> outIterator(ss);

transform( m_str.begin(), m_str.end(), outIterator,
swap_character(asciiChar, substituteString) );

m_str = ss.str();

Note that it's a member of some method that transforms a member string
m_str, and that it searches for a single character and replaces it with
a string.

Could one upgrade that to work on a string?

Is its performance profile more or less "guaranteed" than the entries
so far?

The question ain't in Ruby because the answer is too danged simple -
Regular expressions are built-in, overhead and all...

--
Phlip

re: search and replace

Phlip wrote:[color=blue]
> Kai-Uwe Bux wrote:
>[color=green]
> > Ok, it's not templated; but it is short:[/color]
>
> I kind'a meant "STL-obsessed". Not just templated.[/color]

Ok, based on your coworkers idea, I came up with this one:

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

using namespace std;

class SearchAndReplace
{
public:
SearchAndReplace( const string & search, const string & replace )
: search_( search )
, replace_( replace )
, match_len_( 0 )
{
}

string operator() ( const char & c )
{
string s = "";

if ( c == search_[ match_len_ ] )
{
++match_len_;

if ( match_len_ == search_.length() )
{
s = replace_;
match_len_ = 0;
} else {
s = "";
}
} else {
if ( match_len_ > 0 )
s = search_.substr( 0, match_len_ );

s += c;
match_len_ = 0;
}

return s;
}

private:
string search_;
string replace_;
unsigned match_len_;
};

int main()
{
const string in = "Blo bla blo bla blo!";
const string search = "bla";
const string replace = "bliblaeeeep";

stringstream ss;
ostream_iterator< string > out( ss );

transform( in.begin(), in.end(), out,
SearchAndReplace( search, replace ) );

cout << ss.str() << endl;
}


How's that look?

Cheers,
Andre

re: search and replace

Thats my code with recursion, not optimize but works fine.

void ReplaceString(string &orginal,string searchstring,string value)
{
int pos;

pos = orginal.find (searchstring, 0);
if (pos < 0 ) return;

string s;
s = orginal;
orginal = s.substr(0,pos);
string rest = s.substr(pos + searchstring.length());
orginal = orginal + value + rest;
ReplaceString(orginal,searchstring,value);
}



Howie

re: search and replace

Howie wrote:
[color=blue]
> Thats my code with recursion, not optimize but works fine.[/color]

No, it does not.
[color=blue]
> void ReplaceString(string &orginal,string searchstring,string value)
> {
> int pos;
>
> pos = orginal.find (searchstring, 0);
> if (pos < 0 ) return;
>
> string s;
> s = orginal;
> orginal = s.substr(0,pos);
> string rest = s.substr(pos + searchstring.length());
> orginal = orginal + value + rest;
> ReplaceString(orginal,searchstring,value);
> }[/color]

Try:

int main ( void ) {
const string search = "search";
const string replace = "devious_search_replacement";

string text = " able search baker search charlie ";

ReplaceString( text, search, replace );
}

or:

int main ( void ) {
const string search = "search";
const string replace = "search";

string text = " able search search charlie ";

ReplaceString( text, search, replace );
}

Both run into an infinite loop.

To fix the problem, you might consider to swap the last to instructions:

void ReplaceString(string &orginal,string searchstring,string value)
{
int pos;

pos = orginal.find (searchstring, 0);
if (pos < 0 ) return;

string s;
s = orginal;
orginal = s.substr(0,pos);
string rest = s.substr(pos + searchstring.length());
ReplaceString( rest, searchstring, value );
orginal = orginal + value + rest;
}


Best

Kai-Uwe Bux

re: search and replace

On Fri, 11 Nov 2005 01:42:10 -0500, Kai-Uwe Bux <jkherciueh@gmx.net>
wrote:
[color=blue]
>Howie wrote:
>[color=green]
>> Thats my code with recursion, not optimize but works fine.[/color]
>
>No, it does not.
>[color=green]
>> void ReplaceString(string &orginal,string searchstring,string value)
>> {
>> int pos;
>>
>> pos = orginal.find (searchstring, 0);
>> if (pos < 0 ) return;
>>
>> string s;
>> s = orginal;
>> orginal = s.substr(0,pos);
>> string rest = s.substr(pos + searchstring.length());
>> orginal = orginal + value + rest;
>> ReplaceString(orginal,searchstring,value);
>> }[/color]
>
>Try:
>
>int main ( void ) {
> const string search = "search";
> const string replace = "devious_search_replacement";
>
> string text = " able search baker search charlie ";
>
> ReplaceString( text, search, replace );
>}
>
>or:
>
>int main ( void ) {
> const string search = "search";
> const string replace = "search";
>
> string text = " able search search charlie ";
>
> ReplaceString( text, search, replace );
>}
>
>Both run into an infinite loop.[/color]


Thanks Kai-Uwe,

this problem didn´t occur yet. I have fixed it.

Howie

re: search and replace

On 2005-11-10, Phlip <phlip2005@gmail.com> wrote:[color=blue]
> Great; everyone posted a loop with a find![/color]

Well, it's hard to think of anything better.
[color=blue]
> My colleague came up with this. Somehow:
>
> stringstream ss;
> ostream_iterator<string> outIterator(ss);
>
> transform( m_str.begin(), m_str.end(), outIterator,
> swap_character(asciiChar, substituteString) );
>
> m_str = ss.str();
>
> Note that it's a member of some method that transforms a member
> string m_str, and that it searches for a single character and
> replaces it with a string.
>
> Could one upgrade that to work on a string?
>
> Is its performance profile more or less "guaranteed" than the
> entries so far?[/color]

It looks slower to me, as at least two copies of the input string
have to be made, whereas the string member function version
doesn't necessarily make any copies. Moreover, iostreams are
heavy duty iron for such a simple task.

I'd call the idea clever but impractical. I'm not sure if it's
smarmy. ;-)

--
Neil Cerutti

re: search and replace

On 2005-11-11, int2str@gmail.com <int2str@gmail.com> wrote:[color=blue]
>
> Phlip wrote:[color=green]
>> Kai-Uwe Bux wrote:
>>[color=darkred]
>> > Ok, it's not templated; but it is short:[/color]
>>
>> I kind'a meant "STL-obsessed". Not just templated.[/color]
>
> Ok, based on your coworkers idea, I came up with this one:
>
> #include <iostream>
> #include <iterator>
> #include <string>
> #include <sstream>
> #include <algorithm>
>
> using namespace std;
>
> class SearchAndReplace
> {
> public:
> SearchAndReplace( const string & search, const string & replace )
> : search_( search )
> , replace_( replace )
> , match_len_( 0 )
> {
> }
>
> string operator() ( const char & c )
> {
> string s = "";
>
> if ( c == search_[ match_len_ ] )
> {
> ++match_len_;
>
> if ( match_len_ == search_.length() )
> {
> s = replace_;
> match_len_ = 0;
> } else {
> s = "";
> }
> } else {
> if ( match_len_ > 0 )
> s = search_.substr( 0, match_len_ );
>
> s += c;
> match_len_ = 0;
> }
>
> return s;
> }
>
> private:
> string search_;
> string replace_;
> unsigned match_len_;
> };
>
> int main()
> {
> const string in = "Blo bla blo bla blo!";
> const string search = "bla";
> const string replace = "bliblaeeeep";
>
> stringstream ss;
> ostream_iterator< string > out( ss );
>
> transform( in.begin(), in.end(), out,
> SearchAndReplace( search, replace ) );
>
> cout << ss.str() << endl;
> }
>
>
> How's that look?[/color]

Almost.

Consider in = "Blo blbla blo blbla blo!" for the same search and
replace.

--
Neil Cerutti

re: search and replace

Phlip wrote:
[color=blue]
> C++ers:
>
> Here's an open ended STL question. What's the smarmiest most templated way
> to use <string>, <algorithms> etc. to turn this:
>
> " able search baker search charlie "
>
> into this:
>
> " able replace baker replace charlie "
>
> Note that "replace" has one more letter than "search", so you can't do an
> inplace substitution.
>
> An alternate prize goes to whoever provides an efficient way (that doesn't
> use simple things like character pointers and buffers and C things ;).[/color]

Ok, here is my entry for the efficiency contest:


void replace_all ( std::string & str,
std::string const & pattern,
std::string const & replacement ) {
std::string::size_type const pattern_length = pattern.size();
std::string::size_type const str_length = str.length();
typedef std::vector< std::string::size_type > location_vect;
location_vect hits;
std::string::size_type start = str.find( pattern, 0 );
while ( start != str.npos ) {
hits.push_back( start );
start = str.find( pattern, start+pattern_length );
}
std::string dummy;
dummy.reserve( str_length
+
hits.size()*( replacement.length() - pattern_length ) );
std::string::size_type from = 0;
std::string::size_type to;
for ( location_vect::size_type chunk_index = 0;
chunk_index < hits.size(); ++ chunk_index ) {
to = hits[ chunk_index ];
dummy.append( str, from, to-from );
dummy.append( replacement );
from = to + pattern_length;
}
to = str_length;
dummy.append( str, from, to-from );
str.swap( dummy );
}


Best

Kai-Uwe Bux

re: search and replace

Neil Cerutti wrote:[color=blue]
> On 2005-11-11, int2str@gmail.com <int2str@gmail.com> wrote:[color=green]
> >
> > Phlip wrote:[color=darkred]
> >> Kai-Uwe Bux wrote:
> >>
> >> > Ok, it's not templated; but it is short:
> >>
> >> I kind'a meant "STL-obsessed". Not just templated.[/color]
> >
> > Ok, based on your coworkers idea, I came up with this one:
> >
> > #include <iostream>
> > #include <iterator>
> > #include <string>
> > #include <sstream>
> > #include <algorithm>
> >
> > using namespace std;
> >[/color][/color]

[snipped broken functor]
[color=blue][color=green]
> >
> > int main()
> > {
> > const string in = "Blo bla blo bla blo!";
> > const string search = "bla";
> > const string replace = "bliblaeeeep";
> >
> > stringstream ss;
> > ostream_iterator< string > out( ss );
> >
> > transform( in.begin(), in.end(), out,
> > SearchAndReplace( search, replace ) );
> >
> > cout << ss.str() << endl;
> > }
> >
> >
> > How's that look?[/color]
>
> Almost.
>
> Consider in = "Blo blbla blo blbla blo!" for the same search and
> replace.[/color]

You're right! Thanks.

Revised functor:

class SearchAndReplace
{
public:
SearchAndReplace( const string & search, const string & replace )
: search_( search )
, replace_( replace )
, match_len_( 0 )
{
}

string operator() ( const char & c )
{
string s = "";

if ( c != search_[ match_len_ ] && match_len_ > 0 )
{
s = search_.substr( 0, match_len_ );
match_len_ = 0;
}

if ( c == search_[ match_len_ ] )
{
++match_len_;

if ( match_len_ == search_.length() )
{
s = replace_;
match_len_ = 0;
}
} else {
s += c;
}

return s;
}

private:
string search_;
string replace_;
unsigned match_len_;
};

re: search and replace

Phlip wrote:[color=blue]
> Kai-Uwe Bux wrote:
>[color=green]
> > Ok, it's not templated; but it is short:[/color]
>
> I kind'a meant "STL-obsessed". Not just templated.
>[color=green]
> > void replace_all ( std::string & str,
> > std::string const & pattern,
> > std::string const & replacement ) {
> > std::string::size_type start = str.find( pattern, 0 );
> > while ( start != str.npos ) {
> > str.replace( start, pattern.size(), replacement );
> > start = str.find( pattern, start+replacement.size() );
> > }
> > }[/color]
>
> Great; everyone posted a loop with a find!
>
> My colleague came up with this. Somehow:
>
> stringstream ss;
> ostream_iterator<string> outIterator(ss);
>
> transform( m_str.begin(), m_str.end(), outIterator,
> swap_character(asciiChar, substituteString) );
>
> m_str = ss.str();
>
> Note that it's a member of some method that transforms a member string
> m_str, and that it searches for a single character and replaces it with
> a string.
>
> Could one upgrade that to work on a string?[/color]

transform in this case works with single chars, you have to convert
to a sequence of strings in order to work with this algorithm.
My first example can be converted to work with transform
but that does not satisfies, if spaces are not regarded as delimiters.

I'm learning Haskell and functional programming,
so I found this as a good practicing :).
Here is another version of code in both Haskell and coresponding C++
which works as you expected, I hope.
note there is no single temporary string created in C++ code.:)

// begin C++ ---------------------
#include <iostream>
#include <utility>

using namespace std;

typedef pair<string::iterator,string::iterator> Tuple1;
typedef pair<Tuple1,string::iterator> Tuple2;
typedef pair<bool,Tuple2> Tuple3;

Tuple3
searchr_p(string::iterator srb,string::iterator sre,
string::iterator xsb,string::iterator xse,
string::iterator fndb,string::iterator fnde)
{

if(srb == sre && xsb == xse)
return Tuple3(true,Tuple2(Tuple1(fndb,fnde),xsb));
if(srb == sre)
return Tuple3(true,Tuple2(Tuple1(fndb,fnde),xsb));
if(xsb == xse)
return Tuple3(false,Tuple2(Tuple1(fndb,fnde),xsb));

++fnde;
if(*srb == *xsb)
return searchr_p(++srb,sre,++xsb,xse,fndb,fnde);
else
return Tuple3(false,Tuple2(Tuple1(fndb,fnde),++xsb));
}

string&
searchr(string& sr,
string& rp,
string::iterator xsb,string::iterator xse,
string& out
)
{
if(sr.empty() || rp.empty() || xsb == xse)return out;

Tuple3 fnd = searchr_p(sr.begin(),sr.end(),
xsb,xse,
xsb,xsb);

if(fnd.first)
{
out+= rp;
searchr(sr,rp,fnd.second.second,xse,out);
}
else
{
out.append(fnd.second.first.first,fnd.second.first .second);
searchr(sr,rp,fnd.second.second,xse,out);
}
return out;
}


int main()
{
string sr = "search",rp="replace",str=" able search baker search
charlie ";
string out;
cout<<searchr(sr,rp,str.begin(),str.end(),out)<<'\ n';
}

// end C++

module Main where
import IO
main = do
sr <- getLine
rp <- getLine
str<- getLine
putStrLn $ "Working:" ++ sr ++ " " ++ rp ++ " " ++ str
putStrLn $ searchr sr rp str
putStrLn "Done"
{- search replace " able search baker search charlie " -}

-------------------------------------------------------------------------------

searchr :: String->String->String -> String
searchr [] _ xs = xs
searchr _ [] xs = xs
searchr _ _ [] = []
searchr sr rp xs | fst fnd = rp ++ searchr sr rp (snd $ snd fnd)
| otherwise = (fst $ snd fnd) ++
searchr sr rp (snd $ snd fnd)
where fnd = searchr' sr xs ""

searchr' :: String->String->String -> (Bool,(String,String))
searchr' [] [] fnd = (True,(fnd,[]))
searchr' [] xs fnd = (True,(fnd,xs))
searchr' sr [] fnd = (False,(fnd,[]))
searchr' (sr:srs) (x:xs) fndSoFar | sr == x = searchr' srs xs xxs
| otherwise = (False,(xxs,xs))
where xxs = x:fndSoFar
-------------------------------------------------------------------------------

Greetings, Bane.

re: search and replace

"Phlip" <phlipcpp@yahoo.com> wrote in message
news:hnycf.2524$p37.121@newssvr17.news.prodigy.com ...[color=blue]
> C++ers:
>
> Here's an open ended STL question. What's the smarmiest most templated way
> to use <string>, <algorithms> etc. to turn this:
>
> " able search baker search charlie "
>
> into this:
>
> " able replace baker replace charlie "
>
> Note that "replace" has one more letter than "search", so you can't do an
> inplace substitution.
>
> An alternate prize goes to whoever provides an efficient way (that doesn't
> use simple things like character pointers and buffers and C things ;).
>[/color]

Here is mine entry for efficiency contest :)

#include <iostream>
#include <utility>
#include <string>

using namespace std;

typedef pair<string::iterator,string::iterator> Tuple1;
typedef pair<Tuple1,string::iterator> Tuple2;
typedef pair<bool,Tuple2> Tuple3;

Tuple3
searchr_p(string::const_iterator srb,string::const_iterator sre,
string::iterator xsb,string::iterator xse,
string::iterator fndb,string::iterator fnde)
{

string::const_iterator tmps = srb;
while(srb != sre && xsb != xse && *srb==*xsb)
{
++fnde;++srb;++xsb;
}
if(srb == sre)
return Tuple3(true,Tuple2(Tuple1(fndb,fnde),xsb));
if(xsb == xse)
return Tuple3(false,Tuple2(Tuple1(fndb,fnde),xsb));

while(xsb!=xse && *tmps!=*xsb)
{
++fnde;++xsb;
}

return Tuple3(false,Tuple2(Tuple1(fndb,fnde),xsb));
}

string&
searchr(const string& sr,
const string& rp,
string::iterator xsb,string::iterator xse,
string& out
)
{
if(sr.empty() || rp.empty() || xsb == xse)return out.append(xsb,xse);

Tuple3 fnd = searchr_p(sr.begin(),sr.end(),
xsb,xse,
xsb,xsb);
while(fnd.second.first.first != fnd.second.first.second)
{
if(fnd.first)
{
out+= rp;
}
else
{
out.append(fnd.second.first.first,fnd.second.first .second);
}
fnd = searchr_p(sr.begin(),sr.end(),
fnd.second.second,xse,
fnd.second.second,fnd.second.second);
}
return out;
}


int main()
{
string sr = "search",rp="replace",str=" able search sea baker search
charlie ";
string out,tmp=str;
for (int i =0;i<1000000;++i)str+=tmp;
searchr(sr,rp,str.begin(),str.end(),out);
}

Greetings, Bane.

re: search and replace

In message <slrndn9co9.14s.leadvoice@FIAD06.norwich.edu>, Neil Cerutti
<leadvoice@email.com> writes[color=blue]
>On 2005-11-10, Phlip <phlip2005@gmail.com> wrote:[color=green]
>> Great; everyone posted a loop with a find![/color]
>
>Well, it's hard to think of anything better.
>[color=green]
>> My colleague came up with this. Somehow:
>>
>> stringstream ss;
>> ostream_iterator<string> outIterator(ss);
>>
>> transform( m_str.begin(), m_str.end(), outIterator,
>> swap_character(asciiChar, substituteString) );
>>
>> m_str = ss.str();
>>
>> Note that it's a member of some method that transforms a member
>> string m_str, and that it searches for a single character and
>> replaces it with a string.
>>
>> Could one upgrade that to work on a string?
>>
>> Is its performance profile more or less "guaranteed" than the
>> entries so far?[/color]
>
>It looks slower to me, as at least two copies of the input string
>have to be made, whereas the string member function version
>doesn't necessarily make any copies. Moreover, iostreams are
>heavy duty iron for such a simple task.
>
>I'd call the idea clever but impractical. I'm not sure if it's
>smarmy. ;-)
>[/color]
For smarmy++, there should be no explicit use of for, while, if, etc.,
which should all be hidden within an appropriate STL algorithm. Some of
the other competitors don't seem to have absorbed this principle ;-)

--
Richard Herring

re: search and replace

Phlip wrote:[color=blue]
> C++ers:
>
> Here's an open ended STL question. What's the smarmiest most templated way
> to use <string>, <algorithms> etc. to turn this:
>
> " able search baker search charlie "
>
> into this:
>
> " able replace baker replace charlie "
>
> Note that "replace" has one more letter than "search", so you can't do an
> inplace substitution.
>
> An alternate prize goes to whoever provides an efficient way (that doesn't
> use simple things like character pointers and buffers and C things ;).
>
> (We are aware several C++ Regexps are available; we just need to learn more
> raw STL here.)
>[/color]

Using routines to find the substring ,to reverse the end of the string
and add a string to the end will do the job. The sequence of
intermediate strings would be as follows:

" able search baker search charlie "
" able ielrahc hcraes rekab hcraes"
" able ielrahc hcraes rekab "
" able ielrahc hcraes rekab ecalper"
" able replace baker search charlie "
" able replace baker ielrahc hcraes"
" able replace baker ielrahc "
" able replace baker ielrahc ecalper"
" able replace baker replace charlie "

You should be able to work the rest out for yourself. But as you can see
this method only requires the buffer for the string to be increased by 2
characters and no separate buffers, as well as using simple, easily
understood algorithms.

JFJB

re: search and replace

n2xssvv g02gfr12930 wrote:[color=blue]
> Phlip wrote:
>[color=green]
>> C++ers:
>>
>> Here's an open ended STL question. What's the smarmiest most templated
>> way to use <string>, <algorithms> etc. to turn this:
>>
>> " able search baker search charlie "
>>
>> into this:
>>
>> " able replace baker replace charlie "
>>
>> Note that "replace" has one more letter than "search", so you can't do
>> an inplace substitution.
>>
>> An alternate prize goes to whoever provides an efficient way (that
>> doesn't use simple things like character pointers and buffers and C
>> things ;).
>>
>> (We are aware several C++ Regexps are available; we just need to learn
>> more raw STL here.)
>>[/color]
>
> Using routines to find the substring ,to reverse the end of the string
> and add a string to the end will do the job. The sequence of
> intermediate strings would be as follows:
>
> " able search baker search charlie "
> " able ielrahc hcraes rekab hcraes"
> " able ielrahc hcraes rekab "
> " able ielrahc hcraes rekab ecalper"
> " able replace baker search charlie "
> " able replace baker ielrahc hcraes"
> " able replace baker ielrahc "
> " able replace baker ielrahc ecalper"
> " able replace baker replace charlie "
>
> You should be able to work the rest out for yourself. But as you can see
> this method only requires the buffer for the string to be increased by 2
> characters and no separate buffers, as well as using simple, easily
> understood algorithms.
>
> JFJB[/color]
Here's the code using STL library functions

void ReplaceTest(void)
{
std::string Tmp(" able search baker search charlie ");

std::cout << Tmp << std::endl;

std::string::size_type p = Tmp.find("search",0);
std::reverse(Tmp.begin() + p,Tmp.end());
Tmp.erase(Tmp.end() - 6,Tmp.end());
Tmp += "ecalper";
std::reverse(Tmp.begin() + p,Tmp.end());

p = Tmp.find("search",0);
std::reverse(Tmp.begin() + p,Tmp.end());
Tmp.erase(Tmp.end() - 6,Tmp.end());
Tmp += "ecalper";
std::reverse(Tmp.begin() + p,Tmp.end());

std::cout << Tmp << std::endl;
}

JFJB