Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Stroustrup 5.9 exercise 12

Reply
Thread Tools

Stroustrup 5.9 exercise 12

 
 
arnuld
Guest
Posts: n/a
 
      11-09-2006
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?

 
Reply With Quote
 
 
 
 
Gary Wessle
Guest
Posts: n/a
 
      11-09-2006
"arnuld" <(E-Mail Removed)> 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++.
 
Reply With Quote
 
 
 
 
Renato Golin
Guest
Posts: n/a
 
      11-09-2006
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
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      11-09-2006
> 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 ?

 
Reply With Quote
 
Renato Golin
Guest
Posts: n/a
 
      11-09-2006
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
 
Reply With Quote
 
Marcus Kwok
Guest
Posts: n/a
 
      11-09-2006
arnuld <(E-Mail Removed)> 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
 
Reply With Quote
 
BobR
Guest
Posts: n/a
 
      11-09-2006

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


 
Reply With Quote
 
Renato Golin
Guest
Posts: n/a
 
      11-10-2006
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
 
Reply With Quote
 
BobR
Guest
Posts: n/a
 
      11-11-2006

Renato Golin wrote in message
<455469a5$0$505$(E-Mail Removed)>. ..
>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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Stroustrup 5.9 exercise 9 arnuld C++ 5 11-09-2006 10:45 AM
Stroustrup 5.9 exercise 6 (char& as argument) arnuld C++ 5 11-08-2006 06:03 PM
Stroustrup exercise 7 section 5.9 (using struct) arnuld C++ 6 11-08-2006 04:40 PM
Stroustrup exercise 7 section 5.9 (using arrays) arnuld C++ 2 11-08-2006 03:18 PM
Stroustrup 5.9 exercise 6 arnuld C++ 7 11-08-2006 01:44 PM



Advertisments