Why doesn't my custom iterator work with the STL copy?

Question

I wrote an OutputIterator for an answer to another question. Here it is:

#include <queue>

using namespace std;

template< typename T, typename U >
class queue_inserter {
    queue<T, U> &qu;  
public:
    queue_inserter(queue<T,U> &q) : qu(q) { }
    queue_inserter<T,U> operator ++ (int) { return *this; }
    queue_inserter<T,U> operator * () { return *this; }
    void operator = (const T &val) { qu.push(val); }
};

template< typename T, typename U >
queue_inserter<T,U> make_queue_inserter(queue<T,U> &q) {
    return queue_inserter<T,U>(q);
}

This works great for this little copy function:

template<typename II, typename OI>
void mycopy(II b, II e, OI oi) {
    while (b != e) { *oi++ = *b++; }
}

But it doesn't work at all for the STL copy from algorithms. Here are the wonderful C++ errors I get:

i.cpp:33: error: specialization of ‘template<class _Iterator> struct std::iterator_traits’ in different namespace
/usr/include/c++/4.0.0/bits/stl_iterator_base_types.h:127: error:   from definition of ‘template<class _Iterator> struct std::iterator_traits’
/usr/include/c++/4.0.0/bits/stl_algobase.h: In function ‘_OI std::__copy_aux(_II, _II, _OI) [with _II = int*, _OI = queue_inserter<int, std::deque<int, std::allocator<int> > >]’:
/usr/include/c++/4.0.0/bits/stl_algobase.h:335:   instantiated from ‘static _OI std::__copy_normal<true, false>::copy_n(_II, _II, _OI) [with _II = __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, _OI = queue_inserter<int, std::deque<int, std::allocator<int> > >]’
/usr/include/c++/4.0.0/bits/stl_algobase.h:387:   instantiated from ‘_OutputIterator std::copy(_InputIterator, _InputIterator, _OutputIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, _OutputIterator = queue_inserter<int, std::deque<int, std::allocator<int> > >]’
i.cpp:53:   instantiated from here
/usr/include/c++/4.0.0/bits/stl_algobase.h:310: error: no type named ‘value_type’ in ‘struct std::iterator_traits<queue_inserter<int, std::deque<int, std::allocator<int> > > >’
/usr/include/c++/4.0.0/bits/stl_algobase.h:315: error: no type named ‘value_type’ in ‘struct std::iterator_traits<queue_inserter<int, std::deque<int, std::allocator<int> > > >’
/usr/include/c++/4.0.0/bits/stl_algobase.h:315: error: ‘__value’ is not a member of ‘<declaration error>’
/usr/include/c++/4.0.0/bits/stl_algobase.h:335:   instantiated from ‘static _OI std::__copy_normal<true, false>::copy_n(_II, _II, _OI) [with _II = __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, _OI = queue_inserter<int, std::deque<int, std::allocator<int> > >]’
/usr/include/c++/4.0.0/bits/stl_algobase.h:387:   instantiated from ‘_OutputIterator std::copy(_InputIterator, _InputIterator, _OutputIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, _OutputIterator = queue_inserter<int, std::deque<int, std::allocator<int> > >]’
i.cpp:53:   instantiated from here
/usr/include/c++/4.0.0/bits/stl_algobase.h:317: error: ‘__simple’ is not a valid template argument for type ‘bool’ because it is a non-constant expression
/usr/include/c++/4.0.0/bits/stl_algobase.h:317: error: ‘copy’ is not a member of ‘<declaration error>’

Here is the driver:

int main() {
    vector<int> v;
    v.push_back( 1 );
    v.push_back( 2 );
    queue<int> q;
    copy( v.begin(), v.end(), make_queue_inserter(q) );
    while (q.size() > 0) {
        cout << q.front() << endl;
        q.pop();
    }
}

Why in the world is it specializing iterator_traits. What's wrong with my iterator? Can't I just write my own simple iterators?

And how should the algorithm know what _kind_ of iterator it is? Eg, the algorithm may run faster with Random Access Iterators, but how does it know if your iterator is random access or not? — Mooing Duck, Sep 22 '11 at 20:30
Because all your iterators should start like this `struct queue_inserter : boost::iterator_facade<...> {...` — alfC, Oct 21 '15 at 05:55
@alfC: FWIW, I just tried writing a simple OutputIterator with `boost::iterator_facade` and immediately ran into trouble. http://stackoverflow.com/questions/43481025 Since the OP was *also* trying to make an OutputIterator, "`iterator_facade` solves all your problems by magic" isn't useful advice. Turns out, `iterator_facade` *creates* some problems of its own. (Still should probably use it, but it's not a one-line answer. It's a multi-line answer with several caveats and hopefully an example.) — Quuxplusone, Apr 18 '17 at 19:55

Naveen · Accepted Answer · 2009-11-12T18:16:38.000

18

Your queue_inserter needs to be derived from std::iterator so that all the typedefs such as value_type are properly defined since these are used inside STL algorithms This definition works:

template< typename T, typename U >
class queue_inserter : public std::iterator<std::output_iterator_tag, T>{
    queue<T, U> &qu;  
public:
    queue_inserter(queue<T,U> &q) : qu(q) { }
    queue_inserter<T,U> operator ++ (int) { return *this; }
    queue_inserter<T,U> operator ++ () { return *this; }
    queue_inserter<T,U> operator * () { return *this; }
    void operator = (const T &val) { qu.push(val); }
};

edited Nov 12 '09 at 18:16

answered Nov 12 '09 at 17:40

Naveen

74,600
47
176
233

1

It's amazing how poorly the STL was designed. I thought the whole point of iterators was that I could roll my own? Does `char*` inherit from std::iterator? But thanks for the info. :-) – Frank Krueger Nov 12 '09 at 17:45
5

You can still get around by not deriving..(I haven't tried it though), but you need to all those typedefs yourself. – Naveen Nov 12 '09 at 17:48
3

@Frank Krueger: How would you design the algorithms of the standard library to work efficiently if they can't determine the properties of the types that they need to operate on? It's not a trivial problem. std::iterator_traits is specialized by the implementation for pointer types so that these can be used with algorithms without any further work on the part of the user. – CB Bailey Nov 12 '09 at 18:07
Actually, the iterator type should be`std::output_iterator_tag`, bidirectional implies that `operator--()` is defined. – rcollyer Nov 12 '09 at 18:17
1

@Frank: Thats a poorly though out comment. The way iterators are designed is a very common technique used in C++ to pass type information around when using templates. Just do a quicj search for traits and I am sure you find appropriate articles on it. Note: The algorithms use traits. For the pointer types (like char*) they are explicitly defined for class objects they point back at the type for the required information. All very basic stuff. – Martin York Nov 12 '09 at 19:42
2

But are __typedefs__ inherited that way? I am getting confused between this answer and another answer at SO ([link](http://stackoverflow.com/a/1643190/1019491)). – Hindol Oct 01 '12 at 13:32
FYI @Hindol, inheriting from `std::iterator` *will* give your child class those member typedefs. [(link)](http://stackoverflow.com/questions/1643035/propagating-typedef-from-based-to-derived-class-for-template/1643190#1643190) is saying that even though the child *has* those typedefs, the child can't actually *use them internally itself* (e.g. to declare `reference operator*() const`); that's solely *because the child is a template*. The typedefs are in a sense "only visible to outsiders", unless the child jumps through some hoops to gain access to them itself. – Quuxplusone Apr 18 '17 at 20:00

grigy · Answer 2 · 2009-11-12T17:48:35.220

8

Derive it from std::iterator. If you are interested the Dr. Dobb's has an article about custom containers and iterators.

edited Nov 12 '09 at 17:48

answered Nov 12 '09 at 17:42

grigy

6,696
12
49
76

CB Bailey · Answer 3 · 2009-11-12T18:05:55.107

6

Your iterator doesn't meet the requirement for an 'assignable' type which is a requirement for an output iterator because it contains a reference and assignable types need to ensure that after t = u that t is equivalent to u.

You can provide a suitable specialization for iterator_traits for your iterator either by deriving from a specialization of std::iterator or by providing one explicitly.

namespace std
{
    template<> struct iterator_traits<MyIterator>
    {
        typedef std::output_iterator_tag iterator_category;
        typedef void value_type;
        typedef void difference_type;
    };
}

edited Nov 12 '09 at 18:05

answered Nov 12 '09 at 17:55

CB Bailey

755,051
104
632
656

Thanks for giving me the curiosity to know more about `iterator_traits`! Never knew it before. Although an explicit specialization of `iterator_traits` isn't needed. See my answer :) – legends2k Sep 22 '11 at 20:16
`iterator_traits`, `char_traits`, `pointer_traits;`, `regex_traits`, and `allocator_traits` too! There's also an `` include, but that's completely unrelated. – Mooing Duck Sep 22 '11 at 20:28

legends2k · Answer 4 · 2015-01-11T14:29:01.423

#include <queue>
#include <algorithm>
#include <iterator>
#include <iostream>

using namespace std;

template< typename T, typename U >
class queue_inserter
{
    queue<T, U> &qu;

public:
    // for iterator_traits to refer
    typedef output_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;

    queue_inserter(queue<T,U> &q) : qu(q) { }
    queue_inserter<T,U>& operator ++ () { return *this; }
    queue_inserter<T,U> operator * () { return *this; }
    void operator = (const T &val) { qu.push(val); }
};

template< typename T, typename U >
queue_inserter<T,U> make_queue_inserter(queue<T,U> &q)
{
    return queue_inserter<T,U>(q);
}

int main()
{
    // uses initalizer list (C++0x), pass -std=c++0x to g++
    vector<int> v({1, 2, 3});
    queue<int, deque<int>> q;
    copy(v.cbegin(), v.cend(), make_queue_inserter(q));
    while (!q.empty())
    {
        cout << q.front() << endl;
        q.pop();
    }
}

This should do it with iterator_traits; a helper struct in <iterator> which defines all types an iterator should typically define. Functions in <algorithm>, refer to these types when required like iterator_traits<it>::iterator_category or say iterator_traits<it>::value_type, etc. Just defining them inside one's custom iterator would do the trick. This is the modern way of writing iterators, as opposed to the classical way of inheriting from std::iterator. Having a look at <iterator> reveals that even std::iterator defines these types i.e. iterator_category, difference_type, etc. This is the reason, when inherited from std::iterator, the derived iterator class gets these due to heredity.

Why is inheriting from `std::iterator` obsolete and where I can find more about how to do it the right way then? — SasQ, Dec 13 '12 at 03:03
Please see [this answer](http://stackoverflow.com/a/8054856/183120) for details. And sorry for the very late reply, didn't know you'd asked. — legends2k, Jan 11 '15 at 15:03

Why doesn't my custom iterator work with the STL copy?

4 Answers4

Linked