6

Возможно, кто-либо может объяснить итераторы и их использование с массивами, или же дать соответствующую литературу по этой теме?

Т.к. я читал по разным книгам о итераторах, но там идет речь о использовании их совместно с STL и т.п., а как самому написать - особо такого не написано... Насколько я понял, то они нужны, чтобы перебирать и т.п. элементы массива. Я правда не знаю смысл в этом, если вроде бы можно и непосредственно обращаться, ну да ладно, не важно. Т.е. нужно создать вложенный класс внутри класса, где будет содержаться, скажем, массив?

Если я понял, то в конце концов, когда он написан, то, к примеру, для цикла выведения массива будет такой код:

for(start = Iterator.begin(); start != end; start++)
{
    cout << *start;
}

Или я что-то путаю?

P.S.: А ещё, если у кого есть книги, где об этом говорится, статьи, то пожалуйста и их напишите тоже сюда.


class Array
{
private:
    int* p;
public:
    class Iterator
    {
        public:
        Iterator()  
        {
            p = nullptr;
        }
        Iterator(int *pv)
        {
            p = pv;
        }
        int operator *() const
        {
            return *p;
        }
        Iterator operator ++(int)
        {
            int *temp = p;
            return ++temp;
        }
    };

    Array();
    ~Array();
int& operator[] ();
    Iterator begin()
    {
        return Iterator(buffer_)
    }
int* buffer_;

void partial_sort(Array::Iterator start, Iterator end)
{
    start
}

Вот как понять что-то вроде этого... Точнее говоря это наброски, они не совсем мои.. Вот мне нужно сделать примерно такое же, только работающее..


Если говорить поконкретнее насчёт того, что не понимаю...
Вот класс итератор вложенный, в нем какое поле должно быть ?
При перегрузке Iterator operator ++(int) это он типо должен будет перебирать элементы массива же, да?
А если я хочу перегрузить ==?
Я пробовал писать что-то вроде:

Iterator operator==(Iterator it1, Iterator it2)

Чтобы сравнивать их на равенство, но не получается - ошибка "много аргументов".
ДА и ещё не до конца понимаю как его реализовать..
Т.е. допустим функции вывода, сортировок вместо того, чтобы передавать массив и его длину мне нужно будет передавать 2 итератора, верно? Один из них указывает на начало, другой на конец, да?
А вывод массива в таком случае выглядел бы с итераторами так:

for(start ???; start != end; start++)
  cout << *start;
8
  • 2
    Вот книга Шилдта страница №808 и далее там про это говорится.[Ссылка на файл][2] [2]: sourse.my1.ru/shildt-cpp.rar
    – user1757
    14 мая 2011 в 18:35
  • 1
    Спасибо за книгу Шилдта, но... простите, вы случаем не описались страниецй? - Там просто всего страниц 791.
    – Daniel
    14 мая 2011 в 19:47
  • Для справки: Я читал про итераторы (соответствующие главы) в книгах: Лафоре, Шилдта, Лаптева, Дейтела, Прата, Страуструпа, Савич... Нигде именно того, что подошло бы мне, к сожалению, не нашлось...
    – Daniel
    14 мая 2011 в 19:51
  • Эх... Если бы было так просто нагуглить - я бы не задавал вопрос) Википедия это было пожалуй первое, что я прочёл)
    – Daniel
    14 мая 2011 в 21:52
  • 1
    Самый простой пример кода таков - sourcemaking.com/design_patterns/iterator/cpp/2
    – gecube
    15 мая 2011 в 12:03

6 ответов 6

7

Вот, собственно, пример итератора. Этот код вырезан из SGI STL, почищен от всяких подробностей, чтобы оставить суть. Тут можно посмотреть что и как в итераторах должно быть в принципе:

#include <cstddef> // нужен только лишь для типа std::size_t

class iterator
{
protected:
  int* p;

public:
  explicit iterator(int* __i) : p(__i) { }

  // Forward iterator requirements
  const int& operator*() const
  { return *p; }

  int& operator*()
  { return *p; }

  int* operator->() const
  { return p; }

  // prefix increment (++it)
  iterator& operator++() {
      ++p;
      return *this;
  }

  // postfix increment (it++)
  iterator operator++(int)
  { return iterator(p++); }

  // Bidirectional iterator requirements

  // prefix decrement (--it)
  iterator& operator--() {
      --p;
      return *this;
  }

  // postfix decrement (it--)
  iterator operator--(int)
  { return iterator(p--); }

  // Random access iterator requirements
  const int& operator[](const std::size_t& __n) const
  { return p[__n]; }

  int& operator[](const std::size_t& __n)
  { return p[__n]; }

  iterator& operator+=(const std::size_t& __n)
  { p += __n; return *this; }

  iterator operator+(const std::size_t& __n) const
  { return iterator(p + __n); }

  iterator& operator-=(const std::size_t& __n)
  { p -= __n; return *this; }

  iterator operator-(const std::size_t& __n) const
  { return iterator(p - __n); }

  int* base() const { return p; }
};

// Forward iterator requirements
inline bool
operator==(const iterator& __lhs, const iterator& __rhs)
{ return __lhs.base() == __rhs.base(); }

inline bool
operator!=(const iterator& __lhs, const iterator& __rhs)
{ return __lhs.base() != __rhs.base(); }

// Random access iterator requirements
inline bool
operator<(const iterator& __lhs,
      const iterator& __rhs)
{ return __lhs.base() < __rhs.base(); }

inline bool
operator>(const iterator& __lhs, const iterator& __rhs)
{ return __lhs.base() > __rhs.base(); }

inline bool
operator<=(const iterator& __lhs, const iterator& __rhs)
{ return __lhs.base() <= __rhs.base(); }

inline bool
operator>=(const iterator& __lhs, const iterator& __rhs)
{ return __lhs.base() >= __rhs.base(); }

inline std::size_t
operator-(const iterator& __lhs, const iterator& __rhs)
{ return __lhs.base() - __rhs.base(); }

inline iterator
operator+( std::size_t __n, const iterator& __i)
{ return iterator(__i.base() + __n); }

Обратите внимание на explicit конструктор, на то какие операторы перегружены для того, чтобы итератор удовлетворял концепциям:

  • forward iterator
  • random access iterator
  • bidirectional iterator
1
  • Спасибо, будут разбираться.
    – Daniel
    16 мая 2011 в 12:20
2

Итераторы призваны предоставлять доступ к членам контейнеров, они могут быть использованы способом, похожим на манипуляции указателями. Например, можно использовать итератор для прохода по всем элементам вектора. Есть несколько разных типов итераторов.

Каждый класс контейнеров связан с типом итератора, и каждый из алгоритмов STL использует определенный тип итератора.

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

Код в примере создает итератор и использует его в векторе:

    vector<int> the_vector;
    vector<int>::iterator the_iterator;

    for( int i=0; i < 10; i++ ) 
       the_vector.push_back(i);
    int total = 0;
    the_iterator = the_vector.begin();
    while( the_iterator != the_vector.end() ) {
      total += *the_iterator;
      ++the_iterator;
    }

    cout << "Итого=" << total << endl;

Получить доступ к элементам контейнера можно путем разыменования итератора.

1
  • Спасибо за объяснения) Но опять таки... Дело в том, что мне не STL, мне нужно написать итератор для массива...
    – Daniel
    14 мая 2011 в 19:49
2

Массив - это конкретная форма хранения данных. Отличается тем, что у нас есть числовой индекс у каждого элемента. Причем этот индекс уникален. Обычно эти индексы представляют собой целые числа от некоего минимального до некоего максимального с каким-то фиксированным шагом.

int a[100];

for (int i = 0; i < 100; i++)
{
    std::cout<<a[i]; //вывести на экран i-тый элемент массива
}

Когда стандартный массив начинает не устраивать, то можно сделать специальный класс, который будет перегружать оператор [] и будет выглядеть как массив. Но при этом внутренняя структура может быть, например, связанным списком или еще чем-то более хитрым. Все зависит от задач.

Далее - никто не мешает перегрузить этот оператор так, чтобы он принимал, например, строчку. Это удобно для создания структур данных типа словаря. Наличие численных индексов становится уже необязательно.

Но при этом в любом случае возникает задача обеспечения возможности поэлементного перебора элементов такого "массива". Вот тут-то и появляется итератор. Это некая штука, которая знает как перебирать элементы. Опять же внутренняя реализация нас, как пользователя, не волнует. А с точки зрения разработчика мы можем ее сделать оптимизированной под конкретную задачу. Итераторы бывают разных типов: пассивные, активные - в зависимости от того как они соотносятся с классом, для которого используются. Об этом всем хорошо написано в книжке Джеффа Элджера "C++.Библиотека программиста", изд. Питер.

PS: в качестве типа массива в свежих компиляторах я бы рекомендовал использовать шаблонный тип std::array.

5
  • А можно многабукаф превратить во что то более читабельное? И поподробнее про итераторы? 14 мая 2011 в 18:58
  • Не понял. А что с сообщением случилось? Глюки форматирования, что ли?
    – gecube
    14 мая 2011 в 19:25
  • Прочёл, спасибо конечно, но вот насчёт: "PS: в качестве типа массива в свежих компиляторах я бы рекомендовал использовать шаблонный тип std::array." В том то и дело - нужно написать самому итератор.. Т.е. у меня есть класс, есть вложенный класс Iterator, мне и нужно этот итератор написать и использовать его... (я буду при сортировках использовать, при выводе на экран и т.п.) (т.е. нужно будет ещё перегрузить несколько операций, как я понимаю)
    – Daniel
    14 мая 2011 в 19:45
  • ОК, сейчас намутим пример.
    – gecube
    14 мая 2011 в 20:37
  • Спасибо) Буду ждать)
    – Daniel
    14 мая 2011 в 21:14
2

В принципе итератор, это просто расширенная концепция указателя и все алгоритмы STL, работающие с итераторами должны работать и с указателями напрямую:

#include <stdio.h>
#include <algorithm>

void go( int value )
{
    printf("%d\n", value);
}

int main()
{
    int a[5] = { 0, 1, 2, 3, 4 };
    std::for_each( &a[0], &a[5], &go );
    return 0;
}
1
class MyIterator;
class MyArray{
public:
    MyIterator* Iterate();  // возвращает пассивный итератор, index в 0.
    bool More(MyIterator*); // true если еще есть элементы, иначе - false
    int Next(MyIterator*);  // возвратим текущий элемент массива, index++
    ...
};
class MyIterator
{
     int index;  // здесь мы будем хранить номер текущего элемента
     // для конкретного итератора, т.к. итераторов мы можем завести много.
     ...
}

MyArray* collection = new MyArray(100);// сделаем-ка массив на 100 элементов,
// для этого конструктор коллекции должен принимать кол-во элементов
...
MyIterator* iter = collection->Iterate(); //сделаем итератор
... 
while (collection->More(iter)) // пока еще есть элементы
    std::cout<<collection->Next(iter)<<std::endl; // выведем текущий элемент.

Криво, но похоже на правду.

2
  • Контейнер (класс, описывающий массив) предлагаю описать самому.
    – gecube
    14 мая 2011 в 21:19
  • Спасибо, уже попонятнее стало с одной стороны... Ну вот я добавил в вопрос, точнее отредактировал своё первое сообщение (собственно сам вопрос)...
    – Daniel
    14 мая 2011 в 22:14
-2

Есть классная книга: "С++. Методики программирования Шилдта". там примерно половина посвящена итераторам

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.