Почему мой пользовательский итератор не работает с копией STL?

Я написал OutputIterator для ответа на другой вопрос . Вот:

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

Это отлично подходит для этой маленькой функции копирования:

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

Но это вообще не работает для STL copy от algorithms. Вот замечательные ошибки C ++, которые я получаю:

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>’

Вот драйвер:

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

Почему в мире это специализируется iterator_traits. Что не так с моим итератором? Разве я не могу просто написать свои простые итераторы?


c++ iterator stl
person Frank Krueger    schedule 12.11.2009    source источник
comment
И как алгоритм должен знать, что это за вид итератора? Например, алгоритм может работать быстрее с итераторами произвольного доступа, но как он узнает, является ли ваш итератор произвольным доступом или нет?   -  person Mooing Duck    schedule 23.09.2011
comment
Потому что все ваши итераторы должны начинаться так struct queue_inserter : boost::iterator_facade<...> {...   -  person alfC    schedule 21.10.2015
comment
@alfC: FWIW, я только что попытался написать простой OutputIterator с boost::iterator_facade и сразу же столкнулся с проблемой. stackoverflow.com/questions/43481025 Поскольку OP также пытался создать OutputIterator, iterator_facade решает все ваши проблемы по волшебству - бесполезный совет. Оказывается, iterator_facade создает собственные проблемы. (По-прежнему, вероятно, следует использовать его, но это не однострочный ответ. Это многострочный ответ с несколькими оговорками и, надеюсь, примером.)   -  person Quuxplusone    schedule 18.04.2017
comment
@Quuxplusone. Да, комментарий - это намек, а не ответ.   -  person alfC    schedule 18.04.2017

Ответы (4)


arrow_upward
18
arrow_downward

Ваш queue_inserter должен быть производным от std::iterator, чтобы все определения типов, такие как value_type, были правильно определены, поскольку они используются внутри алгоритмов STL. Это определение работает:

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); }
};
person Naveen    schedule 12.11.2009
comment
Удивительно, насколько плохо был разработан STL. Я думал, что весь смысл итераторов в том, что я могу катить свои собственные? char* наследуется от std :: iterator? Но спасибо за информацию. :-) - person Frank Krueger; 12.11.2009
comment
Вы все еще можете обойтись, не производя ... (хотя я не пробовал), но вам нужно самостоятельно выполнить все эти typedef. - person Naveen; 12.11.2009
comment
@Frank Krueger: Как бы вы спроектировали алгоритмы стандартной библиотеки для эффективной работы, если бы они не могли определить свойства типов, с которыми им нужно работать? Это нетривиальная проблема. std :: iterator_traits специализируется на реализации для типов указателей, поэтому их можно использовать с алгоритмами без какой-либо дополнительной работы со стороны пользователя. - person CB Bailey; 12.11.2009
comment
Фактически, тип итератора должен бытьstd::output_iterator_tag, двунаправленный означает, что operator--() определен. - person rcollyer; 12.11.2009
comment
@Frank: Это плохой комментарий. Способ создания итераторов - это очень распространенный метод, используемый в C ++ для передачи информации о типе при использовании шаблонов. Просто сделайте быстрый поиск черт характера, и я уверен, что вы найдете об этом соответствующие статьи. Примечание: алгоритмы используют черты характера. Для типов указателей (например, char *) они явно определены для объектов класса, они указывают на тип для получения требуемой информации. Все очень простые вещи. - person Martin York; 12.11.2009
comment
Но наследуются ли typedef таким образом? Я запутался между этим ответом и другим ответом на SO (ссылка). - person Hindol; 01.10.2012
comment
К вашему сведению, @Hindol, наследование от std::iterator предоставит вашему дочернему классу эти определения типов членов. (ссылка) говорит, что даже если у дочернего есть эти typedef, дочерний элемент не может фактически использовать их внутри себя (например, для объявления reference operator*() const); это исключительно потому, что дочерний элемент является шаблоном. Определения типов в некотором смысле видны только посторонним, если только ребенок не перепрыгивает через какие-то препятствия, чтобы получить к ним доступ сам. - person Quuxplusone; 18.04.2017

arrow_upward
8
arrow_downward

Получите его из std :: iterator. Если вам интересно, у доктора Добба есть статья о пользовательских контейнерах и итераторах.

person grigy    schedule 12.11.2009

arrow_upward
6
arrow_downward

Ваш итератор не соответствует требованию для «назначаемого» типа, который является требованием для итератора вывода, поскольку он содержит ссылку, а назначаемые типы должны гарантировать, что после t = u этот t эквивалентен u.

Вы можете предоставить подходящую специализацию для iterator_traits для своего итератора, либо унаследовав специализацию std::iterator, либо указав ее явно.

namespace std
{
    template<> struct iterator_traits<MyIterator>
    {
        typedef std::output_iterator_tag iterator_category;
        typedef void value_type;
        typedef void difference_type;
    };
}
person CB Bailey    schedule 12.11.2009
comment
Спасибо за любопытство узнать больше о iterator_traits! Никогда раньше этого не знал. Хотя явная специализация iterator_traits не требуется. Смотрите мой ответ :) - person legends2k; 23.09.2011
comment
iterator_traits, char_traits, pointer_traits;, regex_traits и allocator_traits тоже! Также есть <type_traits> include, но это совершенно не связано. - person Mooing Duck; 23.09.2011

arrow_upward
4
arrow_downward 

#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();
    }
}

Это должно быть сделано с помощью iterator_traits; вспомогательная структура в <iterator>, которая определяет все типы, которые обычно должен определять итератор. Функции в <algorithm> при необходимости обращаются к этим типам, например, iterator_traits<it>::iterator_category или говорят iterator_traits<it>::value_type и т. Д. Простое определение их внутри собственного итератора поможет. Это современный способ написания итераторов в отличие от классического способа наследования от std::iterator. Взгляд на <iterator> показывает, что даже std::iterator определяет эти типы, то есть итератор_категория, разница_тип и т. Д. Это причина, по которой при наследовании от std::iterator производный класс итератора получает их из-за наследственности.

person legends2k    schedule 22.09.2011
comment
Почему наследование от std::iterator устарело и где я могу найти дополнительную информацию о том, как это сделать правильно? - person SasQ; 13.12.2012
comment
Дополнительные сведения см. В этом ответе. И извините за очень поздний ответ, не знала, что вы спросили. - person legends2k; 11.01.2015