Сейчас в списке рассылки буста (comp.lib.boost.devel) идет очень интересное обсуждение предложения Александреску забить на итераторы и строить все только на диапазонах.
Дискуссия идет под сабжем AlRangeExandrescu с участием самого Александреску.
Уже были озвучены (и признаны Андреем) некоторые проблемы с диапазонным подходом (производительность; разные хитрые случаи, когда с итераторами все просто, а с диапазонами все через одно место), например, тут: http://thread.gmane.org/gmane.comp.lib.boost.devel/191918/focus=191994
Посмотрим, чем закончится обсуждение. Да, все желающие могут, естественно, принять в нем участие, GMane позволяет посылать как бы письма прямо с веб-формы.
jazzer пишет:
> Сейчас в списке рассылки буста (comp.lib.boost.devel) идет очень > интересное обсуждение предложения Александреску забить на итераторы и > строить все только на диапазонах.
Я лично с ним согласен, только где все они раньше были ?
Здравствуйте, jazzer, Вы писали:
J>Уже были озвучены (и признаны Андреем) некоторые проблемы с диапазонным подходом (производительность; разные хитрые случаи, когда с итераторами все просто, а с диапазонами все через одно место), например, тут: J>http://thread.gmane.org/gmane.comp.lib.boost.devel/191918/focus=191994
Говорить, что диапазонный подход уступает в производительности — неверно. Для одних случаев больше подходит первый подход, для других — второй. Вопрос в том каких случаев больше. Например, попробуйте прозрачно реализовать фильтрующий итератор для классической пары итераторов — вы получите мега оверхед и по размеру и по производительности, в то время для range based итераторов эта задача решается очень просто. Недостатком пары итераторов является, то что надо дублировать данные. И во многих задачах когда нужно описывать бизнесс логику удобнее пользоваться умным итератором нежели парой.
J>Посмотрим, чем закончится обсуждение. Да, все желающие могут, естественно, принять в нем участие, GMane позволяет посылать как бы письма прямо с веб-формы.
Я отдаю предпочтение диапазонным итераторам.
Здравствуйте, Adriano, Вы писали:
A>Здравствуйте, jazzer, Вы писали:
J>>Уже были озвучены (и признаны Андреем) некоторые проблемы с диапазонным подходом (производительность; разные хитрые случаи, когда с итераторами все просто, а с диапазонами все через одно место), например, тут: J>>http://thread.gmane.org/gmane.comp.lib.boost.devel/191918/focus=191994
A>Говорить, что диапазонный подход уступает в производительности — неверно. Для одних случаев больше подходит первый подход, для других — второй.
Ну, Андрей в этом вопросе радикален — никаких итераторов, никогда!
A>Вопрос в том каких случаев больше. Например, попробуйте прозрачно реализовать фильтрующий итератор для классической пары итераторов — вы получите мега оверхед и по размеру и по производительности, в то время для range based итераторов эта задача решается очень просто. Недостатком пары итераторов является, то что надо дублировать данные. И во многих задачах когда нужно описывать бизнесс логику удобнее пользоваться умным итератором нежели парой.
Можно продемомстрировать выделенное на примере boost::filtered_iterator? http://www.boost.org/libs/iterator/doc/filter_iterator.html
Естественно, из пары таких итераторов элементарно делается filtered_range для Boost.Range — думаю, у каждого, кто пользуеся бустом, в проекте такой велосипедик есть.
Еще есть Adobe.Algorithm, который все STL-ные алгоритмы переписал на диапазоны — можно в него засовывать хоть контейнер, хоть пару итераторов.
J>>Посмотрим, чем закончится обсуждение. Да, все желающие могут, естественно, принять в нем участие, GMane позволяет посылать как бы письма прямо с веб-формы. A>Я отдаю предпочтение диапазонным итераторам.
т.е. слово "итератор" у тебя никуда не делось
Здравствуйте, jazzer, Вы писали:
J>Ну, Андрей в этом вопросе радикален — никаких итераторов, никогда!
A>>Вопрос в том каких случаев больше. Например, попробуйте прозрачно реализовать фильтрующий итератор для классической пары итераторов — вы получите мега оверхед и по размеру и по производительности, в то время для range based итераторов эта задача решается очень просто. Недостатком пары итераторов является, то что надо дублировать данные. И во многих задачах когда нужно описывать бизнесс логику удобнее пользоваться умным итератором нежели парой.
J>Можно продемомстрировать выделенное на примере boost::filtered_iterator? J>http://www.boost.org/libs/iterator/doc/filter_iterator.html J>Естественно, из пары таких итераторов элементарно делается filtered_range для Boost.Range — думаю, у каждого, кто пользуеся бустом, в проекте такой велосипедик есть.
Оператор `|` перегружен для удобства.
Вместо 36 байт (8 + 4*7) — 4092!
J>Еще есть Adobe.Algorithm, который все STL-ные алгоритмы переписал на диапазоны — можно в него засовывать хоть контейнер, хоть пару итераторов.
A>>Я отдаю предпочтение диапазонным итераторам. J>т.е. слово "итератор" у тебя никуда не делось
а как его называть?
Здравствуйте, Adriano, Вы писали:
A>Вместо 36 байт (8 + 4*7) — 4092!
Ого! Это интересно. Надо будет у себя посмотреть.
А как насчет скорости? (Это предполагает, что у тебя есть библиотека диапазонов — она у тебя есть? Если да, то какая?)
J>>Еще есть Adobe.Algorithm, который все STL-ные алгоритмы переписал на диапазоны — можно в него засовывать хоть контейнер, хоть пару итераторов.
A>>>Я отдаю предпочтение диапазонным итераторам. J>>т.е. слово "итератор" у тебя никуда не делось A>а как его называть?
Ну вот и я не знаю.
Для меня, итераторы и диапазоны — это вещи взаимодополняющие.
Всегда, пока можно и удобно, надо пользоваться диапазонами, но в конце все равно по результирующему диапазону придется ходить, и форычами дело, наверняка, не исчерпается. А ходить, кроме как итераторами, больше нечем, в общем-то.
Аналогия примерно такая: даже если у тебя в программе миллион классов, это не значит, что от простых типов нужно отказаться и пользоваться исключительно классами, и для всех простых типов написать обертки.
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, Adriano, Вы писали:
A>>Вместо 36 байт (8 + 4*7) — 4092! J>Ого! Это интересно. Надо будет у себя посмотреть.
Абстракция "пара итераторов" удваивается при добавлении одного фильтра, это заложено в саму абстракцию, ведь фильтрующими должны быть и begin и end. А в случае с "умным" итератором этого не происходит.
Получается сложность 2^n в лучшем случае.
J>А как насчет скорости?
думаю не очень
A>(Это предполагает, что у тебя есть библиотека диапазонов — она у тебя есть? Если да, то какая?)
простые функции на базе Boost.Range, Boost.Iterator. идея взята из Boost.RangeEx.
J>>>Еще есть Adobe.Algorithm, который все STL-ные алгоритмы переписал на диапазоны — можно в него засовывать хоть контейнер, хоть пару итераторов.
A>>>>Я отдаю предпочтение диапазонным итераторам. J>>>т.е. слово "итератор" у тебя никуда не делось A>>а как его называть? J>Ну вот и я не знаю. J>Для меня, итераторы и диапазоны — это вещи взаимодополняющие. J>Всегда, пока можно и удобно, надо пользоваться диапазонами, но в конце все равно по результирующему диапазону придется ходить, и форычами дело, наверняка, не исчерпается. А ходить, кроме как итераторами, больше нечем, в общем-то. J>Аналогия примерно такая: даже если у тебя в программе миллион классов, это не значит, что от простых типов нужно отказаться и пользоваться исключительно классами, и для всех простых типов написать обертки.
Грабля в том, что в дизайн С++ итераторов заложено разделение на begin и end, которого нет в "итераторах Александреску". Я думаю что в 99% случаях "итераторы Александреску" будут иметь такую же производительность или выше.
Здравствуйте, jazzer, Вы писали:
J>Сейчас в списке рассылки буста (comp.lib.boost.devel) идет очень интересное обсуждение предложения Александреску забить на итераторы и строить все только на диапазонах.
Там приводили пример std::find. Как его по-человечески перевести на диапазоны? Есть некая элегантность в том, чтобы сделать из него два алгоритма — before и after, но чем заменить ++*std::find(first, last, value)? Что делать с regex_search — тоже удвоить интерфейс?
Или если я хочу реализовать sorted_range, который будет хранить итераторы на элементы другого диапазона, но в другом порядке, — куда здесь засунуть диапазоны? И даже итераторы здесь вносят оверхед — те из них, которые должны хранить ссылку на свой контейнер (например, std::deque). Здесь можно было бы держать одну такую ссылку и много MFC-подобных POSITION.
Здравствуйте, Roman Odaisky, Вы писали:
RO>Там приводили пример std::find. Как его по-человечески перевести на диапазоны? Есть некая элегантность в том, чтобы сделать из него два алгоритма — before и after, но чем заменить ++*std::find(first, last, value)? Что делать с regex_search — тоже удвоить интерфейс?
RO>Или если я хочу реализовать sorted_range, который будет хранить итераторы на элементы другого диапазона, но в другом порядке, — куда здесь засунуть диапазоны? И даже итераторы здесь вносят оверхед — те из них, которые должны хранить ссылку на свой контейнер (например, std::deque). Здесь можно было бы держать одну такую ссылку и много MFC-подобных POSITION.
Это все отголоски приплюснутого мышления (сори за термин, но больно хорошо тут подходит).
Пока те кто обсуждает эту тему будут думать в терминах махровой императивщины, они никогда не поймут что пытается предложить Александреску.
Суть в том, что чтобы понять его предложение нужно забыть про "хранить итераторы на элементы другого диапазона" и прочую муть. Есть последовательность и преобразования в другие последовательности.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Это все отголоски приплюснутого мышления (сори за термин, но больно хорошо тут подходит). VD>Пока те кто обсуждает эту тему будут думать в терминах махровой императивщины, они никогда не поймут что пытается предложить Александреску.
VD>Суть в том, что чтобы понять его предложение нужно забыть про "хранить итераторы на элементы другого диапазона" и прочую муть. Есть последовательность и преобразования в другие последовательности.
Одними последовательностями всё не исчерпывается (где исчерпывается, там, понятно, лучше только в терминах последовательностей).
Жизнь немножко разнообразнее.
Иначе все сведется к догмам типа "свободные функции — это все отголоски приплюснутого мышления, надо забыть про них и прочую муть. Всё есть объект и объекты обмениваются сообщениями".
Все хорошо на своем месте.
P.S. Кстати, после того, как ты наконец получил свою финальную последовательность, по ней еще нужно пройтись потом, и, опять же, одним только форычем (к которому сводятся все range-ориентированные дизайны) всё не исчерпывается, и во многих случаях тебе опять же потребуются итераторы.
Т.е., коненчо, можно и на последовательностях извернуться, но это будет тот же маразм, что и создавать по классу на каждую функцию только из-за того, что "всё есть объект".
Здравствуйте, VladD2, Вы писали:
VD>Пока те кто обсуждает эту тему будут думать в терминах махровой императивщины, они никогда не поймут что пытается предложить Александреску.
Ну да. C++ — императивный язык, никуда от этого не денешься. В функциональном языке, если бы я хотел заменить элемент списка на что-нибудь еще, я бы так и писал, как предлагает Александреску: before(range, x) ++ [y] ++ after(range, x). А в C++ так не делают, в C++ это *find(range, x) = y.
VD>Суть в том, что чтобы понять его предложение нужно забыть про "хранить итераторы на элементы другого диапазона" и прочую муть. Есть последовательность и преобразования в другие последовательности.
Идея sorted_range тебе, я думаю, очевидна? Выглядит это как диапазон, а вот как это реализовать?
Здравствуйте, Roman Odaisky, Вы писали:
RO>>>А в C++ так не делают, в C++ это *find(range, x) = y.
E>>В C++ так лучше не делать.
RO>Предполагается, что можно быть уверенным, что элемент x там есть.
Тут вообще-то интересная штука получается. Если стоит задача заменить элемент в последовательности, а его там нет, то вариант "before(range, x) ++ [y] ++ after(range, x)", не сломается. Хотя и произведет неправильную последовательность. Вариант же "*find(range, x)=y" может привести к чему угодно, в самом худем случае -- к наведенной ошибке, которая проявится совсем в другом месте. Т.е. ни один из вариантов не дает удовлетворительного поведения в случае, если программист ошибся. Но я бы предпочел неправильную последовательность неопределенному поведению.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Тут вообще-то интересная штука получается. Если стоит задача заменить элемент в последовательности, а его там нет, то вариант "before(range, x) ++ [y] ++ after(range, x)", не сломается. Хотя и произведет неправильную последовательность. Вариант же "*find(range, x)=y" может привести к чему угодно, в самом худем случае -- к наведенной ошибке, которая проявится совсем в другом месте. Т.е. ни один из вариантов не дает удовлетворительного поведения в случае, если программист ошибся. Но я бы предпочел неправильную последовательность неопределенному поведению.
Хотя мой пример несколько неудачен, потому что он, по сути, сводится к ((y if i == x else i) for i in range), т. е., это задача transform_iterator/transform_range (хотя поведение разное — в случае, если x встречается более одного раза).
Вообще, зачем нужен find? У кого-кого, а у тебя должны быть мегабайты исходников на C++, грепни их на предмет std::find. Какие основные применения и как можно заменить на диапазоны?
Вот, что я наскреб:
1. list.erase(find_if(list.begin(), list.end(), is_bad)) -> list = before(list, is_bad) ++ after(list, is_bad)
2. lexicographical_compare(find_if(first1, last1, is_good), last1, find_if(first2, last2, is_good), last2) -> очевидно
3. ++seq2[find(seq1.begin(), seq1.end(), some_value) — seq1.begin()] -> тут не очень понятно, seq2[before(seq1, some_value).size()], что ли?
4. if(find(first, last, value) != last) -> вообще новую функцию ввести, exists?
Что-то создается впечатление, что Оккаму скоро будет нечем бриться.
Здравствуйте, Roman Odaisky, Вы писали:
M>>Можно же реализовать диапазоны с помощью итераторов. ?
RO>Он хочет вообще избавиться от итераторов.
Что значит "вообще избавиться"? Итераторы — это не часть языка, а часть библиотеки. STL 1.0 никуда не денется. Она есть и все старперы могут использовать ее.
Ну, а в дизайне современных библиотек действительно их использовать совершенно не обязательно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Взято из рассылки буста, там же понемногу началось обсуждение:
My article with a draft name "Iterators Must Go (Ahead)" is now published on InformIt and mentioned on reddit.com. Due to the vagaries of posting time and reddit dynamics, the article didn't stay long on reddit's programming page so it got very few views and comments.
Please comment here and/or there and vote up if you liked it.
Many thanks to the many Boost participants who reviewed the article prior to publication (see the article's last section for a full list).
Andrei
ЗЫ Теперь про Андрея пишут: "Andrei Alexandrescu, author of The D Programming Language", имея в виду то, что он написал книжку "The D Programming Language", а не сам язык, однако выглядит это в результате так, будто он и есть автор языка
с участием самого Александреску.
