search and replace

Discussion in 'C++' started by Phlip, Nov 10, 2005.

  1. Phlip

    Phlip Guest

    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!!!
     
    Phlip, Nov 10, 2005
    #1
    1. Advertising

  2. Phlip

    Tom Guest

    "Phlip" <> wrote in message
    news:hnycf.2524$...
    > 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.


    >
    > 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, Nov 10, 2005
    #2
    1. Advertising

  3. Phlip

    Kai-Uwe Bux Guest

    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::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
     
    Kai-Uwe Bux, Nov 10, 2005
    #3
  4. Phlip

    Guest

    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_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
     
    , Nov 10, 2005
    #4
  5. Phlip

    Kai-Uwe Bux Guest

    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_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
     
    Kai-Uwe Bux, Nov 10, 2005
    #5
  6. * :
    >
    > 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?
     
    Alf P. Steinbach, Nov 10, 2005
    #6
  7. Phlip

    Guest

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


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

    > }
    >
    > cout << text << endl;
    > }



    Cheers,
    Andre
     
    , Nov 10, 2005
    #7
  8. "Phlip" <> wrote in message
    news:hnycf.2524$...
    > 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.
     
    Branimir Maksimovic, Nov 10, 2005
    #8
  9. "Branimir Maksimovic" <> wrote in message
    news:dkv6u9$jr2$...
    >
    > 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.
     
    Branimir Maksimovic, Nov 10, 2005
    #9
  10. Phlip

    Phlip Guest

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

    --
    Phlip
     
    Phlip, Nov 10, 2005
    #10
  11. Phlip

    Guest

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

    >
    > 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
     
    , Nov 11, 2005
    #11
  12. Phlip

    Howie Guest

    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
     
    Howie, Nov 11, 2005
    #12
  13. Phlip

    Kai-Uwe Bux Guest

    Howie wrote:

    > 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
     
    Kai-Uwe Bux, Nov 11, 2005
    #13
  14. Phlip

    Howie Guest

    On Fri, 11 Nov 2005 01:42:10 -0500, Kai-Uwe Bux <>
    wrote:

    >Howie wrote:
    >
    >> 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.



    Thanks Kai-Uwe,

    this problem didnĀ“t occur yet. I have fixed it.

    Howie
     
    Howie, Nov 11, 2005
    #14
  15. Phlip

    Neil Cerutti Guest

    On 2005-11-10, Phlip <> wrote:
    > 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. ;-)

    --
    Neil Cerutti
     
    Neil Cerutti, Nov 11, 2005
    #15
  16. Phlip

    Neil Cerutti Guest

    On 2005-11-11, <> wrote:
    >
    > Phlip wrote:
    >> Kai-Uwe Bux wrote:
    >>
    >> > Ok, it's not templated; but it is short:

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

    --
    Neil Cerutti
     
    Neil Cerutti, Nov 11, 2005
    #16
  17. Phlip

    Kai-Uwe Bux Guest

    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.
    >
    > 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
     
    Kai-Uwe Bux, Nov 11, 2005
    #17
  18. Phlip

    Guest

    Neil Cerutti wrote:
    > On 2005-11-11, <> wrote:
    > >
    > > Phlip wrote:
    > >> Kai-Uwe Bux wrote:
    > >>
    > >> > Ok, it's not templated; but it is short:
    > >>
    > >> 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;
    > >


    [snipped broken functor]

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


    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_;
    };
     
    , Nov 11, 2005
    #18
  19. Phlip wrote:
    > 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::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?


    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.
     
    Branimir Maksimovic, Nov 11, 2005
    #19
  20. "Phlip" <> wrote in message
    news:hnycf.2524$...
    > 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.
     
    Branimir Maksimovic, Nov 12, 2005
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mark McKay
    Replies:
    3
    Views:
    1,331
    Thomas Weidenfeller
    Jan 21, 2004
  2. Brian Blais
    Replies:
    1
    Views:
    400
    Bruno Desthuilliers
    Jun 27, 2006
  3. Greg Ewing
    Replies:
    2
    Views:
    367
    Dieter Maurer
    Jun 29, 2006
  4. Abby Lee
    Replies:
    5
    Views:
    449
    Abby Lee
    Aug 2, 2004
  5. Replies:
    1
    Views:
    529
    Rainer Weikusat
    Jun 21, 2012
Loading...

Share This Page