Can't find predicate 'initial(char)'

[jazcap53]

Hi--

I'm struggling with Stroustrup's "The C++ Programming Language (Special Edition)". In Section 16.3.6 he gives the following code example:
===================

vector<string> fruit;

// put some fruit names in the vector

// remove those starting with the letter 'p'
sort(fruit.begin(), fruit.end());
vector<string>::iterator p1 = find_if(fruit.begin(), fruit.end(), initial('p'));
vector<string>::iterator p2 = find_if(fruit.begin(), fruit.end(), initial_not('p'));
fruit.erase(p1, p2);

===================
Problem: I haven't been able to find (or create) the 'initial' or the 'initial_not' predicates. I've tried #include'ing <vector>, <algorithm>, <string>, and <functional>, but still don't find either one. As I understand it, I *shouldn't* be able to create them myself because I can't modify the STL classes.

Could the problem just be that 'initial' and 'initial_not' are not part of my C++ implementation?
I don't find documentation for them on this (or any other) site.

I'm running Fedora fc8 on an Intel 32-bit machine. The compiler is gcc 4.1.2.

Thanks in advance for any help.

--Andy

[Mitsakos]

I don't think initial() is part of the STL. I might be wrong so if anybody knows about it should correct me.

'initial' and 'initial_not' must be custom made functions.
The find_if takes 3 arguments. An iterator where to start looking from, an iterator where to stop looking and a function that returns a bool value depending on what you want to find.

The initial and initial_not functions will be:

bool initial(string fru){
   if(fru[0] == 'p') return true;
   else return false;
}
bool initial_not(string fru){
   if(fru[0] != 'p') return true;
   else return false;
}

I don't know if you can call it with a parameter from inside the find_if...

Also the second find_if should have as a start iterator the p1. So it can find the first string in fruits that doesn't start with 'p' but it is after the ones that does start with 'p'.


Hope that helps

[Duthomhas]

They must be just a simple example. The only way I could implement it is fairly inefficient and type-specific.

struct initial
  {
  char c;
  initial( char c ): c( c ) { }
  bool operator () ( const std::string& s ) const
    {
    return s.at( 0 ) == c;
    }
  };

struct initial_not
  {
  char c;
  bool b;
  initial_not( char c ): c( c ), b( false ) { }
  bool operator () ( const std::string& s )
    {
    if (!b) b = (s.at( 0 ) == c);
    return b && (s.at( 0 ) != c);
    }
  };

A better algorithm would use template functors and std::not1():

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename Container>
struct initial: public std::unary_function <Container, bool>
  {
  typedef typename Container::value_type value_type;
  value_type value;
  initial( const value_type& value ): value( value ) { }
  bool operator () ( const Container& container ) const
    {
    return *(container.begin()) == value;
    }
  };

int main()
  {
  vector <string> names;
  string s;
  char c;
  vector <string> ::iterator b, e;

  cout << "Enter your list of names. Enter nothing to finish\n> ";
  while (getline( cin, s ) and !s.empty())
    {
    names.push_back( s );
    cout << "> ";
    }
  sort( names.begin(), names.end() );

  do {
    cout << "What starting letter do you wish to find? ";
    getline( cin, s );
    }
  while (cin && s.empty());
  c = s[ 0 ];

  b = find_if(
        names.begin(),
        names.end(),
        initial <string> ( c )
        );
  e = find_if(
        b,
        names.end(),
        not1( initial <string> ( c ) )
        );

  if (b != names.end())
    {
    cout << "Found the following:\n";
    for (; b != e; b++)
      cout << *b << endl;
    }
  else
    cout << "No such item found.\n";

  return 0;
  }

Hope this helps.

[Mitsakos]

Can you please explain a little the template part?
I understood some of the followings but I don't know if they are correct:

struct initial: public std::unary_function <Container, bool>
Creates a struct named initial that will act as a unary function.

typedef typename Container::value_type value_type;
From this point on you will use the name value_type instead of "typename Container::value_type"

value_type value;
You create a new variable named value with type value_type. But why you need the "typename Container::value_type value_type" and not just Container? Isn't it the same as creating an object the same type as the template? Why don't you use Container value ?

initial( const value_type& value ): value( value ) { }
The costructor for the struct

bool operator () ( const Container& container ) const
Overloading the operator (). But why it needs to be "const" ?

return *(container.begin()) == value;
It returns true if the data in container.begin() are the same as the value from the constructor. I suppose we use container.begin() so we can use it in every object that declares a function begin that returns a pointer or iterator type.


Thank you for your time.

[Duthomhas]

You understand it pretty well.

struct initial: public std::unary_function <Container, bool> std::unary_function is a template class (in <functional>) that provides information about its types so that it can be used with the standard algorithms (in this case, count_if()).

In this case, initial::argument_type is the Container's type, and initial::result_type is bool.

This tells us that the object functor takes a 'Container' as argument and returns bool, which is what a predicate does.

typedef typename Container::value_type value_type;
In this case I just did it to relieve having to type a lot, but it also creates a new type: initial::value_type, which is the same as the container's elements' type.

As to why I did this, you need to think about the types of things being used.

The count_if() takes an iterator to a container (vector) and passes the vector's elements (strings) to the initial() object, which returns true if the element is to be counted.

Inside the initial() object, we don't know or care what the outermost container's type is (vector), as we never see or handle it. What we do require, though, is that the predicate argument type is itself some form of container (string). We are interested if the argument container (string) begins with a specific element, whose type is Container::value_type (string::value_type).

In short, a vector <string <char> > is first iterated over its strings with the count_if() algorithm, and each string's first character is tested against a given value:

initial( const value_type& value ): value( value ) { }
We want to be able to specify which value is to be used to test against with each string.

bool operator () ( const Container& container ) const
Always make your functions const if they don't modify the object. No other reason.

return *(container.begin()) == value;
Yes, but I could also have written it other ways:

return container.at( 0 ) == value;

return container[ 0 ] == value;

are also valid. I suppose the last would be most optimal, but the second is the safest. (I forgot to check if the container is empty.)

I'm glad you all are picking this up so well. The STL is very cool, and makes life easier in a lot of ways.

:-)

[Mitsakos]

Thank you very much for the reply.
I thought that the Container::value_type returns string type, but in fact it returns the value_type of the string which is char.
Indeed the STL can make your life alot easier but the same time a lot more difficult until you learn how to use it and its functions.
Thank you again.

[Duthomhas]

Yeah, it scares a lot of people, including otherwise competent programmers. But just like with C++, if you just mess with it a bit it starts to be easier to absorb with a glance.
cout << *(++i) && foo << endl;
What?

:-)

[jazcap53]

Thank you both for your thoughtful replies and the very valuable instruction.