The C++ STL function find() doesn't accept the iterator arguments of a user-defined class

Question

When I pass user-defined iterator arguments in std::find(), the GCC 5.2.1. compiler (on Ubuntu 15.10) gives two error messages:

(1)

/usr/include/c++/5/bits/stl_algo.h:162:34: error: no matching function for call to ‘__iterator_category(Text_iterator&)’
std::__iterator_category(__first));

(2)

/usr/include/c++/5/bits/stl_iterator_base_types.h:204:5: error: no type named ‘iterator_category’ in ‘struct std::iterator_traits’

The error is caused by the line auto p = find(first, last, first_char);, which is inside the find_txt() function. When the line is commented out, the code compiles seamlessly. Here's the code excerpt that causes the errors:

#include "std_lib_facilities.h"//from B. Stroustrup's site

using Line = vector<char>;

class Text_iterator {

    list<Line>::iterator ln; //points to lines
    Line::iterator pos; //points to characters

    public: 
    Text_iterator(list<Line>::iterator ll, Line::iterator pp)
        :ln{ll}, pos{pp} { }
    char& operator*() { return *pos; }
    Text_iterator& operator++();
    bool operator==(const Text_iterator& other) const
        { return ln==other.ln && pos==other.pos; }
    bool operator!=(const Text_iterator& other) const
        { return !(*this==other); }
};

Text_iterator& Text_iterator::operator++()
{
    ++pos;
    if (pos==(*ln).end()) {
    ++ln;
    pos = (*ln).begin();
}
    return *this;
}

Text_iterator find_txt(Text_iterator first, Text_iterator last, const string& s)
{
    if (s.size()==0) return last;// can’t find an empty stringchar first_char = s[0];
    char first_char = s[0];
    while (true) {
        auto p = find(first, last, first_char); //<------------the PROBLEM!!!!!!
        //if (p==last || match(p,last,s)) return p;
        //first = ++p;// look at the next character
    }
}

void ex6()
{
    ;
}


int main()
{
    ex6();
}

I referred to the files mentioned in the error messages:

template<typename _Iterator, typename _Predicate>
    inline _Iterator
    __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
    {
        return __find_if(__first, __last, __pred,
        std::__iterator_category(__first)); //this is line #162 in stl_algo.h
    }

and

template<typename _Iter>
    inline typename iterator_traits<_Iter>::iterator_category
    __iterator_category(const _Iter&)//this is line #204 in stl_iterator_base_types.h
    { return typename iterator_traits<_Iter>::iterator_category(); }

Does the problem lie in auto p = find(first, last, first_char); or in those two GCC library files—that is, stl_algo.h and stl_iterator_base_types.h? What could be the possible ways to handle it?

I was preparing code for doing exercise 6, Chapter 20 of Stroustrup's Programming: Principles and Practice Using C++, 2nd Ed. and got stuck here. The search on the Internet for std::find() problems has been to no avail. None of the questions referred to the iterator arguments to this funtion.

Answer 1

The standard algorithms (including std::find) require that the used iterator meets the requirements of the Iterator concept. Among those requirements is

std::iterator_traits<It> has member typedefs value_type, difference_type, reference, pointer, and iterator_category

According to the error message,

no type named ‘iterator_category’ in ‘struct std::iterator_traits’

which probably refers to std::iterator_traits<Text_iterator>. So, apparently the custom iterator isn't an iterator since it doesn't meet the requirements.

Solution: Specialize std::iterator_traits template for the custom iterator type and define the required member types. Also make sure that other requirements of Iterator are met as well as InputIterator, since that is what std::find requires.

An example specialization:

namespace std {
    template<>
    struct iterator_traits<Text_iterator> {
        typedef ptrdiff_t          difference_type;
        typedef char               value_type;
        typedef char*              pointer;
        typedef char&              reference;
        typedef input_iterator_tag iterator_category;
    };
}