string iterators--Accelerated C++ example

I can't get the following code from Accelerated C++ to work. It seems to be a problem with the string interators being passed to the find_if() <algorithm>. The error says the iterator arguments are ambiguous: they could be char* or const char*:

Code:

#include <iostream>
#include <string>
#include<vector>
#include <algorithm>

using namespace std;

bool space(char ch)
{
	//if ch is a space, returns true:
	return isspace(ch)?true:false;
}

bool not_space(char ch)
{
	//if ch is not a space, returns true:
	return isspace(ch)?false:true;
}

int main()
{
	string str = "Although functors and predicates are cool, you"
		"should be very careful when writing unary and binary functors."
		"Except when used with the std::for_each algorithm, the context"
		"they hold should be constant.";

	vector<string> words;

	string::const_iterator i = str.begin();
	string::const_iterator j = 0;
	
	while(i != str.end())
	{
		i = find_if(i, str.end(), not_space); //error

		//rest of code
	}


	return 0;
}

C:\Beginning C++\test2\main.cpp(37) : error C2782: '_II __cdecl std::find_if(_II,_II,_Pr)' : template parameter '_II' is ambiguous
could be 'char *'
or 'const char *'

I can get find_if() to work with non-const iterators:

string::iterator i = str.begin();
string::iterator j = 0;

So, find_if() won't take const_iterator arguments, which doesn't make much sense to me: find_if() is a templated function, and find_if() doesn't change what it's iterating over.

Yes I noticed that to. I don't know what to say. The error I get on GCC is there is no matching function call and that find_if takes a normal_iterator.

35 C:\Dev-Cpp\boardCode\7stud.cpp no matching function for call to `find_if(__gnu_cxx::__normal_iterator<const char*, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >&, __gnu_cxx::__normal_iterator<char*, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, int (&)(char))'

So maybe find_if only takes a non const iterator?

Originally Posted by prog-bman

Yes I noticed that to. I don't know what to say. The error I get on GCC is there is no matching function call and that find_if takes a normal_iterator.

35 C:\Dev-Cpp\boardCode\7stud.cpp no matching function for call to `find_if(__gnu_cxx::__normal_iterator<const char*, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >&, __gnu_cxx::__normal_iterator<char*, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, int (&)(char))'

So maybe find_if only takes a non const iterator?

Thanks for taking a look. That's the conclusion I came to as well, although I can't figure out why that should be the case.

There's some errata for the book online, and I looked through it, but I didn't see that error mentioned.

Well. That must be wrong according to the standard if I am reading this right.

template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

1 Requires: Type T is EqualityComparable (20.1.1).

2 Returns: The first iterator i in the range [ first, last) for which the following corresponding conditions hold: *i == value, pred(*i) != false. Returns lastif no such iterator is found.

3 Complexity: At most last first applications of the corresponding predicate.

20.1.1 Equality comparison

1 In Table 28, T is a type to be supplied by a C + + program instantiating a template, a, b and c are values of type T.

Table 28.
-------------------------------------------------------------------------------------

EqualityComparable requirements expression return type requirement

a == b convertible to bool == is an equivalence relation,that is, it satisfies the following properties:

For all a, a == a.

If a == b, then b == a.

If a == b and b == a, then a == c.
-------------------------------------------------------------------------------------

The way I take that if the first two args are comparible by == then the function should accept them. I tried it and a const_iterator and str.end() are comparable by == so it should work.

>There's some errata for the book online, and I looked through it, but I didn't see that error mentioned.
That's because it's not an error in the book. It's an error in how you interpreted the book. They're using a function that takes a reference to const string, yet your translation doesn't take that into account and uses a non-const string instead. Try this:

Code:

#include <iostream>
#include <string>
#include<vector>
#include <algorithm>

using namespace std;

bool space(char ch)
{
  //if ch is a space, returns true:
  return isspace(ch)?true:false;
}

bool not_space(char ch)
{
  //if ch is not a space, returns true:
  return isspace(ch)?false:true;
}

int main()
{
  const string str = "Although functors and predicates are cool, you"
    "should be very careful when writing unary and binary functors."
    "Except when used with the std::for_each algorithm, the context"
    "they hold should be constant.";

  vector<string> words;

  string::const_iterator i = str.begin();
  string::const_iterator j = 0;

  while(i != str.end())
  {
    i = find_if(i, str.end(), not_space); //error

    //rest of code
  }

  return 0;
}

Yes, you're right: the book uses that code in a function that takes a const string& parameter. My mistake. In my defense, this is where I was getting the code from:

http://www.awprofessional.com/articl...p?p=25333&rl=1

The code is run together and in miniature type making it very difficult to read.

I still don't understand why making the string a const clears up the ambiguity my compiler is complaining about. Doesn't the compiler try to instantiate a version of the find_if() template based on the arguments I use? Since my arguments are const iterators, doesn't that mean I'm directing the compiler to instantiate a version of find_if() with pointers to const chars?

Code:

	string str = "Although functors and predicates are cool, you"
		"should be very careful when writing unary and binary functors."
		"Except when used with the std::for_each algorithm, the context"
		"they hold should be constant.";

	vector<string> words;

	string::const_iterator i = str.begin();
	string::const_iterator j = 0;
	
	while(i != str.end())
	{
		i = find_if(i, str.end(), not_space); //error

		//rest of code
	}

I think the issue here is that you are using both a const_iterator (i) and a normal iterator (str.end()). The compiler can't decide and gives the ambiguous warning. The solution is either to make both arguments const_iterator, by making the string const so that str.end() yields a const_iterator (as in Prelude's example), or make both arguments normal iterators. The iterator also needs to be advanced (i++) to avoid an endless loop.

Code:

	string str = "It will be a nice day tomorrow!";

	string::iterator i = str.begin();
	
	while(i != str.end())
	{
		i = find_if(i, str.end(), not_space); //error

		//rest of code

		i++;
	}

I think the issue here is that you are using both a const_iterator (i) and a normal iterator (str.end()). The compiler can't decide and gives the ambiguous warning.

I see now: one of my arguments to find_if() is a const char*, namely the const_iterator i, and the other: str.end() is a char*. Since my string is non-const, end() returns a char*. If my string were const, then end() would return a const char* because begin() and end() are overloaded to return a const_iterator when the object is const. So the way I have it now, the compiler doesn't know what version of find_if() to instantiate because the first two arguments are of different types.

Thanks for the explanation.

The solution is either to make both arguments const_iterator, by making the string const so that str.end() yields a const_iterator (as in Prelude's example), or make both arguments normal iterators.

...or assign str.end() to a const interator:

Code:

string:const_iterator end = string.end();
...
...
i = find_if(i, end, not_space);

The iterator also needs to be advanced (i++) to avoid an endless loop.

The iterator is advanced a different way in:

Code:

//the rest of the code

However, I think with iterators you always want to avoid the postfix form and use the prefix form: ++i instead. If you try to write the operator++() and operator++(int) for a class, it's apparent why: the postfix version requires that you create a temporary object, so it's not as efficient.

Here's the full program if anyone is interested(which is from Accelerated C++):

Code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> //for find_if()

using namespace std;

bool space(char ch)
{
	//if ch is a space, returns true:
	return isspace(ch)?true:false;
}

bool not_space(char ch)
{
	//if ch is not a space, returns true:
	return isspace(ch)?false:true;
}


int main()
{
	 string str = "Although functors and predicates are cool, you "
		"should be very careful when writing unary and binary functors. "
		"Except when used with the std::for_each algorithm, the context "
		"they hold should be constant.";

	vector<string> words;  //container for the individual words

	string::const_iterator i = str.begin();
	string::const_iterator j = 0;
	string::const_iterator end = str.end();
	
	while(i != str.end())
	{
		i = find_if(i, end, not_space); //looks for the first character in the string,
						//starting at i and occuring before end
		j = find_if(i, end, space); //looks for the first space after i, which
				            //is the end of the word

		words.push_back(string(i,j));  //uses the string constructor with two
					       //iterators denoting a range of characters
		i=j;  //move i to the end of the word

	}

	//display the words:
	for(int x = 0; x < words.size(); x++)
	{
		cout<<words[x]<<endl;
	}

	//...or the iterator way:
	copy(words.begin(), words.end(), ostream_iterator<string>(cout, "\n") );

	return 0;
}

This post reminded me of another option. Prog-bman posted the prototype for the find_if template function:

Code:

 template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

Now, we can see that if we supply different types for first and last, the compiler will be unable to deduce which type to use for InputIterator, and give the ambiguous warning. However, rather than letting the compiler deduce a type for InputIterator, we can explicitly provide it:

Code:

// i is a string::const_iterator and str.end() is a string::iterator so type can not be deduced...
i = find_if<string::const_iterator>(i, str.end(), not_space);

One could also use a cast.

Code:

	string::const_iterator j = 0;

This line will not compile in Dev-C++/G++:

Code:

   conversion
   from `int' to non-scalar type `__gnu_cxx::__normal_iterator<const char*, 
   std::basic_string<char, std::char_traits<char>, std::allocator<char> > >' 
   requested

Finally, here is a version of the code that removes the need for the space and not_space functions:

Code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>  // for find_if
#include <iterator>   // for ostream_iterator
#include <functional> // for not1
#include <cctype>     // for isspace
using namespace std;

int main()
{
	string str = "Ah, a nice short string.";

	vector<string> words;  // container for the individual words

	string::iterator i = str.begin();
	string::iterator j;
	
	while(i != str.end())
	{
		i = find_if(i, str.end(),                           // looks for the first character in the string,
		            not1(ptr_fun((int (*)(int)) isspace))); // starting at i and occuring before end

		j = find_if(i, str.end(),            // looks for the first space after i, which
		            (int (*)(int)) isspace); // is the end of the word

		words.push_back(string(i,j));  // uses the string constructor with two
					       // iterators denoting a range of characters

		i = j;  // move i to the end of the word
	}

	// display the words:
	for(size_t x = 0; x < words.size(); x++)
	{
		cout << words[x] << endl;
	}

	// ...or the iterator way:
	copy(words.begin(), words.end(), ostream_iterator<string>(cout, "\n") );
}

Originally Posted by anonytmouse

This post reminded me of another option. Prog-bman posted the prototype for the find_if template function:

Code:

 template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

Now, we can see that if we supply different types for first and last, the compiler will be unable to deduce which type to use for InputIterator, and give the ambiguous warning. However, rather than letting the compiler deduce a type for InputIterator, we can explicitly provide it:

Code:

// i is a string::const_iterator and str.end() is a string::iterator so type can not be deduced...
i = find_if<string::const_iterator>(i, str.end(), not_space);

Nice.

Code:

	string::const_iterator j = 0;

This line will not compile in Dev-C++/G++:

Code:

   conversion
   from `int' to non-scalar type `__gnu_cxx::__normal_iterator<const char*, 
   std::basic_string<char, std::char_traits<char>, std::allocator<char> > >' 
   requested

How can you initialize j? Just set it to begin()? That seems like an unnecessary function call.

Finally, here is a version of the code that removes the need for the space and not_space functions:

Code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>  // for find_if
#include <iterator>   // for ostream_iterator
#include <functional> // for not1
#include <cctype>     // for isspace
using namespace std;

int main()
{
	string str = "Ah, a nice short string.";

	vector<string> words;  // container for the individual words

	string::iterator i = str.begin();
	string::iterator j;
	
	while(i != str.end())
	{
		i = find_if(i, str.end(),   // looks for the first character in the string,
		            not1(ptr_fun((int (*)(int)) isspace))); // starting at i and occuring before end

		j = find_if(i, str.end(),   // looks for the first space after i, which
		            (int (*)(int)) isspace); // is the end of the word

		words.push_back(string(i,j));  // uses the string constructor with two
					       // iterators denoting a range of characters

		i = j;  // move i to the end of the word
	}

	// display the words:
	for(size_t x = 0; x < words.size(); x++)
	{
		cout << words[x] << endl;
	}

	// ...or the iterator way:
	copy(words.begin(), words.end(), ostream_iterator<string>(cout, "\n") );
}

Whoa!

ptr_fun((int (*)(int)) isspace))

Ok, the inner part looks like a C-style cast(?? ) of isspace() to a function pointer. Hmmmm...but isn't the name of a function already a pointer to its type, which is already int (*) (int)? I tried it without the casts, and it compiles for me.

Then, I looked up ptr_fun(), and it's an STL "adapter" which uses the function pointer to create a function that the STL not1() function can handle. Whew! That seems like a lot of work. Can that be more efficient?

Why can't the STL just blindly apply the isspace() function to *iterator? isspace() can only handle integer arguments, so it will either work on the range or it won't. Why does the STL need to create a special function object containing isspace() just to negate the return value, which is a fixed type also?

Well because it is C++ that is why if it was simple then everyone could learn it.

Ok, the inner part looks like a C-style cast(?? ) of isspace() to a function pointer. Hmmmm...but isn't the name of a function already a pointer to its type, which is already int (*) (int)? I tried it without the casts, and it compiles for me.

Dev-C++/GCC defines a number of overloaded versions of isspace. The cast tells the compiler which version to use. MSVC doesn't require the cast. A C++ style cast would be preferable.

Why can't the STL just blindly apply the isspace() function to *iterator? isspace() can only handle integer arguments, so it will either work on the range or it won't. Why does the STL need to create a special function object containing isspace() just to negate the return value, which is a fixed type also?

not1 requires a function object so that it can use the typedef provided by the function object for its argument type. Here is the Dev-C++ implementation of unary_negate (not1 just calls the unary_negate constructor):

Code:

template <class _Predicate>
class unary_negate
  : public unary_function<typename _Predicate::argument_type, bool> {
protected:
  _Predicate _M_pred;
public:
  explicit unary_negate(const _Predicate& __x) : _M_pred(__x) {}
  bool operator()(const typename _Predicate::argument_type& __x) const {
    return !_M_pred(__x);
  }
};

This is not particularly inefficient. The function object consists of single function pointer (and a couple of typedefs that don't exist at run-time). It is possible that the compiler optimizes out the function object altogether. Here is the pointer_to_unary_function class (ptr_fun just calls the pointer_to_unary_function constructor):

Code:

template <class _Arg, class _Result>
class pointer_to_unary_function : public unary_function<_Arg, _Result> {
protected:
  _Result (*_M_ptr)(_Arg);
public:
  pointer_to_unary_function() {}
  explicit pointer_to_unary_function(_Result (*__x)(_Arg)) : _M_ptr(__x) {}
  _Result operator()(_Arg __x) const { return _M_ptr(__x); }
};

template <class _Arg, class _Result>
inline pointer_to_unary_function<_Arg, _Result> ptr_fun(_Result (*__x)(_Arg))
{
  return pointer_to_unary_function<_Arg, _Result>(__x);
}

not1 requires a function object so that it can use the typedef provided by the function object for its argument type.

Why can't not1 assume the return type is bool or something convertible to bool? Also, why isn't the unary_negate operator() function's parameter of type Predicate::result_type, i.e. the result of isspace()?