search and replace

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

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

[Tom]

"Phlip" <ph******@yahoo .com> wrote in message
news:hn******** ********@newssv r17.news.prodig y.com...

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(SearchSt ring) )*sizeOf(Replac eString);

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.


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

[int2str]

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

Phlip wrote:

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_ty pe 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

[Kai-Uwe Bux]

Phlip wrote:

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::si ze_type start = str.find( pattern, 0 );
while ( start != str.npos ) {
str.replace( start, pattern.size(), replacement );
start = str.find( pattern, start+replaceme nt.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

[Kai-Uwe Bux]

in*****@gmail.c om wrote:

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

Phlip wrote:

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_ty pe 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_ty pe 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

[Alf P. Steinbach]

* in*****@gmail.c om:

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.

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

[int2str]

Kai-Uwe Bux wrote:

in*****@gmail.c om wrote:

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_ty pe 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_ty pe 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

[Branimir Maksimovic]

"Phlip" <ph******@yahoo .com> wrote in message
news:hn******** ********@newssv r17.news.prodig y.com...

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:searchRepl ace' srch rpls
xs
| otherwise = x:searchReplace ' srch rpls xs
C++:
string searchReplace(s tring search,string replace,string xs)
{
istringstream is(xs);string tmp;
ostringstream os;
while(is>>tmp)i f(tmp==search)o s<<replace;els e os<<tmp;
return os.str();
}

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

Greetings, Bane.

[Branimir Maksimovic]

"Branimir Maksimovic" <bm***@eunet.yu > wrote in message
news:dk******** **@news.eunet.y u...

C++:
string searchReplace(s tring search,string replace,string xs)
{
istringstream is(xs);string tmp;
ostringstream os;
while(is>>tmp)i f(tmp==search)o s<<replace;els e os<<tmp; while(is>>tmp)
{
if(tmp==search) os<<replace;els e os<<tmp;
os<<' ';
}
return os.str();
}

Of course this is only if spaces are not important.

Greetings, Bane.

[Phlip]

Kai-Uwe Bux wrote:

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::si ze_type start = str.find( pattern, 0 );
while ( start != str.npos ) {
str.replace( start, pattern.size(), replacement );
start = str.find( pattern, start+replaceme nt.size() );
}
}

Great; everyone posted a loop with a find!

My colleague came up with this. Somehow:

stringstream ss;
ostream_iterato r<string> outIterator(ss) ;

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

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