search and replace

P

Phlip

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.)
 
T

Tom

Phlip said:
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.

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.
 
K

Kai-Uwe Bux

Phlip said:
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.

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
 
I

int2str

These days every post here smells way too much like homework, but I'll
give you the benefit of the doubt :D.
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 "

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...
Note that "replace" has one more letter than "search", so you can't do an
inplace substitution.

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
 
K

Kai-Uwe Bux

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


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...


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

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
 
A

Alf P. Steinbach

* (e-mail address removed):
These days every post here smells way too much like homework, but I'll
give you the benefit of the doubt :D.

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.
 
I

int2str

Kai-Uwe Bux said:
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() );

You spotted my mistake here. This should read:
found_at = text.find( search, found_at + replace.length() );
}

cout << text << endl;
}


Cheers,
Andre
 
B

Branimir Maksimovic

Phlip said:
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 ;).

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.
 
B

Branimir Maksimovic

Branimir Maksimovic said:
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;
while(is>>tmp)
{
if(tmp==search)os<<replace;else os<<tmp;
os<<' ';
}
return os.str();
}

Of course this is only if spaces are not important.

Greetings, Bane.
 
P

Phlip

Kai-Uwe Bux said:
Ok, it's not templated; but it is short:

I kind'a meant "STL-obsessed". Not just templated.
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() );
}
}

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...
 
I

int2str

Phlip said:
I kind'a meant "STL-obsessed". Not just templated.

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
 
H

Howie

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
 
K

Kai-Uwe Bux

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

No, it does not.
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);
}

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
 
H

Howie

No, it does not.


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.


Thanks Kai-Uwe,

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

Howie
 
N

Neil Cerutti

Great; everyone posted a loop with a find!

Well, it's hard to think of anything better.
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?

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. ;-)
 
N

Neil Cerutti

I kind'a meant "STL-obsessed". Not just templated.

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?

Almost.

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

Kai-Uwe Bux

Phlip said:
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 ;).

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
 
I

int2str

[snipped broken functor]
Almost.

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

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

Branimir Maksimovic

Phlip said:
I kind'a meant "STL-obsessed". Not just templated.


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?

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
 
B

Branimir Maksimovic

Phlip said:
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 ;).

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top