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.

TL;DR: Your `Text_iterator` won't be an iterator just because you name it that way. It doesn't fulfill the requirements placed on the iterator by the standard. — Kuba hasn't forgotten Monica, Dec 08 '16 at 16:35
See also http://stackoverflow.com/questions/1724009/why-doesnt-my-custom-iterator-work-with-the-stl-copy — Mark Ransom, Dec 08 '16 at 16:59

eerorika · Accepted Answer · 2016-12-08T17:01:25.697

11

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;
    };
}

edited Dec 08 '16 at 17:01

answered Dec 08 '16 at 16:31

eerorika

232,697
12
197
326

1

An example of how to specialize `std::iterator_traits` would be useful too, since it's not intuitively obvious. – Mark Ransom Dec 08 '16 at 16:40
@MarkRansom added an example. – eerorika Dec 08 '16 at 16:49
2

Another approach (preferred) is to add nessesary typedefs to iterator itself, if you have access to its code. – Revolver_Ocelot Dec 08 '16 at 17:06
When I added the `typedef` inside the Text_iterator, I got this answer: – Jarisleif Dec 08 '16 at 20:41
/tmp/cc5OjFBw.o: In function `Text_iterator std::__find_if >(Text_iterator, Text_iterator, __gnu_cxx::__ops::_Iter_equals_val, std::input_iterator_tag)': twenty.cpp:(.text._ZSt9__find_ifI13Text_iteratorN9__gnu_cxx5__ops16_Iter_equals_valIKcEEET_S6_S6_T0_St18input_iterator_tag[_ZSt9__find_ifI13Text_iteratorN9__gnu_cxx5__ops16_Iter_equals_valIKcEEET_S6_S6_T0_St18input_iterator_tag]+0x78): undefined reference to `Text_iterator::operator++()' collect2: error: ld returned 1 exit status – Jarisleif Dec 08 '16 at 20:45
1

@Jarisleif if you take a close look at your class definition, you'll find that you didn't define `Text_iterator::operator++()`. The linker is telling you this. – eerorika Dec 08 '16 at 21:32
@user2079303 it was defined in my original file, I just didn't include it in the question code and forgot to add it back together with your tip. Now it compiles seamlessly. – Jarisleif Dec 08 '16 at 21:57

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

1 Answers1