Форум программистов, компьютерный форум CyberForum.ru

Иттераторы - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
23.01.2010, 05:05     Иттераторы #1
Никогда не пользовался, а теперь хочу разобраться. Запостите, пожалуйста ответы на вопросы:
1. Что такое иттераторы?
2. Как их делать?
3. Как ими пользоваться?
4. Каким образом при этом достигается ускорение?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.01.2010, 05:05     Иттераторы
Посмотрите здесь:

Инкапсуляция, иттераторы, абстрактные списки на С C++
C++ Иттераторы

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
inter
9696 / 2449 / 43
Регистрация: 06.03.2009
Сообщений: 8,503
23.01.2010, 07:03     Иттераторы #2
настолько лень приложить усилие? http://ru.wikipedia.org/wiki/%D0%98%...82%D0%BE%D1%80
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
23.01.2010, 07:42  [ТС]     Иттераторы #3
Айси. Иттератор похож на указатель, но в операторах сложения/вычитания и инкремента/декремента проверяет выход за границу контейнера? Если я точно знаю, что у меня динамический массив, то в чём преимущество? Каким образом можно достичь ускорения по сравнению с индексом? Зачем мне вообще что добавлять в начало во время перебора? А если я добавлю хоть что то в динамический массив (даже в конец), то каким образом сохранятся адреса элементов массива? Индекс я могу сравнивать с нулём, что быстрее, а иттератор придётся сравнивать с указателем на вершину, что медленнее. По-моему перенос тормоза со сложения с базой в декремент адреса и всего делов. Подозреваю у себя ошибку. Где она?

Добавлено через 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
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
23.01.2010, 09:42     Иттераторы #4
Итератор похож на указатель, а не на индекс. В приведённом примере ты со своим итератором занулил бы всю доступную память, пока тебя не остановил бы сбой. Многие итераторы не проверяются, проверять их ты должен сам. В данном случае условие надо было написать как p>=c.begin();
Суть итераторов заключается в том, что они ИМИТИРУЮТ поведение указателей на массиве. Причём имитировать это поведение они могут и на других структурах данных - списках, деревьях и т.д. Таким образом ты можешь единообразно работать с разными по своей природе контейнерами, не заморачиваясь деталями их реализации. Аналогично, при разработке своих контейнеров имеет смысл разработать для них итераторы, имеющие такое же поведение.
Эта идея замечательно развивается в понятии обобщённого программирования (см. хелп по <algorithm>). Сделанные в виде шаблонов функции вроде сортировки или перекидывания части элементов используют этот единообразный способ для того, чтобы работать с разными контейнерами. То есть, одна и та же std::sort способна сортировать и vector, и list, и deque, и твой собственный контейнер, если ты озаботился сделать для него совместимые итераторы.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.01.2010, 05:46  [ТС]     Иттераторы #5
Цитата Сообщение от 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
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
27.01.2010, 11:15     Иттераторы #6
Цитата Сообщение от taras atavin Посмотреть сообщение
1. Что такое иттераторы?
итератор - это паттерн проектирования, который позволяет обойти все элементы агрегата без раскрытия информации о том, как он устроен.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.01.2010, 04:55     Иттераторы #7
что то типа этого, черт его знает, как правельнее сделать
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
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.01.2010, 05:01  [ТС]     Иттераторы #8
Эйси.
1. Класс иттератора объявляется внутри класса контейнера.
2. В нём делаеются два конструктора: дефолтный и с параметром-указателем.
3. Единственное данное - указатель.
4. Объявляется оператор приведения к ссылке.
Так?

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

Добавлено через 2 минуты
А можно в коде оператора-члена, объявленного в иттераторе, получить доступ к полям контейнера? Как?
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.01.2010, 05:18     Иттераторы #9
1-4 все так!!! но это мой собственный пример, в stl контейнирах в С++ итераторы описаны намного сложнее. и служат намного болие широким целям, у Бьерна Страуструпа в "Язык программирования C++" все описано по поводу итераторов и контейнеров.
важно что класс итератора внутри класса контейнера, потму что обычно это все шаблонные классы и класс итератора зависит от класса контейнера. остальное - как придется...

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

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

Comprenez-vous?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.01.2010, 05:37  [ТС]     Иттераторы #10
Цитата Сообщение от 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
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.01.2010, 05:38     Иттераторы #11
можно получить только если чрез другие итераторы, как и видно из релизации выше:
C++
1
 TArray::iterator it=a.begin()
вот тут оно и происходит, но не непосредственно, а через функцию iterator TArray::begin(). вот так можно организовать доступ к любому полю контейнера - через еще одну функцию, определенную в классе контейнеа. только лучге не трогать никакие поля, кроме самих непосредственных данных - элементов контейнера, иначе идеология итератора нарушится.

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

дикремента у итераторов еще не встречал, но врядли это очень плохо...
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.01.2010, 05:43  [ТС]     Иттераторы #12
Цитата Сообщение от 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
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.01.2010, 05:44     Иттераторы #13
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
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.01.2010, 05:47  [ТС]     Иттераторы #14
Цитата Сообщение от Aye Aye Посмотреть сообщение
тут нельзя false надо возвращать end();
end() - действительный иттератор конца контейнера. Если так сделать, то перебор зациклится и никакая проверка вообще не поможет. Уж это то даже я понимаю.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.01.2010, 05:49     Иттераторы #15
так, вощем проверку на выход за предел допустимого диапозона сам класс итератора не должен предусматривать, в 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
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.01.2010, 05:57  [ТС]     Иттераторы #16
Цитата Сообщение от Aye Aye Посмотреть сообщение
надо это извне делать
. А если это список? Тогда заголовок цикла не сможет ничего проверить, основываясь только на методах контейнера и текущем значении иттератора. Где же универсальность? Без проверки в самом иттераторе она вообще не возможна. Даже в массиве, откуда оператор p>=c.begin()? Он вытекает из того факта, что адрес элемента не может быть меньше адреса начала всего массива. Но это относится только к массивам.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.01.2010, 06:08     Иттераторы #17
для прохода итератора от конца контейнера к началу делают
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
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.01.2010, 06:09  [ТС]     Иттераторы #18
Допустим. пусть я иду от begin() и дошёл до конца.
Цитата Сообщение от Aye Aye Посмотреть сообщение
C++
1
iterator end() { iterator it(Data + Number); return it; }
. Проверять на p<c.end()? А как иттератор знает, что он реверсивный? И какой end вернуть в списке?
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.01.2010, 06:14     Иттераторы #19
у него тип дургой:
TArray::reverse_iterator

вот на основе этого можно подумать
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.01.2010, 06:20  [ТС]     Иттераторы #20
От произвольного элемента как перебирать? Предположим, я хочу перебрать от указателя на середину массива до начала. rbegin юзить нельзя, так как он начнёт с конца, а у меня конкретный указатель, с которого надо начать. Не указав реверс, цикл пойдём к концу, а мне надо к началу.

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

Добавлено через 55 секунд
Но всё же каков end() для списка?
Yandex
Объявления
28.01.2010, 06:20     Иттераторы
Ответ Создать тему
Опции темы

Текущее время: 20:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru