Иттераторы

@taras atavin · Регистрация: 24.11.2009

Студворк — интернет-сервис помощи студентам

Никогда не пользовался, а теперь хочу разобраться. Запостите, пожалуйста ответы на вопросы:
1. Что такое иттераторы?
2. Как их делать?
3. Как ими пользоваться?
4. Каким образом при этом достигается ускорение?

@inter-admin · 23.01.2010, 07:03

настолько лень приложить усилие? http://ru.wikipedia.org/wiki/%... 0%BE%D1%80

@taras atavin · 23.01.2010, 07:42 **[ТС]**

Айси. Иттератор похож на указатель, но в операторах сложения/вычитания и инкремента/декремента проверяет выход за границу контейнера? Если я точно знаю, что у меня динамический массив, то в чём преимущество? Каким образом можно достичь ускорения по сравнению с индексом? Зачем мне вообще что добавлять в начало во время перебора? А если я добавлю хоть что то в динамический массив (даже в конец), то каким образом сохранятся адреса элементов массива? Индекс я могу сравнивать с нулём, что быстрее, а иттератор придётся сравнивать с указателем на вершину, что медленнее. По-моему перенос тормоза со сложения с базой в декремент адреса и всего делов. Подозреваю у себя ошибку. Где она?

Добавлено через 6 минут

C++
1
2
3
4
for (p=c.end(); p; --p)
{
 *p=0;
}

Чем это лучше, чем

C++
1
2
3
4
for (i=n-1; i>=0; --i)
{
 a[i]=0;
}

?

Добавлено через 1 минуту
Я не спорю, а не понимаю и задаю наводящие вопросы.

@Nick Alte · 23.01.2010, 09:42

Итератор похож на указатель, а не на индекс. В приведённом примере ты со своим итератором занулил бы всю доступную память, пока тебя не остановил бы сбой. Многие итераторы не проверяются, проверять их ты должен сам. В данном случае условие надо было написать как p>=c.begin();
Суть итераторов заключается в том, что они ИМИТИРУЮТ поведение указателей на массиве. Причём имитировать это поведение они могут и на других структурах данных - списках, деревьях и т.д. Таким образом ты можешь единообразно работать с разными по своей природе контейнерами, не заморачиваясь деталями их реализации. Аналогично, при разработке своих контейнеров имеет смысл разработать для них итераторы, имеющие такое же поведение.
Эта идея замечательно развивается в понятии обобщённого программирования (см. хелп по <algorithm>). Сделанные в виде шаблонов функции вроде сортировки или перекидывания части элементов используют этот единообразный способ для того, чтобы работать с разными контейнерами. То есть, одна и та же std::sort способна сортировать и vector, и list, и deque, и твой собственный контейнер, если ты озаботился сделать для него совместимые итераторы.

@taras atavin · 27.01.2010, 05:46 **[ТС]**

Сообщение от Nick Alte

всю доступную

Как? При p=c.begin

C++
1
--p

не даст p=NULL? Тогда как этот код вообще выглядит?

C++
1
2
3
4
for (p=c.end(); p>=c.begin(); --p)
{
 *p=0;
}

что ли? Я хотел занулить всю память, отведённую под массив. Как это делается? И как делается сам иттератор?

Добавлено через 2 минуты
Преимущество иттератора именно в универсальности? Не в скорости?

Добавлено через 4 минуты

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class TArray
{
 private:
  double *Data;
  unsigned long int Number;
 public:
  TArray (unsigned long int Number)
  {
   Data=new (Number);
   if (Data)
   {
    this->Number=Number;
   }
   else
   {
    Number=0;
   }
  }
  ~TArray ()
 {
  if (Data)
  {
   delete [] Data;
  }  
 }
 double & operator [] (unsigned long int Index)
 {
  return Data[Index];
 }
};

Как выглядит иттератор для такого контейнера? С проверкой и без?

@zim22 · 27.01.2010, 11:15

Сообщение от taras atavin

1. Что такое иттераторы?

итератор - это паттерн проектирования, который позволяет обойти все элементы агрегата без раскрытия информации о том, как он устроен.

@Aye Aye · 28.01.2010, 04:55

что то типа этого, черт его знает, как правельнее сделать

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <conio.h>
using namespace std;
class TArray{
private:
       double *Data;
       int Number;
public:
       class iterator{
       private:
               double *info;
       public:
              iterator(){info=0;}
              iterator(double *d):info(d){}
              double &operator*()
              {
                     return *info;
              }
              iterator &operator++(int i)
              {
                       this->info++;
                       return *this;
              }
              iterator &operator++()
              {
                       this->info++;
                       return *this;
              }
 
              bool operator!=(const iterator &it)const
              {
                   return !(info==it.info);
              }
              iterator &operator=(const iterator &it)
              {
                       info=it.info;
                       return *this;
              }
        };
        TArray (int Num)
        {
               Data=new double[Num];
               if (Data)
               {
                  Number=Num;
               }
               else
               {
                   Num=0;
               }
        }
        ~TArray ()
        {
                if (Data)
                {
                   delete [] Data;
                }  
        }
        double & operator [] (int Index)
        {
               return Data[Index];
        }
        iterator &begin()
        {
                 iterator *it=new iterator(Data);
                 return *it;
        }
        iterator &end()
        {
                 iterator *it=new iterator(Data + Number);
                 return *(it);
        }
};
 
int main()
{
    TArray a(10);
    for (int i=0;i<10;i++) a[i]=i+i;
    TArray::iterator it;
    
    for (it=a.begin();it!=a.end();it++)
    {
        cout << *it << " ";
    }
    getch();
    return 0;
}

Добавлено через 8 минут
похоже вот так:

C++
1
2
3
4
5
6
7
8
9
10
        iterator begin()
        {
                 iterator it(Data);
                 return it;
        }
        iterator end()
        {
                 iterator it(Data + Number);
                 return it;
        }

поадекватнее будет... хз

@taras atavin · 28.01.2010, 05:01 **[ТС]**

Эйси.
1. Класс иттератора объявляется внутри класса контейнера.
2. В нём делаеются два конструктора: дефолтный и с параметром-указателем.
3. Единственное данное - указатель.
4. Объявляется оператор приведения к ссылке.
Так?

Добавлено через 1 минуту
А что за оператор it?

Добавлено через 2 минуты
А можно в коде оператора-члена, объявленного в иттераторе, получить доступ к полям контейнера? Как?

@Aye Aye · 28.01.2010, 05:18

1-4 все так!!! но это мой собственный пример, в stl контейнирах в С++ итераторы описаны намного сложнее. и служат намного болие широким целям, у Бьерна Страуструпа в "Язык программирования C++" все описано по поводу итераторов и контейнеров.
важно что класс итератора внутри класса контейнера, потму что обычно это все шаблонные классы и класс итератора зависит от класса контейнера. остальное - как придется...

it это не оператор

))) это же обькет - экземпляр класса TArray::iterator.

нельзя!!! никак!!! в этом вся соль, больше абстракции - легче работа. например: ты же понятия не имеешь как устроен итератор стандартного контейнера map, а пользуешься им весьма эфективно! а между тем попробуй посмотри как он устоен - мозг можно поломать. так что не надо рыться в реалезации, надо просто очено точно и эфективно реализовывать интерфейс (доступные пользователю методы и поля данных)

Comprenez-vous?

@taras atavin · 28.01.2010, 05:37 **[ТС]**

Сообщение от Aye Aye

it это не оператор ))) это же обькет - экземпляр класса TArray::iterator

. Извини, не внимательно прочитал.

Сообщение от Aye Aye

нельзя!!! никак!!! в этом вся соль,

В чём же соль? В том что так:

C++
1
2
3
4
5
6
7
8
9
iterator &operator--(int i)
{
 if (info==Data)
 {
  return false;
 }
 --info;
 return *this;
}

нельзя? А как же сделать проверку? Получается, что иттератор массива принципиально отличается от иттератора связного списка: если у тебя список, то p>=c.begin() может дать false даже при p=c.end(); и проверка может быть только в самом операторе декремента:

C++
1
2
3
4
itterator & operator--()
{
 return itterator(info->previus);
}

и ни каких гвоздёв - если элемент первый, то previus=NULL и декремент вернёт NULL, иначе возвращается действительный иттератор, а если у тебя массив, то проверку надо делать в заголовке цикла, а сам иттератор этого сделать не может. Где же универсальность?

Добавлено через 2 минуты

Сообщение от Aye Aye

так что не надо рыться в реалезации

. У меня свои контейнеры и если я не разберусь в реализации, то фиг я смогу пользоваться иттераторами.

Сообщение от Aye Aye

итератор стандартного контейнера map, а пользуешься им весьма эфективно!

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

@Aye Aye · 28.01.2010, 05:38

можно получить только если чрез другие итераторы, как и видно из релизации выше:

C++
1
 TArray::iterator it=a.begin()

вот тут оно и происходит, но не непосредственно, а через функцию iterator TArray::begin(). вот так можно организовать доступ к любому полю контейнера - через еще одну функцию, определенную в классе контейнеа. только лучге не трогать никакие поля, кроме самих непосредственных данных - элементов контейнера, иначе идеология итератора нарушится.

__________________________
для каждого конетейнера свой тип итератора и итераторы не наследуют какой то один базовый класс, а универсатьность есть: она проявлется в том что все функции из <algorithm> могут обрабатывать любые контейнеры, даже C-строки! только я не знаю как это реализовано, и тут не могу помоч

дикремента у итераторов еще не встречал, но врядли это очень плохо...

@taras atavin · 28.01.2010, 05:43 **[ТС]**

Сообщение от Aye Aye

лучге не трогать никакие поля

. Я не собираюсь менять поля. Я вообще считаю, что менять их в иттераторе нельзя, а хочу всего лишь прочитать поле контейнера и сравнить с текущим значением иттератора. Если begin объявлен в контейнере, то как его правильно вызвать в иттераторе? Так:

C++
1
2
3
4
5
6
7
8
9
intterator & operator -- ()
{
 if (info==Begin())
 {
  return itterator (NULL);
 }
 --info;
 return *this; 
}

можно?

@Aye Aye · 28.01.2010, 05:44

C++
1
2
3
4
5
6
7
8
9
iterator &operator--(int i)
{
 if (info==Data)
 {
  return false;//тут нельзя false надо возвращать end(); это стандарт
 }
 --info;
 return *this;
}

я сам запутался, ща все проверю...

@taras atavin · 28.01.2010, 05:47 **[ТС]**

Сообщение от Aye Aye

тут нельзя false надо возвращать end();

end() - действительный иттератор конца контейнера. Если так сделать, то перебор зациклится и никакая проверка вообще не поможет. Уж это то даже я понимаю.

@Aye Aye · 28.01.2010, 05:49

так, вощем проверку на выход за предел допустимого диапозона сам класс итератора не должен предусматривать, в stl контейнерах не предусмотренно, по крайней мере. надо это извне делать
вызывать внутри класса итератора функции-члены класс контейнера не получится.

не зациклится, это для операций поиска делают.

C++
1
2
3
4
5
6
7
8
9
iterator RArray::find (const double key)
{
         //нашли
         return iterator(..)//че тут будт я не уверен, но надо вернуть итератор указывающий на этот элемент
         //не нашли 
         return end();
}
//далее в теле проги ищем
 if (a.find(3.14) == a.end())cout << "нет такого числа в контейнере";

на звание професионала не притендую, помагаю чем могу

))

@taras atavin · 28.01.2010, 05:57 **[ТС]**

Сообщение от Aye Aye

надо это извне делать

. А если это список? Тогда заголовок цикла не сможет ничего проверить, основываясь только на методах контейнера и текущем значении иттератора. Где же универсальность? Без проверки в самом иттераторе она вообще не возможна. Даже в массиве, откуда оператор p>=c.begin()? Он вытекает из того факта, что адрес элемента не может быть меньше адреса начала всего массива. Но это относится только к массивам.

@Aye Aye · 28.01.2010, 06:08

для прохода итератора от конца контейнера к началу делают
iterator TArray::rbegin() и iterator TArray::rend() - типа реверсивные begin() и end(). и вот у них operator++ будет гнать итератор от конца к началу.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class list
private:
        node *endlist;
        node *beginlist;
public:
        list(){}
        struct node{
                 //куски кода...
                 node *next; //следующий узел списка
        };
        class iterator{
                //чето там...
                iterator &operator++(int i)
                {
                           info=info->next;
                           return *this;
                 }
        };
        iterator begin()
        {
                  return iterator(beginlist);
         }
         iterator end()
        {
                  return iterator(endlist);
         }
         
};
//в main()
list L;
for (list::iterator iter=L.begin();iter!=L.end();iter++)
{
       //работа с *iter
}

итератор не может быть больше или меньше begin() (если контейнер в виде дерева, очевидно что больше-меньше не подходит), итератор это просто ссылка на очередной обькет, и у него два оператор != и ++, что бы можно было следущий элемент получить, и за границу не выйти.

@taras atavin · 28.01.2010, 06:09 **[ТС]**

Допустим. пусть я иду от begin() и дошёл до конца.

Сообщение от Aye Aye

C++
1
iterator end() { iterator it(Data + Number); return it; }

. Проверять на p<c.end()? А как иттератор знает, что он реверсивный? И какой end вернуть в списке?

@Aye Aye · 28.01.2010, 06:14

у него тип дургой:
TArray::reverse_iterator

вот на основе этого можно подумать

@taras atavin · 28.01.2010, 06:20 **[ТС]**

От произвольного элемента как перебирать? Предположим, я хочу перебрать от указателя на середину массива до начала. rbegin юзить нельзя, так как он начнёт с конца, а у меня конкретный указатель, с которого надо начать. Не указав реверс, цикл пойдём к концу, а мне надо к началу.

Добавлено через 46 секунд
Другой тип? Понятно. Это решает и проблему произвольного старта.

Добавлено через 55 секунд
Но всё же каков end() для списка?

Новые блоги и статьи Все статьи Все блоги /
BOINC: 22 года — и всё ещё работает Programma_Boinc 12.03.2026 BOINC: 22 года — и всё ещё работает Дэвид Андерсон написал ретроспективу. Кратко: в 2001 году он ушёл из United Devices, где был CTO, и за несколько месяцев написал ядро BOINC — клиент, сервер,. . .	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562

	Иттераторы 23.01.2010, 05:05. Показов 4149. Ответов 20 Метки нет (Все метки) Никогда не пользовался, а теперь хочу разобраться. Запостите, пожалуйста ответы на вопросы: 1. Что такое иттераторы? 2. Как их делать? 3. Как ими пользоваться? 4. Каким образом при этом достигается ускорение? 0

@inter-admin 9715 / 6470 / 52 Регистрация: 06.03.2009 Сообщений: 28,500
	23.01.2010, 07:03
	настолько лень приложить усилие? http://ru.wikipedia.org/wiki/%... 0%BE%D1%80 0

@Nick Alte 1675 / 1047 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	23.01.2010, 09:42
	Итератор похож на указатель, а не на индекс. В приведённом примере ты со своим итератором занулил бы всю доступную память, пока тебя не остановил бы сбой. Многие итераторы не проверяются, проверять их ты должен сам. В данном случае условие надо было написать как p>=c.begin(); Суть итераторов заключается в том, что они ИМИТИРУЮТ поведение указателей на массиве. Причём имитировать это поведение они могут и на других структурах данных - списках, деревьях и т.д. Таким образом ты можешь единообразно работать с разными по своей природе контейнерами, не заморачиваясь деталями их реализации. Аналогично, при разработке своих контейнеров имеет смысл разработать для них итераторы, имеющие такое же поведение. Эта идея замечательно развивается в понятии обобщённого программирования (см. хелп по <algorithm>). Сделанные в виде шаблонов функции вроде сортировки или перекидывания части элементов используют этот единообразный способ для того, чтобы работать с разными контейнерами. То есть, одна и та же std::sort способна сортировать и vector, и list, и deque, и твой собственный контейнер, если ты озаботился сделать для него совместимые итераторы. 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	28.01.2010, 05:01 [ТС]
	Эйси. 1. Класс иттератора объявляется внутри класса контейнера. 2. В нём делаеются два конструктора: дефолтный и с параметром-указателем. 3. Единственное данное - указатель. 4. Объявляется оператор приведения к ссылке. Так? Добавлено через 1 минуту А что за оператор it? Добавлено через 2 минуты А можно в коде оператора-члена, объявленного в иттераторе, получить доступ к полям контейнера? Как? 0

@Aye Aye 373 / 287 / 97 Регистрация: 17.12.2009 Сообщений: 567
	28.01.2010, 05:18
	1-4 все так!!! но это мой собственный пример, в stl контейнирах в С++ итераторы описаны намного сложнее. и служат намного болие широким целям, у Бьерна Страуструпа в "Язык программирования C++" все описано по поводу итераторов и контейнеров. важно что класс итератора внутри класса контейнера, потму что обычно это все шаблонные классы и класс итератора зависит от класса контейнера. остальное - как придется... it это не оператор ))) это же обькет - экземпляр класса TArray::iterator. нельзя!!! никак!!! в этом вся соль, больше абстракции - легче работа. например: ты же понятия не имеешь как устроен итератор стандартного контейнера map, а пользуешься им весьма эфективно! а между тем попробуй посмотри как он устоен - мозг можно поломать. так что не надо рыться в реалезации, надо просто очено точно и эфективно реализовывать интерфейс (доступные пользователю методы и поля данных) Comprenez-vous? 0

@Aye Aye 373 / 287 / 97 Регистрация: 17.12.2009 Сообщений: 567
	28.01.2010, 06:14
	у него тип дургой: TArray::reverse_iterator вот на основе этого можно подумать 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	28.01.2010, 06:20 [ТС]
	От произвольного элемента как перебирать? Предположим, я хочу перебрать от указателя на середину массива до начала. rbegin юзить нельзя, так как он начнёт с конца, а у меня конкретный указатель, с которого надо начать. Не указав реверс, цикл пойдём к концу, а мне надо к началу. Добавлено через 46 секунд Другой тип? Понятно. Это решает и проблему произвольного старта. Добавлено через 55 секунд Но всё же каков end() для списка? 0