Пользовательский Iterator в С++

Ответ 1

Когда я сделал свой собственный итератор (некоторое время назад), я унаследовал от std:: iterator и задал тип как первый параметр шаблона. Надеюсь, что это поможет.

Для форвардных итераторов user forward_iterator_tag, а не input_iterator_tag в следующем коде.

Этот класс был первоначально взят из класса istream_iterator (и изменен для моего собственного использования, чтобы он больше не напоминал istram_iterator).

template<typename T>
class <PLOP>_iterator
         :public std::iterator<std::input_iterator_tag,       // type of iterator
                               T,ptrdiff_t,const T*,const T&> // Info about iterator
{
    public:
        const T& operator*() const;
        const T* operator->() const;
        <PLOP>__iterator& operator++();
        <PLOP>__iterator operator++(int);
        bool equal(<PLOP>__iterator const& rhs) const;
};

template<typename T>
inline bool operator==(<PLOP>__iterator<T> const& lhs,<PLOP>__iterator<T> const& rhs)
{
    return lhs.equal(rhs);
}

Проверьте эту документацию на тегах итератора:
http://www.sgi.com/tech/stl/iterator_tags.html

Просто перечитав информацию об итераторах:
http://www.sgi.com/tech/stl/iterator_traits.html

Это старый способ делать вещи (iterator_tags), более современный подход - настроить iterator_traits < > для вашего итератора, чтобы он полностью совместим с STL.

Ответ 2

Если у вас есть доступ к Boost, использование iterator_facade является самым надежным решением и довольно простым в использовании.

Ответ 3

Сначала немного обобщаем:

typedef int value_type;
typedef std::vector<value_type*> inner_range;
typedef std::vector<inner_range*> outer_range;

Теперь итератор:

struct my_iterator : std::iterator_traits<inner_range::iterator> 
{
    typedef std::forward_iterator_tag iterator_category;

    my_iterator(outer_range::iterator const & outer_iterator, 
                outer_range::iterator const & outer_end)
    : outer_iterator(outer_iterator), outer_end(outer_end)
    { 
        update();
    }

    my_iterator & operator++()
    {
        ++inner_iterator;
        if(inner_iterator == inner_end)
        {
            ++outer_iterator;
            update();
        }
        return *this;
    }

    reference operator*() const
    {   
        return *inner_iterator;
    }

    bool operator==(my_iterator const & rhs) const
    {   
        bool lhs_end = outer_iterator == outer_end;
        bool rhs_end = rhs.outer_iterator == rhs.outer_end;
        if(lhs_end && rhs_end)
            return true;
        if(lhs_end != rhs_end)
            return false;
        return outer_iterator == rhs.outer_iterator 
            && inner_iterator == rhs.inner_iterator;
    }

private:

    outer_range::iterator outer_iterator, outer_end;
    inner_range::iterator inner_iterator, inner_end;

    void update()
    {
        while(outer_iterator != outer_end)
        {
            inner_iterator = (*outer_iterator)->begin();
            inner_end = (*outer_iterator)->end();
            if(inner_iterator == inner_end)
                ++outer_iterator;
            else
                break;
        }
    }    
};

Этот класс предполагает, что внешние итераторы содержат указатели на внутренние диапазоны, что и требовалось в вашем вопросе. Это отражается в элементе update, в стрелках до begin() и end(). Вы можете заменить эти стрелки точками, если вы хотите использовать этот класс в более распространенной ситуации, когда внешний итератор содержит внутренние диапазоны по значению. Обратите внимание на то, что этот класс агностически связан с тем, что внутренний диапазон содержит указатели, только клиенты этого класса должны знать это.

Код может быть короче, если мы используем boost::iterator_facade, но нет необходимости добавлять зависимость boost для чего-то такого простого. Кроме того, единственными сложными частями являются операции равенства и приращения, и мы все равно должны их кодировать.

Я оставил следующие члены котельной пластины как "упражнения для читателя":

• postfix increment iterator
• оператор!=
• конструктор по умолчанию
• operator- >

Еще одно интересное упражнение - превратить это в шаблон, который работает с произвольными контейнерами. Код в основном тот же, за исключением того, что вы должны добавить аннотации typename в нескольких местах.

Пример использования:

int main()
{
    outer_type outer;
    int a = 0, b = 1, c = 2;
    inner_type inner1, inner2;
    inner1.push_back(&a);
    inner1.push_back(&b);
    inner2.push_back(&c);
    outer.push_back(&inner1);
    outer.push_back(&inner2);

    my_iterator it(outer.begin(), outer.end());
                e(outer.end(), outer.end());
    for(; it != e; ++it)
        std::cout << **it << "\n";
}

Какие принты:

0 1 2

Ответ 4

Итератор - это просто класс, поддерживающий определенный интерфейс. Как минимум, вы захотите иметь возможность:

• приращение и/или уменьшение его
• разыщите его, чтобы получить объект, который он "указывает" на
• проверить его на равенство и неравенство
• скопируйте и назначьте его

Как только у вас есть класс, который может сделать это разумно для вашей коллекции, вам нужно будет изменить коллекцию, чтобы иметь функции, возвращающие итераторы. Как минимум вы захотите

• функция begin(), которая возвращает экземпляр вашего нового типа итератора, расположенный в первом элементе
• функция end(), которая возвращает итератор, который (возможно, по определению) помещается в один конец конца элементов в вашем контейнере

Ответ 5

Отметьте Библиотека шаблонов просмотров.

Особенно проверьте

• Union View, представляющий два контейнера, конкатенированные.
• Конкатенационный просмотр, представляющий коллекцию контейнеров, конкатенированных.

Ответ 6

Это самый простой код, который я смог создать (для пользовательских итераторов). Заметьте, что я только начинаю изучать эту область. Это вызывает встроенную функцию upper_bound для выполнения двоичного поиска по целочисленной функции, x^2 в качестве примера.

#include <algorithm>
#include <iostream>

using namespace std;

class Iter
{
  public:
  int x;
  Iter() { x = -1; }
  Iter(int a) { x = a; }

  bool operator!=(Iter &i2) const { return x != i2.x; }
  void operator++() { x++; }
  void operator+=(int b) { x += b; }
  int operator-(const Iter &i2) const { return x - i2.x; }
  int operator*() const {
    cout << "calculating for x " << x << endl;
    return x*x;
  }

  typedef random_access_iterator_tag iterator_category;
  typedef int value_type;
  typedef int difference_type;
  typedef int* pointer;
  typedef int& reference;
};

main ()
{
  ios::sync_with_stdio(false);
  cout << upper_bound(Iter(0), Iter(100), 40).x << endl;
}

// :collapseFolds=1:folding=explicit:

И вот как выглядит результат:

calculating for x 50
calculating for x 25
calculating for x 12
calculating for x 6
calculating for x 9
calculating for x 8
calculating for x 7
7