Про итераторы
От: c-smile Канада http://terrainformatica.com
Дата: 22.04.05 23:54
Оценка: 4 (1)
Есть два подхода к итераторам: "Java" и "STL"

В Java позиция итератора это позиция *между* элементами последовательности.


в stl позиция итератора это позция элемента


Вот в статье (здесь) про последнюю QT (v.4.0) утверждается что:

The Java-style iterators are new in Qt 4.0 and are the standard ones used in Qt applications. They are more convenient to use than the STL-style iterators, at the price of being slightly less efficient. Their API is modelled on Java's iterator classes.


В принципе дейтвительно Java вариант выглядит логичнее в том смысле что:
1) не нужно специального end value (которое кстати не всегда и можно-то натурально определить)
2) операции prev / next симметричны.

А вы как думаете?
Re: Про итераторы
От: McSeem2 США http://www.antigrain.com
Дата: 23.04.05 00:26
Оценка: +1
Здравствуйте, c-smile, Вы писали:

CS>В принципе дейтвительно Java вариант выглядит логичнее в том смысле что:

CS>1) не нужно специального end value (которое кстати не всегда и можно-то натурально определить)
CS>2) операции prev / next симметричны.

Интересный вопрос. В оправдание STL итераторов — как голый указатель в C/C++ может указывать на нечто между элементами? Это я к тому, что std::vector<>::iterator — это фактически голый указатель и есть. И делать его "межэлементным" не резон по причине производительности. А отсюда пошли и все остальные итераторы. Не знаю, возможно не стоило STL-цам упираться в единость концепции и, например, нагрузить std::set<>::iterator большей функциональностью (в отличие от std::vector).
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[2]: Про итераторы
От: c-smile Канада http://terrainformatica.com
Дата: 23.04.05 00:32
Оценка:
Здравствуйте, McSeem2, Вы писали:

MS>В оправдание STL итераторов — как голый указатель в C/C++....


Голый указатель имеет смысл когда используется как указатель на начало
последовательности элементов. Т.е. такое использование итератора
предполагает знание про геометрию контейнера что иделогически (по отношению
к итератору) в корне не верно. Ага?
Re: Про итераторы
От: Шахтер Интернет  
Дата: 23.04.05 01:27
Оценка: +2
Здравствуйте, c-smile, Вы писали:

CS>Есть два подхода к итераторам: "Java" и "STL"


CS>А вы как думаете?


Смысл твоего сообщения от меня ускользает.
Согласно картинкам, оба варианта изоморфны.
Вообще, не очень понятно, что значит -- указывать между элементами?
... << RSDN@Home 1.1.3 stable >>
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re: Про итераторы
От: Elifant  
Дата: 23.04.05 02:59
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Есть два подхода к итераторам: "Java" и "STL"


CS>В Java позиция итератора это позиция *между* элементами последовательности.

CS>в stl позиция итератора это позция элемента

CS>В принципе дейтвительно Java вариант выглядит логичнее в том смысле что:

CS>1) не нужно специального end value (которое кстати не всегда и можно-то натурально определить)
CS>2) операции prev / next симметричны.

CS>А вы как думаете?


Когда я после C++ начал программить на Java, возникла простая задача: гуй, 3 кнопки "загрузить", "вперед" и "назад", нужно загрузить из файла список картинок и просматривать.
В C++ я загружал все картинки в некий контейнер и отдавал гую итератор. по "вперед" делаем ++it и показываем, по "назад" --it и показываем.
Попробовал то же самое в Java. По нажатию "вперед" делаю it.next(), получаю картинку, показываю. По нажатию "назад" делаю it.prev() и получаю ту же самую картинку. Тогда плюнул и заюзал Vector и индекс.
Подскажите плз, как сделать это правильно с Java-итераторами?
Re: Про итераторы
От: Костя Ещенко Россия  
Дата: 23.04.05 05:32
Оценка: +2 -1
c-smile wrote:

> Есть два подхода к итераторам: "Java" и "STL"

>
> В Java позиция итератора это позиция *между* элементами последовательности.
>
>
> в stl позиция итератора это позция элемента
>
>
> Вот в статье (здесь) про последнюю QT (v.4.0) утверждается что:
>

> The Java-style iterators are new in Qt 4.0 and are the standard ones used in Qt applications. They are more convenient to use than the STL-style iterators, at the price of being slightly less efficient. Their API is modelled on Java's iterator classes.

>
> В принципе дейтвительно Java вариант выглядит логичнее в том смысле что:
> 1) не нужно специального end value (которое кстати не всегда и можно-то натурально определить)
> 2) операции prev / next симметричны.
>
> А вы как думаете?

Для эффективной реализации (обобщенных) алгоритмов над последовательностями трудно придумать что-то лучшее, чем итераторы STL. У них есть все что надо, но нет ничего лишнего, мы не платим за то, чего не заказывали. В этом видимо и был поинт создателей STL.

Но у конечного юзера алгоритмов и контейнеров могут быть несколько иные требования, чем у реализатора алгоритмов.
Например, стандартартными алгоритмами удобнее пользоваться, если они принимают не итераторы, а диапазоны. И появляются boost::range и прочие подобные решения, где диапазоны реализованы посредством пары STL-итераторов.
А в ситуациях, когда нас меньше волнует эффективность, есть место и для итераторов подобных Джавовским, которые реализуемы посредством STL-итератора + ссылки на контейнер + дополнительных проверок.
Posted via RSDN NNTP Server 1.9
На самом деле, люди не читают газеты, они принимают их каждое утро, так же как ванну. ©Маршалл Мак-Льюэн
Re[3]: Про итераторы
От: McSeem2 США http://www.antigrain.com
Дата: 23.04.05 05:40
Оценка: +1 -2
Здравствуйте, c-smile, Вы писали:

CS>Голый указатель имеет смысл когда используется как указатель на начало

CS>последовательности элементов. Т.е. такое использование итератора
CS>предполагает знание про геометрию контейнера что иделогически (по отношению
CS>к итератору) в корне не верно. Ага?

Честно сказать, мне концепция итераторов вообще не нравится. Просто потому, что ее превратили в какую-то притянутую за уши догму. У итератора по его названию должна быть одна единственная операция — инкремент. На то он и итератор. Если итератор имеет операцию декремент, то это уже не итератор, это нечто другое, скажем, указатель (не обязательно Сишный, просто некий абстрактный). А уж такое понятие, как random access iterator — вообще оксиморон. Примерно как "живой труп". В чистом виде, итератором является только то, что согласуется с полиси InputIterator и не более. И итератор дожен быть принципиально read-only. Иначе это уже не итератор. Указатель в частных случаях имеет право быть итератором, но вообще — он нечто большее, чем итератор.

В Жаве тоже не лучше. Единственное отличие, как я понимаю, это то, что жавовские итераторы имеют гистерезис, то есть, запаздывание на единицу при смене направления. Что на практике дает больше усложнений, чем кайфов.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: Про итераторы
От: Odi$$ey Россия http://malgarr.blogspot.com/
Дата: 23.04.05 06:09
Оценка: +2
Здравствуйте, c-smile, Вы писали:

CS>Есть два подхода к итераторам: "Java" и "STL"


CS>В Java позиция итератора это позиция *между* элементами последовательности.

CS>

CS>в stl позиция итератора это позция элемента

CS>

CS>А вы как думаете?


в STL она тожа как-бы между, если судить по логике приведения reverse_iterator к iterator при помощи base() — он начинает указывать на другой элемент, на одну позицию правее:

Re[2]: Про итераторы
От: c-smile Канада http://terrainformatica.com
Дата: 23.04.05 19:09
Оценка:
Здравствуйте, Шахтер, Вы писали:

Ш>Согласно картинкам, оба варианта изоморфны.


Наверное. Но не совсем.

Ш>Вообще, не очень понятно, что значит -- указывать между элементами?


Object next() возвращает элемент над которым "пролетает" итератор.

В Java не требуется специальное значение end
так как тест на bos/eos осущесвляется отдельной функцией (hasNext).

while (i.hasNext())
        cout << i.next().ascii() << endl;


Еще раз — не знаю — хорошо это или плохо. Поэтому и спросил.
Re[2]: Про итераторы
От: c-smile Канада http://terrainformatica.com
Дата: 23.04.05 19:15
Оценка:
Здравствуйте, Odi$$ey, Вы писали:

OE>в STL она тожа как-бы между, если судить по логике приведения reverse_iterator к iterator при помощи base() — он начинает указывать на другой элемент, на одну позицию правее:


OE>


Просто для логичекой симметрии пришлось определить
наряду с end еще и rend что имхо выглядит несколько
негармонично.
Re[4]: Про итераторы
От: c-smile Канада http://terrainformatica.com
Дата: 23.04.05 19:35
Оценка:
Здравствуйте, McSeem2, Вы писали:

MS>Честно сказать, мне концепция итераторов вообще не нравится. Просто потому, что ее превратили в какую-то притянутую за уши догму. У итератора по его названию должна быть одна единственная операция — инкремент. На то он и итератор....


Как я понимаю тебя больше бы устроил механизм foreach.

Вот например в D:

// параметризуемый класс (ака template)
class Collection(T)
{
  int opApply(int delegate(inout T) dg) 
  {
      для всех элементов коллекции вызвать dg...
  }
}


Использование:

Collection!(Foo) myFooCollection;

foreach( Foo f; myFooCollection ) // foreach это просто вызов метода opApply 
{                                 // c синтезированным "naked" delegate
   f.something() ...
}


Принципиальное отличие (и прэлэсть) состоит в том
коллекция сама управляет перебором — т.е. вопросов
типа "где стоит указатель" просто не возникает.

So far мне в D итераторы не понадобились.
opApply — действительно удобно и идеологически правильно.
Re[4]: Про итераторы
От: Зверёк Харьковский  
Дата: 23.04.05 19:44
Оценка:
Здравствуйте, McSeem2, Вы писали:

CS>>Голый указатель имеет смысл когда используется как указатель на начало

CS>>последовательности элементов. Т.е. такое использование итератора
CS>>предполагает знание про геометрию контейнера что иделогически (по отношению
CS>>к итератору) в корне не верно. Ага?

MS>Честно сказать, мне концепция итераторов вообще не нравится.

[зверьковыгрызено]
Ты знаешь, Макс, в последнее время я тоже стал приходить к этой мысли
Еще полгода назад я лепил их практически везде, где надо перебрать 3 элемента — прилежно реализовывал все 10 операторов.... даже если по юз-кейсу эти итераторы никто никогда не будет сравнивать...

А потом забил. И более того — даже на красоту конструкций it++, *it забил в пользу менее симпатишных, но иногда более очевидных it.get(), it.next()...
И теперь у меня в коде такое... Для каждого контейнеро-образного класса — свой способ перебрать элементы.

Так и живем
это мы, Зверьки!
FAQ — це мiй ай-кью!
Re[3]: Про итераторы
От: Зверёк Харьковский  
Дата: 23.04.05 19:48
Оценка:
Здравствуйте, c-smile, Вы писали:

Ш>>Вообще, не очень понятно, что значит -- указывать между элементами?


CS>Object next() возвращает элемент над которым "пролетает" итератор.


CS>В Java не требуется специальное значение end

CS>так как тест на bos/eos осущесвляется отдельной функцией (hasNext).

CS>
CS>while (i.hasNext())
CS>        cout << i.next().ascii() << endl;
CS>


CS>Еще раз — не знаю — хорошо это или плохо. Поэтому и спросил.


Ну, один из очевидных недостатков — невозможно перебрать "часть" контейнера — как-нибудь так:
std::sort(container.begin(), container.begin() + 10);


Другой вопрос — что нужна такая возможность далеко не всегда.
это мы, Зверьки!
FAQ — це мiй ай-кью!
Re[4]: Про итераторы
От: c-smile Канада http://terrainformatica.com
Дата: 23.04.05 20:08
Оценка:
Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Ну, один из очевидных недостатков — невозможно перебрать "часть" контейнера — как-нибудь так:

ЗХ>
ЗХ>std::sort(container.begin(), container.begin() + 10);
ЗХ>


А что означает
container.begin() + 10
для котейнера типа list?
Re: Про итераторы
От: Кодт Россия  
Дата: 23.04.05 20:29
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Есть два подхода к итераторам: "Java" и "STL"

CS>А вы как думаете?

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

Итераторы STL — это обобщение идеи указателя: они позволяют, не меняя состояние субъекта, многократно (за исключением одебиленных Input/Output Iterator) доступаться к одному объекту.

Итераторы Java (а также энумераторы COM) — это обобщение идеи сканера файла: доступ к объекту приводит к смене состояния субъекта.

Input/Output Iterator — это, на самом деле, синтаксический сахар: чтобы работу со устройствами чтения/записи привести к тому же виду, что и работу с последовательными контейнерами.

В принципе, никто не мешает сделать и наоборот: трактовать указатели контейнеров как сканеры файлов — в тех алгоритмах, где есть однонаправленное чтение/запись.
// вот как выглядят некоторые алогритмы
template<class InputScanner, class OutputScanner>
void copy_javalike(InputScanner src, OutputScanner dst)
{
  while(!src.finish()) dst.write(src.read());
}
template<class InputScanner, class OutputScanner, class Transform>
void transform_javalike(InputScanner src, OutputScanner dst, Transform tf)
{
  while(!src.finish()) dst.write(tf(src.read());
}
template<class InputScanner, class Value, class SumFunc>
Value adjacent_sum_javalike(Value start, InputScanner src, SumFunc sum)
{
  while(!src.finish()) start = sum(start,src.read());
  return start;
}

// переходники от указателей к сканерам

template<class InputIterator>
struct stl_input_scanner
{
  InputIterator begin, end; // дань традиции STL: конец диапазона задаётся указателем на "за-конец"
  stl_input_scanner(InputIterator b, InputIterator e) : begin(b), end(e) {}
  bool finish() const { return begin==end; }
  typename std::iterator_traits<InputIterator>::value_type read() { return *begin++; }
};

template<class OutputIterator>
struct stl_output_scanner
{
  OutputIterator pos;
  stl_output_scanner(OutputIterator p) : pos(p) {}
  template<class Value>
  void write(Value const& v) { *p++ = v; }
};

Но тут выясняется, что есть алгоритмы, работающие с последовательностями — а есть алгоритмы, работающие с контейнерами. В принципе, для работы с контейнерами очень пригодилась бы модель полуинтервалов (да и на последовательности её можно спроецировать).
Но разнообразие моделей доступа, применительно к одним и тем же объектам (контейнерам или файлам) — это накладно.
Представьте себе модель вектора, у которого есть методы begin(), end(), start_read(), start_write(), full_range().
Мрачновато...
Поэтому STL остановилась на обобщённых указателях (с бонусом в виде синтаксического сахара — совместимости с голыми указателями). И мне кажется, именно этот бонус склонил чашу весов.
А у COM и Java этого сахара не было...
Перекуём баги на фичи!
Re[5]: Про итераторы
От: Кодт Россия  
Дата: 23.04.05 20:41
Оценка:
Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Ты знаешь, Макс, в последнее время я тоже стал приходить к этой мысли

ЗХ>Еще полгода назад я лепил их практически везде, где надо перебрать 3 элемента — прилежно реализовывал все 10 операторов.... даже если по юз-кейсу эти итераторы никто никогда не будет сравнивать...

ЗХ>А потом забил. И более того — даже на красоту конструкций it++, *it забил в пользу менее симпатишных, но иногда более очевидных it.get(), it.next()...

ЗХ>И теперь у меня в коде такое... Для каждого контейнеро-образного класса — свой способ перебрать элементы.

Есть такая методология — стрёмное программирование (XP).
Надо тебе сделать output iterator поверх какого-то фидера — делаешь тяп-ляп, зато совместимо со всеми прочими алгоритмами.
struct my_output_iterator : iterator<input_iterator_tag, Value>
{
  my_output_iterator& operator++(int) { return *this; } // тяп-ляп номер раз
  my_output_iterator& operator*() { return *this; } // тяп-ляп номер два
  my_output_iterator& operator=(Value v) { NowWriteIt(v); }
};

Потом, когда руки дотянутся — переделаешь так, чтобы не было шансов для misuse.
Да и, в конце концов, стратегии позволят нарожать таких итераторов сколько хочешь. Только один раз грамотно шаблон сделать...
// делаем оснастку для SomeInputFile
struct access_to_SomeFile
{
  typedef Data value_type;
  typedef SomeFile file_type;
  static bool eof(file_type& f) { return f.EndOfFile(); }
  static Data read(file_type& f) { Data v; f.Read(v); return v; }
};

// строим правильный стопроцентно совместимый и грамотно бьющий по пальцам итератор в духе святого STL
typedef file_input_iterator< access_to_SomeFile > somefile_input_iterator;
Перекуём баги на фичи!
Re[5]: Про итераторы
От: Зверёк Харьковский  
Дата: 23.04.05 20:41
Оценка:
Здравствуйте, c-smile, Вы писали:

ЗХ>>Ну, один из очевидных недостатков — невозможно перебрать "часть" контейнера — как-нибудь так:

ЗХ>>
ЗХ>>std::sort(container.begin(), container.begin() + 10);
ЗХ>>


CS>А что означает

CS>container.begin() + 10
CS>для котейнера типа list?

Для list — ничего не означает. Я всего лишь привел пример. Пойнт мой был: возможность вызова функции, которая принимает начальный и конечный итераторы, но передать ей не begin и end, а что-то другое; таким образом, обработать лишь часть контейнера.
это мы, Зверьки!
FAQ — це мiй ай-кью!
Re[6]: Про итераторы
От: Зверёк Харьковский  
Дата: 23.04.05 20:48
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Зверёк Харьковский, Вы писали:


ЗХ>>Ты знаешь, Макс, в последнее время я тоже стал приходить к этой мысли

ЗХ>>Еще полгода назад я лепил их практически везде, где надо перебрать 3 элемента — прилежно реализовывал все 10 операторов.... даже если по юз-кейсу эти итераторы никто никогда не будет сравнивать...

ЗХ>>А потом забил. И более того — даже на красоту конструкций it++, *it забил в пользу менее симпатишных, но иногда более очевидных it.get(), it.next()...

ЗХ>>И теперь у меня в коде такое... Для каждого контейнеро-образного класса — свой способ перебрать элементы.

К>Есть такая методология — стрёмное программирование (XP).

Прошлым летом поимел опыт экстремального программирования. Ездил в коммандировку. В шахте на глубине 800 метров в каске с фонарём на ноутбуке правил прогу на ассме.

(с) Михаил Дюмин
Автор: Дюмин Михаил
Дата: 21.04.05


а если серьезно — я обычно именно так и пишу.
но в последнее время стал сталкиваться с тем, что мне от "итератора" надо нааамного меньше, чем предоставляет концепция итератора stl.
последний пример — курсор к БД, который я пытался-пытался сделать итератором, а потом плюнул, сделал вот такое:
class cursor
{
...
    bool    next();
    value_t    get();
...
}

и мне от него больше ничего не нада. Причем через .end(), ++, == это выражалось сууущественно хуже.
это мы, Зверьки!
FAQ — це мiй ай-кью!
оффтоп
От: Зверёк Харьковский  
Дата: 23.04.05 21:01
Оценка:
Здравствуйте, Кодт, я там когда-то обещал статейку по LazyK. Так вот, у меня наконец-то дошли кажется руки этим заняться. Еще актуально или ты уже сам разобрался?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
FAQ — це мiй ай-кью!
Re[7]: Про итераторы
От: Кодт Россия  
Дата: 23.04.05 21:30
Оценка:
Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>а если серьезно — я обычно именно так и пишу.

ЗХ>но в последнее время стал сталкиваться с тем, что мне от "итератора" надо нааамного меньше, чем предоставляет концепция итератора stl.
ЗХ>последний пример — курсор к БД, который я пытался-пытался сделать итератором, а потом плюнул, сделал вот такое:
ЗХ>class cursor
ЗХ>{
ЗХ>...
ЗХ>    bool    next();
ЗХ>    value_t    get();
ЗХ>...
ЗХ>}

ЗХ>и мне от него больше ничего не нада. Причем через .end(), ++, == это выражалось сууущественно хуже.

Так я и говорю: есть разные модели для доступа к элементам. И привести одно к другому — с помощью шаблонов и проксей делается без проблем (как говорится, "день потерять, потом за час долететь").

Другое дело, что если нет потребности в совместимости с каким-то алгоритмом, заточенным под существующую модель — то эту совместимость можно не накладывать.

Кстати, пример адаптации указателя к сканеру — это создание COM-энумератора ко внутреннему STL-контейнеру COM-объекта. Тоже не обходится без этической силы и бениной матери... И тоже решается шаблонами — IEnumOnSTLImpl.
Перекуём баги на фичи!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.