Stroustrup 5.9 exercise 12

[arnuld]

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?

 

[Gary Wessle]

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

 

[Renato Golin]

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

 

[arnuld]

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 ?

 

[Renato Golin]

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

 

[Marcus Kwok]

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

 

[BobR]

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 <<--------
*/

 

[Renato Golin]

string Aname.npos =4294967295
string Aname.max_size() =1073741820 <<--------

Good point bob,

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

--renato

 

[BobR]

Renato Golin wrote in message

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