Stroustrup 5.9 exercise 12

Discussion in 'C++' started by arnuld, Nov 9, 2006.

  1. arnuld

    arnuld Guest

    problem: write a function that counts the number of occurences of a
    pair of letters in a string. e.g the pair "ab" appears twice in
    "xabaacbaxabb".

    i thought i could use "count()" from standard library but that works on
    a container and "std::string" is not a container, its a class. even if
    i put the "std::string" into a container then it will act as one elemnt
    only e.g ["xabaaacbaxabb"] and hence count will not work (i tried it).
    so can you please give some idea in solving this problem?
    arnuld, Nov 9, 2006
    #1
    1. Advertising

  2. arnuld

    Gary Wessle Guest

    "arnuld" <> writes:

    > problem: write a function that counts the number of occurences of a
    > pair of letters in a string. e.g the pair "ab" appears twice in
    > "xabaacbaxabb".
    >
    > i thought i could use "count()" from standard library but that works on
    > a container and "std::string" is not a container, its a class. even if
    > i put the "std::string" into a container then it will act as one elemnt
    > only e.g ["xabaaacbaxabb"] and hence count will not work (i tried it).
    > so can you please give some idea in solving this problem?


    loop through each position in the string, taking this position + 1 as
    a string, feed it into a map<string,int> mymap[ab]=i++.
    Gary Wessle, Nov 9, 2006
    #2
    1. Advertising

  3. arnuld

    Renato Golin Guest

    arnuld wrote:
    > problem: write a function that counts the number of occurences of a
    > pair of letters in a string. e.g the pair "ab" appears twice in
    > "xabaacbaxabb".
    >
    > i thought i could use "count()" from standard library but that works on
    > a container and "std::string" is not a container, its a class. even if
    > i put the "std::string" into a container then it will act as one elemnt
    > only e.g ["xabaaacbaxabb"] and hence count will not work (i tried it).
    > so can you please give some idea in solving this problem?
    >


    You can use the find method of the string object.

    #include <iostream>
    #include <string>

    using namespace std;

    int
    main () {
    // The string
    string str = "xabaacbaxabb";
    // The null pos
    string::size_type pos = string::npos;
    // Count matches
    int count = 0;

    // Set pos to next match
    // Search for it again on next pos
    // Until stop matching
    while ((pos = str.find("ab", pos+1)) != string::npos) {
    // Increment your counter while matches
    count++;
    }
    cout << count << endl;
    return 0;
    }


    You can also put everything inside a for loop:

    for (pos = string::npos, count = 0;
    (pos = haystack.find(needle, pos+1)) != string::npos;
    count++)
    ;

    --renato

    --
    Reclaim your digital rights, eliminate DRM, learn more at
    http://www.defectivebydesign.org/what_is_drm
    Renato Golin, Nov 9, 2006
    #3
  4. arnuld

    arnuld Guest

    > Renato Golin wrote:

    > You can use the find method of the string object.
    >
    > #include <iostream>
    > #include <string>
    >
    > using namespace std;
    >
    > int
    > main () {
    > // The string
    > string str = "xabaacbaxabb";
    > // The null pos
    > string::size_type pos = string::npos;
    > // Count matches
    > int count = 0;
    >
    > // Set pos to next match
    > // Search for it again on next pos
    > // Until stop matching
    > while ((pos = str.find("ab", pos+1)) != string::npos) {
    > // Increment your counter while matches
    > count++;
    > }
    > cout << count << endl;
    > return 0;
    > }


    hey, it works, thanks :) but i did not understand what "string::npos"
    does.

    >
    > You can also put everything inside a for loop:
    >
    > for (pos = string::npos, count = 0;
    > (pos = haystack.find(needle, pos+1)) != string::npos;
    > count++)
    > ;
    >


    what exactly the "haystack" is ?
    arnuld, Nov 9, 2006
    #4
  5. arnuld

    Renato Golin Guest

    arnuld wrote:
    > hey, it works, thanks :) but i did not understand what "string::npos"
    > does.


    npos is the null-position or no-position and it's a value defined by the
    string implementation as "no position within this string". Each
    implementation can create whatever number it wants to (negative,
    MAX_INT, etc) so, to do a portable code you should never compare it to
    the number you have now as "end-of-string" but to npos.

    As zero is the first position it cannot be used to check if the find is
    successful or not such as in:

    if (!string.find("foo"))

    or

    if ((pos = string.find("foo")) == 0)

    In my implementation, string::npos is 4294967295 (or max unsigned int)
    as it does not allow strings bigger than that (I suppose). You can check
    yours by simply:

    cout << string::npos << endl;

    But you should never use that value to check if the position is valid or
    not.

    Note that you should set pos to npos at the beginning because, if
    something fails with find you will not be locked in that loop.


    > what exactly the "haystack" is ?


    Literally is horse's food (normally loads of them), but it's a common
    term used in search algorithms because of the phrase "finding a needle
    in a haystack".

    In algorithms phraseology. 'haystack' is the text or collection of
    things you have and 'needle' is what you want to find there.

    cheers,
    --renato

    --
    Reclaim your digital rights, eliminate DRM, learn more at
    http://www.defectivebydesign.org/what_is_drm
    Renato Golin, Nov 9, 2006
    #5
  6. arnuld

    Marcus Kwok Guest

    arnuld <> wrote:
    > i thought i could use "count()" from standard library but that works on
    > a container and "std::string" is not a container, its a class.


    Actually, std::string is a container of chars, but with a different
    interface than the standard "containers".

    std::string is actually a typedef of std::basic_string<char>.

    --
    Marcus Kwok
    Replace 'invalid' with 'net' to reply
    Marcus Kwok, Nov 9, 2006
    #6
  7. arnuld

    BobR Guest

    Renato Golin wrote in message ...
    >
    >In my implementation, string::npos is 4294967295 (or max unsigned int)
    >** as it does not allow strings bigger than that (I suppose)**. You can

    check
    >yours by simply:
    >
    > cout << string::npos << endl;


    std::string Aname( "hello" );
    std::cout<<" string::npos ="<< std::string::npos << std::endl;
    std::cout<<" string Aname.npos ="<< Aname.npos << std::endl;
    std::cout<<" string Aname.max_size() ="<< Aname.max_size() << std::endl;
    /* --- output --- (win32, MinGW(GCC)) YMMV
    string::npos =4294967295
    string Aname.npos =4294967295
    string Aname.max_size() =1073741820 <<--------
    */

    --
    Bob R
    POVrookie
    BobR, Nov 9, 2006
    #7
  8. arnuld

    Renato Golin Guest

    BobR wrote:
    > string Aname.npos =4294967295
    > string Aname.max_size() =1073741820 <<--------


    Good point bob,

    I wonder why they limit to 1G instead of 4G-1...

    --renato

    --
    Reclaim your digital rights, eliminate DRM, learn more at
    http://www.defectivebydesign.org/what_is_drm
    Renato Golin, Nov 10, 2006
    #8
  9. arnuld

    BobR Guest

    Renato Golin wrote in message
    <455469a5$0$505$>...
    >BobR wrote:
    >> string Aname.npos =4294967295
    >> string Aname.max_size() =1073741820 <<--------

    >
    >Good point bob,
    >
    >I wonder why they limit to 1G instead of 4G-1...
    >renato


    My rule is: when the string gets to be 999meg, I switch to vector<string> to
    break it up a little. <G>

    When is the last time you really needed a string that big?

    On an old 40 column machine, using an old 66 lines per page printer, that's
    nearly 380,000 pages! PER string!!<G> That's a lot of trees!! So, by limiting
    it to 1G, they were doing their part for conservation.
    { I gotta quit watching those old 'Three Stooges' movies! Nyuck nyuck nyuck.}

    --
    Bob R
    POVrookie
    BobR, Nov 11, 2006
    #9
    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. arnuld

    Stroustrup 5.9 exercise 6

    arnuld, Nov 8, 2006, in forum: C++
    Replies:
    7
    Views:
    368
    arnuld
    Nov 8, 2006
  2. arnuld
    Replies:
    5
    Views:
    340
    Alf P. Steinbach
    Nov 8, 2006
  3. arnuld
    Replies:
    2
    Views:
    291
    arnuld
    Nov 8, 2006
  4. arnuld
    Replies:
    6
    Views:
    382
    arnuld
    Nov 8, 2006
  5. arnuld

    Stroustrup 5.9 exercise 9

    arnuld, Nov 8, 2006, in forum: C++
    Replies:
    5
    Views:
    385
    Bernd Strieder
    Nov 9, 2006
Loading...

Share This Page