Пользовательский итератор в C ++

Question

У меня есть класс TContainer, который представляет собой совокупность нескольких указателей коллекций stl на класс TItems.

Мне нужно создать итератор для прохождения элементов во всех коллекциях в моем классе TContainer, абстрагирующих клиента от внутренней работы.

Что было бы хорошим способом сделать это? Должен ли я создать класс, который расширяет итератор (если да, какой класс итератора мне следует расширить), должен ли я создать класс итератора, который является совокупностью итераторов?

Мне нужен только итератор FORWARD_ONLY.

I.E, если это мой контейнер:

typedef std::vector <TItem*> ItemVector;
class TContainer {
   std::vector <ItemVector *> m_Items;
};

Каким будет хороший итератор для обхода всех элементов, содержащихся в векторах переменной-члена m_Items.

Answer 1

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

Для прямых итераторов пользователь 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.

Answer 2

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

Answer 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, но нет необходимости добавлять буст-зависимость для чего-то такого простого. Кроме того, единственными сложными частями являются операции равенства и приращения, и мы все равно должны их кодировать.

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

• Постфиксный итератор приращения
• оператор! =
• конструктор по умолчанию
• оператор->

Еще одно интересное упражнение - превратить его в шаблон, который работает с произвольными контейнерами. Код в основном такой же, за исключением того, что вы должны добавить аннотации 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

Answer 4

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

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

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

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

Answer 5

Проверьте Библиотека шаблонов представлений .

Особенно чек

1. Union View с двумя объединенными контейнерами.
2. Представление сцепления , представляющее совокупность соединенных контейнеров.

Answer 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