Читаем Thinking In C++. Volume 2: Practical Programming полностью

The simplest use of find( ) searches for one or more characters in a string. This overloaded version of find( ) takes a parameter that specifies the character(s) for which to search and optionally a parameter that tells it where in the string to begin searching for the occurrence of a substring. (The default position at which to begin searching is 0.) By setting the call to find inside a loop, you can easily move through a string, repeating a search to find all the occurrences of a given character or group of characters within the string^.

The following program uses the method of The Sieve of Eratosthenes to find prime numbers less than 50. This method starts with the number 2, marks all subsequent multiples of 2 as not prime, and repeats the process for the next prime candidate. Notice that we define the string object sieveChars using a constructor idiom that sets the initial size of the character array and writes the value ‘P’ to each of its member^.

//: C03:Sieve.cpp

//{L} ../TestSuite/Test

#include

#include

#include

#include "../TestSuite/Test.h"

using namespace std;

class SieveTest : public TestSuite::Test {

  string sieveChars;

public:

  // Create a 50 char string and set each

  // element to 'P' for Prime

SieveTest() : sieveChars(50, 'P') {}

  void run() {

    findPrimes();

    testPrimes();

  }

  bool isPrime(int p) {

    if (p == 0 || p == 1) return false;

    int root = int(sqrt(double(p)));

    for (int i = 2; i <= root; ++i)

      if (p % i == 0) return false;

    return true;

  }

  void findPrimes() {

    // By definition neither 0 nor 1 is prime.

    // Change these elements to "N" for Not Prime

    sieveChars.replace(0, 2, "NN");

    // Walk through the array:

    size_t sieveSize = sieveChars.size();

    int root = int(sqrt(double(sieveSize)));

    for (int i = 2; i <= root; ++i)

      // Find all the multiples:

      for (size_t factor = 2; factor * i < sieveSize;

           ++factor)

        sieveChars[factor * i] = 'N';

  }

  void testPrimes() {

    size_t i = sieveChars.find('P');

    while (i != string::npos) {

      test_(isPrime(i++));

      i = sieveChars.find('P', i);

    }

    i = sieveChars.find_first_not_of('P');

    while (i != string::npos) {

      test_(!isPrime(i++));

      i = sieveChars.find_first_not_of('P', i);

    }

  }

};

int main() {

  SieveTest t;

  t.run();

  return t.report();

} ///:~

The find( ) function allows you to walk forward through a string, detecting multiple occurrences of a character or a group of characters, and find_first_not_of( ) allows you to find other characters or substrings^.