Здравствуйте, skeptik_!

_>Да пожалуйста. Разница с msvc 9.0 в том, что у них условие заключает в себя цикл, а у меня стоит в начале (это я уже потом посмотрел)
_>

_>template< typename ForwardIterator >
_>ForwardIterator max( ForwardIterator first, ForwardIterator last )
_>{
_>    if ( first == last )
_>        return first;

_>    ForwardIterator result = first;
_>    while( ++first != last )
_>        if ( *result < *first )
_>            result = first;
_>    return result;
_>}
_>

А если на входе first > last?

Или эти итераторы по кольцу гуляют (++first)?

Здравствуйте, SergeCpp, Вы писали:

SC>А если на входе first > last?

От этого так же сложно защититься, как и от того, что first и last принадлежат _разным_ последовательностям.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, eao197, Вы писали:

E>>Еще раз: программисты ошибаются. ОШИБАЮТСЯ!
S>Пока что вся эта дискуссия показывает недостатки плюсов как языка по сравнению с полноценным ФП.
Мне тоже яблоки больше груш нравятся.

S>Если я правильно понимаю, на ФЯ написать некорректную реализацию max_element практически нереально.
S>Потому, что непустые последовательности там радикально отличаются от пустых. В итоге программист вынужден явно обработать все случаи:0, 1, и больше элементов.
Это и есть предусловия.

S>А все эти припрыгивания с лишним сравнением (которое предположительно снизит производительность для вырожденных случаев)
Производительность здесь вообще не является главным критерием(это скорее бонус).

Во-первых, каждую проверку необходимо поддерживать. Если сегодня есть 'a > 0', а завтра нужно сделать 'a > 1', то необходимо править _все_ вхождения.

Во-вторых, это банальная логика — прежде чем прыгнуть в басейн, я проверю уровень воды, а вы прыгните в любом случае, плюс необходимо будет добавить реакцию на исключение — "прыгнуть не получилось". Зачем ? А потом огрмное количство кода занимается обработкой таких вот фиктивных ошибок. А ведь этот код опять же, надо поддерживать.

Да, бывают такие места где проверить не получается(или это сложно) — там приходится прыгать.

eao197 пропагандирует defensive programming, где все(функции) друг другу не доверяют. Я, в принципе, применяю этот же подход, только более "крупномасштабно": функции разростаются до неких trusted regions, где данные могут существовать только если удовлетворяют некоторым условиям, а проверки происходят на их границах. Это снижает количество проверок, локализует места появления багов, делает логику более чистой, но за это необходимо платить некоторую цену — в данном случае соблюдение контрактов. Где-то помогает типизация, где-то тестирование. С++ не навязывает своих решений.

S>и надеждой на корректную обработку [b]неочевидных контрактов[b] — соревнования в эквилибристике.
Вот кому неочевидно, тому остается только надеятся.

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, Юрий Жмеренецкий, Вы писали:

ЮЖ>>Уверенность не может быть сама по себе. Она "выводится" из предусловий — где-то компилятором(checked_value), где-то документацией + assert + unit test для него в debug'e.

E>Ничего из этого не может гарантировать отсутствие ошибок в программе.
Использование DbC позволяет уменьшить количество потенциальних мест их появления.

ЮЖ>>Одна — в смысле единственная, может быть и две, но выполнены они будут один раз.
ЮЖ>>Может быть непосредственно перед вызовом max_element, может быть выше по стеку.

E>Если выше по стеку, то сложно этой проверке доверять после проведения рефакторингов.
Если рефакторинг ломает некоторые контракты, то все места их "использования" должны быть проверены каким-либо способом.

ЮЖ>>Вобщем, опять этот плохой С++? Да, нет поддержки со стороны run-time(assert даже не предлагаю =) ). А какая она должна быть ?

E>Посмотрите на Eiffel. Ну или на D, хотя там в постусловиях нет old, если не ошибаюсь.
Для несколькх языков смотрел, мне интересно как это должно выглядеть в С++.

ЮЖ>>типы исключений указывать надо.
E>Не, типы исключений не надо. А вот nothrow-спецификатор очень бы не помешал.
Что должно происходитить при нарушениях контракта ?

E>Ариан 5 взорвался на старте. А спустя несколько лет Mars Climate Orbiter потерпел крушение по аналогичным причинам (неправильное переиспользование кода). Так что не похоже, что даже крах спутников учит программистов читать документацию.
Не все могут учиться на чужом опыте...

Здравствуйте, minorlogic, Вы писали:

M>P.S. Меня кстати в стандартной библиотеке немного удивляет отсутствие класса Range который инкапсулирует пару итераторов.

Отсутствие чего-либо в стандартной библиотеке удивляет наверное всех.

Здравствуйте, Юрий Жмеренецкий, Вы писали:

ЮЖ>Использование DbC позволяет уменьшить количество потенциальних мест их появления.

Может. Но вот нет в C++ DbC. Поэтому использование defensive programming для библиотек мне представляется более надежной техникой.

E>>Если выше по стеку, то сложно этой проверке доверять после проведения рефакторингов.
ЮЖ>Если рефакторинг ломает некоторые контракты, то все места их "использования" должны быть проверены каким-либо способом.

Вспоминается чья-то мудрость: тесты могут показать наличие ошибок в программе, но не могут гарантировать их отсутствие.
Поэтому даже использование unit-тестирования и regression-тестирования не может доказать, что рефакторинг не привнес в программу новых ошибок.

ЮЖ>Для несколькх языков смотрел, мне интересно как это должно выглядеть в С++.

В C++ этого уже не будет. Если только не использовать каких-нибудь внешних нестандартных генераторов/преобразователей кода.

E>>Ариан 5 взорвался на старте. А спустя несколько лет Mars Climate Orbiter потерпел крушение по аналогичным причинам (неправильное переиспользование кода). Так что не похоже, что даже крах спутников учит программистов читать документацию.
ЮЖ>Не все могут учиться на чужом опыте...

О том и речь.

Здравствуйте, eao197, Вы писали:

E>Поэтому использование defensive programming для библиотек мне представляется более надежной техникой.
Уже теплее. А внутри библиотек ?

E>>>Если выше по стеку, то сложно этой проверке доверять после проведения рефакторингов.
ЮЖ>>Если рефакторинг ломает некоторые контракты, то все места их "использования" должны быть проверены каким-либо способом.

E>Вспоминается чья-то мудрость: тесты могут показать наличие ошибок в программе, но не могут гарантировать их отсутствие.
E>Поэтому даже использование unit-тестирования и regression-тестирования не может доказать, что рефакторинг не привнес в программу новых ошибок.
Есть такое. Но чем тогда поможет использование defensive programming и поддержка DbC на уровне языка(не использование, а именно поддержка) ?
Ничем...

ЮЖ>>Для несколькх языков смотрел, мне интересно как это должно выглядеть в С++.
E>В C++ этого уже не будет.
Подвижки были:
Proposal to add Design by Contract to C++
Proposal to add Contract Programming to C++

Здравствуйте, minorlogic, Вы писали:

M>P.S. Меня кстати в стандартной библиотеке немного удивляет отсутствие класса Range который инкапсулирует пару итераторов. С таким классом валидация диапазонов может происходить на этапе конструирования.

Papers n1871, n2068 от Thorsten Ottosen -- planned for a future TR.

Здравствуйте, Юрий Жмеренецкий, Вы писали:

ЮЖ>>>Для несколькх языков смотрел, мне интересно как это должно выглядеть в С++.
E>>В C++ этого уже не будет.
ЮЖ>Подвижки были:
ЮЖ>Proposal to add Design by Contract to C++
ЮЖ>Proposal to add Contract Programming to C++

Уже два года как ведутся в рубрике "Not ready for C++0x, but open to resubmit in future".

Здравствуйте, Юрий Жмеренецкий, Вы писали:

Ю
S>>Если я правильно понимаю, на ФЯ написать некорректную реализацию max_element практически нереально.
S>>Потому, что непустые последовательности там радикально отличаются от пустых. В итоге программист вынужден явно обработать все случаи:0, 1, и больше элементов.
ЮЖ>Это и есть предусловия.
Ну, на самом деле не совсем. Это скорее инварианты. Просто с точки зрения ФП, списки бывают двух существенно разных типов: пустые — [], и сконструированные из [head, tail].
Если программист хочет, чтобы max принимала только второй вид списков, то компилятор защитит его от передачи пустого списка.
Дальше, когда программист попытается сделать рекурсию, ему компилятор не даст напрямую сделать max(tail), потому что tail не гарантирован от []. Значит, придется вручную разрулить ситуацию при помощи pattern matching.

Поскольку список — immutable, я как-то стесняюсь назвать такую типизацию предусловием.
С тем же успехом можно считать, что ссылка в С++ — это указатель с предусловием "не равен NULL".


ЮЖ>Производительность здесь вообще не является главным критерием(это скорее бонус).
Если производительность не является главным критерием, то все пред, пост и прочие условия явно пишутся в коде в виде ассертов.
Но почему-то хардкорные плюсовики со страшной силой критикуют проверку диапазонов на каждый чих в управляемых языках.
ЮЖ>Во-первых, каждую проверку необходимо поддерживать. Если сегодня есть 'a > 0', а завтра нужно сделать 'a > 1', то необходимо править _все_ вхождения.
Вот это мне непонятно. Вхождения чего? Мы говорим о повторно используемой функции и об уровне ее доверия по отношению к вызывающему коду.
ЮЖ>Во-вторых, это банальная логика — прежде чем прыгнуть в басейн, я проверю уровень воды, а вы прыгните в любом случае, плюс необходимо будет добавить реакцию на исключение — "прыгнуть не получилось". Зачем ?
У вас правильные выводы из неправильной логики. Понимаете, функция прыжка — одна, а функций, которые ее используют — много. Заложить проверку в функцию прыжка — гарантировать определенное поведение. Вынуждать делать проверку всех клиентов — не иметь никаких гарантий.
ЮЖ>А потом огрмное количство кода занимается обработкой таких вот фиктивных ошибок. А ведь этот код опять же, надо поддерживать.
Никогда не видел ситуации, где бы обработкой занималось "огромное количество кода". Как правило, стратегий обработки ошибок значительно меньше, чем самих ошибок. Ну природа так устроена. Поэтому классификация исключений — вполне себе нормальный метод структурирования. Если в каком-то конкретном случае обработка ошибочной ситуации происходит прямо по месту вызова, то никто не обязывает делать catch — проверяйте бассейн перед прыжком. Более того, в простых случаях компилятор даже может заинлайнить код, устранить избыточную проверку и выбросить тот фрагмент, который бы бросал исключение в случае ошибки.
Вот, к примеру, в дотнете точно известно, что происходит при разыменовании нулевого указателя: NullReferenceException. Но при этом catch(NullReferenceException) в природе не встречается.
Зато нормой является на границе "региона доверия" проверить аргументы и выбросить ArgumentNullException.
Важно, что эта норма — не обязательная. Если нулевой аргумент будет передан в незащищенную функцию, сценарий будет практически таким же — с той разницей, что место обнаружения может оказаться далеко от места пресупления.
Но то, что вы предлагаете — это UB вместо NullReferenceException, и приятная возможность проверить аргументы превращается в обязанность.

ЮЖ>Да, бывают такие места где проверить не получается(или это сложно) — там приходится прыгать.

ЮЖ>eao197 пропагандирует defensive programming, где все(функции) друг другу не доверяют. Я, в принципе, применяю этот же подход, только более "крупномасштабно": функции разростаются до неких trusted regions, где данные могут существовать только если удовлетворяют некоторым условиям, а проверки происходят на их границах.
Вот это, разумеется, правильный ответ. Но никаких средств поддержки таких регионов в С++ нет. Максимум защиты — это выделение контракта в отдельный класс, занимающийся ассертами и передачей управления приватной реализации, которая уже работает без проверок.
ЮЖ>Это снижает количество проверок, локализует места появления багов, делает логику более чистой, но за это необходимо платить некоторую цену — в данном случае соблюдение контрактов. Где-то помогает типизация, где-то тестирование. С++ не навязывает своих решений.

S>>и надеждой на корректную обработку [b]неочевидных контрактов[b] — соревнования в эквилибристике.
ЮЖ>Вот кому неочевидно, тому остается только надеятся.
Ну, я бы просто предпочел перейти на язык программирования, который позволяет заменить надежды гарантиями. Потому, что понятие "очевидности" не распространяется на программы размером больше 1000 строк.

Здравствуйте, Юрий Жмеренецкий, Вы писали:

E>>Поэтому использование defensive programming для библиотек мне представляется более надежной техникой.
ЮЖ>Уже теплее. А внутри библиотек ?

А внутри библиотек -- это уже тема отдельного разговора. Сам я редко использую defensive programming внутри библиотеки.

Но разговор-то шел о max_element, который как раз располагается на границе.

E>>Поэтому даже использование unit-тестирования и regression-тестирования не может доказать, что рефакторинг не привнес в программу новых ошибок.
ЮЖ>Есть такое. Но чем тогда поможет использование defensive programming и поддержка DbC на уровне языка(не использование, а именно поддержка) ?
ЮЖ>Ничем...

Ну что тут сказать. У меня совершенно противоположное мнение.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Юрий Жмеренецкий, Вы писали:

S>Ю
S>>>Если я правильно понимаю, на ФЯ написать некорректную реализацию max_element практически нереально.
S>>>Потому, что непустые последовательности там радикально отличаются от пустых. В итоге программист вынужден явно обработать все случаи:0, 1, и больше элементов.
ЮЖ>>Это и есть предусловия.
S>Ну, на самом деле не совсем. Это скорее инварианты.
Согласен, я сначала хотел о другом написать, а выделение забыл убрать.

ЮЖ>>Производительность здесь вообще не является главным критерием(это скорее бонус).
S>Если производительность не является главным критерием, то все пред, пост и прочие условия явно пишутся в коде в виде ассертов.
Про постусловия мы пока не говорим, а предусловия — да, выражаются в виде ассертов(с точки зрения С++).

ЮЖ>>Во-первых, каждую проверку необходимо поддерживать. Если сегодня есть 'a > 0', а завтра нужно сделать 'a > 1', то необходимо править _все_ вхождения.
S>Вот это мне непонятно. Вхождения чего?
"проверку диапазонов на каждый чих" по стеку. Ведь при подходе, когда каждая функция не доверяет никому приходится проверять все предусловия ?


ЮЖ>>Во-вторых, это банальная логика — прежде чем прыгнуть в басейн, я проверю уровень воды, а вы прыгните в любом случае, плюс необходимо будет добавить реакцию на исключение — "прыгнуть не получилось". Зачем ?
S>У вас правильные выводы из неправильной логики. Понимаете, функция прыжка — одна, а функций, которые ее используют — много.
Посмотрите с другой стороны: не со стороны функций, а со стороны данных к которым она применяется. Ведь проверять уровень воды можно не только перед прыжком. Я даже не пойду в бассейн, если он закрыт. Проверка в другом месте: Предже чем бассейн будет открыт для посещений в нем необходимо проверить уровень воды.

S>Заложить проверку в функцию прыжка — гарантировать определенное поведение.
Сама по себе попытка прыжка в пустой бассейн — не есть определенное поведение. Вы создаете фиктивное поведение для заведомо ошибочных ситуаций.

S>Вынуждать делать проверку всех клиентов — не иметь никаких гарантий.
Проще гарантировать наличие полного бассейна(сокращается количество мест, из-за ошибок в которых может возникнуть UB), чем выполнять проверки каждый раз при попытке прыгнуть в него.

ЮЖ>>А потом огрмное количство кода занимается обработкой таких вот фиктивных ошибок. А ведь этот код опять же, надо поддерживать.
S>Никогда не видел ситуации, где бы обработкой занималось "огромное количество кода". Как правило, стратегий обработки ошибок значительно меньше, чем самих ошибок.
Чем дальше оттягивается момент проверок, тем больше происходит изменений состояния, которые необходимо откатить. Это лишний код("возвращаться из бассейна домой, если он закрыт").

S>Ну природа так устроена. Поэтому классификация исключений — вполне себе нормальный метод структурирования.
Классификация исключений здесь не играет какой-либо значимой роли.

S>Вот, к примеру, в дотнете точно известно, что происходит при разыменовании нулевого указателя: NullReferenceException. Но при этом catch(NullReferenceException) в природе не встречается.
Такие категоричные заявления опровергаются одним контпримером =)

S>Зато нормой является на границе "региона доверия" проверить аргументы и выбросить ArgumentNullException.
S>Важно, что эта норма — не обязательная. Если нулевой аргумент будет передан в незащищенную функцию, сценарий будет практически таким же — с той разницей, что место обнаружения может оказаться далеко от места пресупления.
Разница может быть огромной. Необходимы гарантии того, что выполняемый код не наломает дров.
Да и для откатов может потребоваться значительной количество любых ресурсов. Эта цена одной проверки выше.

S>Но то, что вы предлагаете — это UB вместо NullReferenceException,
Опять двадцать пять. Еще раз: так или иначе я проверю все аргументы которым я не доверяю. На тех же границах регионов. Этим я гарантирую что везеде где они используются они удовлетворяют предусловиям. Я могу дать гарантии даже для несуществующих компонентов что они получат валидные данные. А у вас по системе будут гулять пустые бассейны. И любой кто их использует должен будет их проверять.

S>и приятная возможность проверить аргументы превращается в обязанность.
Это маленькая цена по сравнению с преимуществами, которые дает эта возможность.

ЮЖ>>... Но никаких средств поддержки таких регионов в С++ нет.
Сговорились с eao197 ?)

S>Максимум защиты — это выделение контракта в отдельный класс, занимающийся ассертами и передачей управления приватной реализации, которая уже работает без проверок.
Так иногда и делается, только вот ассерты != проверки !

S>>>и надеждой на корректную обработку [b]неочевидных контрактов[b] — соревнования в эквилибристике.
ЮЖ>>Вот кому неочевидно, тому остается только надеятся.
S>Ну, я бы просто предпочел перейти на язык программирования, который позволяет заменить надежды гарантиями.
Аха, сначала обеспечиваем наличие в системе пустых бассейнов, в которые можно прыгать, а потом гарантируем что в них никто не прыгнет. Зашибись. И для этого еще требуем поддержку от языка... Это борьба с симптомами, а не с причиной.

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, Юрий Жмеренецкий, Вы писали:

E>>>Поэтому использование defensive programming для библиотек мне представляется более надежной техникой.
ЮЖ>>Уже теплее. А внутри библиотек ?

E>А внутри библиотек -- это уже тема отдельного разговора. Сам я редко использую defensive programming внутри библиотеки.

E>Но разговор-то шел о max_element, который как раз располагается на границе.
В этом случае придется защищаться и от того что 'first > last' и от того что итераторы принадлежат разным доменам.
Здесь я не согласен с тем что max_element располагается на границе.

Здравствуйте, minorlogic, Вы писали:

M>Интереснее было бы если бы вы привели тут итоговый код
Ничего интересного. Ты не привёл точной спецификации.
Например, ты не укзал где искать, что делать, если множество, где искать, пустое, не укзал что возвращаем -- сам максимум или какую-то ссылку/индекс/итератор максимального элемента, если второе, то что делаем, если максимум достигается не на одном элементе. Ну и т. д.

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

Здравствуйте, minorlogic, Вы писали:

M>Проверять или нет возвращаемое значение решает програмист , есть очень много ситуаций когда заранее известно что массив не пустой.

А когда и зачем надо звать max_element если массив может быть пуст? Зачем проверять факт пустоты массива после вызова max_element, а не до?

Здравствуйте, Erop, Вы писали:

E>Почему я этого требую? Да потому, что как-то кто-то тут уже предлагал такие "тесты". Всего вышеоговоренного не оговорил, в результате люди написали ожну функцию, а "экзаменатор" сделал умный вид, и сказал, что хотел совсем другую

Это не экзамен, демонстрационный пример. Жаль что ты не увидел то что я пытался донести.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, minorlogic, Вы писали:

M>>Проверять или нет возвращаемое значение решает програмист , есть очень много ситуаций когда заранее известно что массив не пустой.

E>А когда и зачем надо звать max_element если массив может быть пуст? Зачем проверять факт пустоты массива после вызова max_element, а не до?

И это тоже может выбирать програмист.

Здравствуйте, eao197, Вы писали:

E>Мне сложно назвать мегаудачным решение, при котором миллионы пользователей вынуждены проверять условие, которое мог проверить и обработать один разработчик max_element. Поскольку мне кажется очень странным использование max_element в стиле:
E>

E>std::vector< int > v;
E>... какие-то действия, которые, по мнению разработчика, заполняют v...
E>std::vector< int >::iterator m = std::max_element( v.begin(), v.end() );
E>if( m == v.end() )
E>  // Что за оно вааще?!!
E>

По-моему, если учесть выделенное, то пост-проверка не нужна. Либо кидать исключение при невозможности заполнения, либо проверять v.empty() перед поиском.

std::max_element раелизовано вполне в духе остальных STL алгоритмов, где за валидностью диапазона итераторов приходится следить пользователю (не только пустые диапазоны, но и принадлежность итераторов разным последовательностям...)

Возвращаясь к предложенному тобой набору

Автор: eao197
Дата: 23.08.08

, логичнее (?) иметь пару:

template<class Container> max_element(Container c);
template<class Container> max_element(Container c, const std::nothrow_t&);

Что ж поделать, STL не угадал наперёд путь развития C++, исключения и накопление опыта работы над ошибками... Кстати именно этот

Автор: eao197
Дата: 22.08.08

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

Здравствуйте, gear nuke, Вы писали:


GN>Возвращаясь к предложенному тобой набору

Автор: eao197
Дата: 23.08.08

, логичнее (?) иметь пару:
GN>

template<class Container> max_element(Container c);
GN>template<class Container> max_element(Container c, const std::nothrow_t&);

GN>Что ж поделать, STL не угадал наперёд путь развития C++, исключения и накопление опыта работы над ошибками...

А теперь попробуй применить твою функцию в данном коде:

template< typename RandomAccessIterator >
void selection_sort( RandomAccessIterator first, RandomAccessIterator last )
{
    while( first < --last )
        std::iter_swap( last, std::max_element( first, last + 1 ) );
}

Хотя алгоритмы в виде template<class Container> void some_algo( Container& ); зачастую именно то, что нужно в конечном коде, они совершенно неприменимы для комбинирования с другими алгоритмами для написания новых алгоритмов. Поэтому надо было предлагать оба варианта, и интервальный, и контейнерный. Что впрочем буст и делает.

Здравствуйте, Кэр, Вы писали:

Кэр>Здравствуйте, jazzer, Вы писали:

J>>если тормоза уже заметны, то, очевидно, это уже не преждевременная оптимизация

Кэр>Осталось ответить на вопрос — как они заметны? "На глазок"?

Да, "на глазок".
Поэтому что у пользователя будет глазок, очень похожий на твой, а тебе совсем не хочется, чтобы твои пользователи на весь мир о твоем софте кричали, что он тормозной, если, конечно, ты не Microsoft

Так что это ни разу не преждевременная оптимизация, а самая что ни на есть обычная.

А профайлер только поможет найти конкретное место, которое надо оптимизировать, не более того.

You will always get what you always got
  If you always do  what you always did