Traversals and Predicates

[cppuser]

Hello,
can someone tell me what means "traversal" and what means "predicate" ?
It's from "The C++ Programming language" book, 3.8.4 page 61.

Thank you in advance :)

[Duthomhas]

Predicate = function returning true or false for an argument value.
See http://www.cs.odu.edu/~toida/nerzic/content/logic/pred_logic/intr_to_pred_logic.html
Google around "predicate logic"

Traversal = following a path (say, of nodes in a linked list, or items in an array, etc)

Complex Number = http://en.wikipedia.org/wiki/Complex_number

[cppuser]

Thank you for your answer, Duoas. :)
Have a nice day !

[cppuser]

But what's actually the difference between find and find_if and between replace and replace_if and count and count_if ?

[jsmith]

find is equivalent to find_if with operator== as the predicate.

Example:

vector<int> v;
// put stuff in it

find( v.begin(), v.end(), 5 );
//is equivalent to:


struct IsEqualTo5 {
   bool operator()( int x ) const
       { return x == 5; }
};

find_if( v.begin(), v.end(), IsEqualTo5() );

Same goes for replace/replace_if and count/count_if

[jsmith]

Another way to look at it. Consider an implementation of find and find_if:

// simplified a bit here...

template< typename Iter, typename T >
Iter find( Iter first, Iter last, T val )
{
    for( ; first != last; ++first )
        if( *first == val )
             return first;

    return first;
}


template< typename Iter, typename Compare >
Iter find_if( Iter first, Iter last, Compare comp )
{
    for( ; first != last; ++first )
        if( comp( *first ) )  // This is the only difference
             return first;

    return first;
}

[Duthomhas]

The first uses the equality predicate.
The second allows you to provide your own predicate.

Examples:

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;

// Here is our example string
string pi = "3.14159265358979323846264338327950288419716939937510";

// Here is a predicate function.
// It takes as argument a digit.
// If it is a numeric value evenly divisible by three, then it returns true.
// Otherwise, it returns false.
bool divisible_by_three( char digit )
  {
  return isdigit( digit ) && (digit != '0') && (((digit - '0') % 3) == 0);
  }

int main()
  {
  cout << "The value of pi to " << (pi.length() - 2) << " decimal places is\n"
       << pi
       << "\n\n";

  cout << "The number of digits equal to '4' is "
       << count( pi.begin(), pi.end(), '4' )
       << "\n\n";

  cout << "The number of digits evenly divisible by 3 is "
       << count_if( pi.begin(), pi.end(), divisible_by_three )
       << "\n\n";

  return 0;
  }

A predicate may either be an actual function, as in the example, or a functor -- an object that behaves like a function. I could have coded it like this:

// Here is a predicate functor.
// It takes as argument a digit.
// If it is a numeric value evenly divisible by three, then it returns true.
// Otherwise, it returns false.
struct divisible_by_three
  {
  bool operator () ( const char& digit ) const
    {
    return isdigit( digit ) && (digit != '0') && (((digit - '0') % 3) == 0);
    }
  };

  cout << "The number of digits evenly divisible by 3 is "
       << count_if( pi.begin(), pi.end(), divisible_by_three() )
       << "\n\n";

See http://www.newty.de/fpt/functor.html for more.

Hope this helps.

[cppuser]

Thank you, I'm starting to understand this.

Duoas, is here some mistake or there are really no brackets after "divisible_by_three" after the first count_if ?

cout << "The number of digits evenly divisible by 3 is "
       << count_if( pi.begin(), pi.end(), divisible_by_three )
       << "\n\n";

cout << "The number of digits evenly divisible by 3 is "
       << count_if( pi.begin(), pi.end(), divisible_by_three() )
       << "\n\n";

[Duthomhas]

That's exactly right.

In the first, the predicate is a function, whose address is simply divisible_by_three.

In the second, the predicate is a functor (a class), so we must create a temporary instance of that class as divisible_by_three().

Here it is using the functor with both a named instance and a temporary instance:

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;

// Here is our example string
string pi = "3.14159265358979323846264338327950288419716939937510";

// Here is a predicate functor.
// It takes as argument a digit.
// If it is a numeric value evenly divisible by three, then it returns true.
// Otherwise, it returns false.
struct divisible_by_three
  {
  bool operator () ( const char& digit ) const
    {
    return isdigit( digit ) && (digit != '0') && (((digit - '0') % 3) == 0);
    }
  };

int main()
  {
  cout << "The value of pi to " << (pi.length() - 2) << " decimal places is\n"
       << pi
       << "\n\n";

  // Here we create a named instance of the class (its name is "db3")
  divisible_by_three db3;

  cout << "The number of digits evenly divisible by 3 is "
       << count_if( pi.begin(), pi.end(), db3 )
       << "\n\n";

  // Here we create a temporary instance of the class (it has no name)
  cout << "The number of digits evenly divisible by 3 is "
       << count_if( pi.begin(), pi.end(), divisible_by_three() )
       << "\n\n";

  return 0;
  }

Thanks for using your brain! You rock!

[cppuser]

Ah, now I understand. Thank you Duoas. :) I'll have to get use to this conceptions.