Очень простой цикл

[valexey]

Нет никакой сложности. Просто этот цикл не вписывался ни в одни из библиотечных шаблонов. Поэтому пришлось его сочинять. Наивное решение казалось не совсем првильным (что коробило, потому что если уж дело дошло до "ручного" цикла, то хотелось составить его максимально правильно). Решение через КА - черезчур громоздким. Поэтому было интересно кто как такое решает.

Ну вот и я добрался до этой темы :-)
По моему мнению, в данном случае явное использование цикла это явный оверкилл. Ведь задача отлично ложится на один из стандартных библиотечных алгоритмов, а именно - std::search:

Код: [Выделить]

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

template<typename Iterator>
Iterator search_00(Iterator begin, Iterator end) {
    auto tmp = *begin;
    std::array<decltype(tmp),2> what = {0,0};
    return std::search(begin, end,  what.begin(), what.end());
}

int main() {
    auto where = {0,1,2,3,4,0,0,1,2,3,4};
    auto place = search_00(where.begin(), where.end());
    std::cout << "place number: " << place - where.begin() << std::endl;
}

Собственно "ищущих" строк кода тут ровно две, остальное - подготовка данных и вывод.:

Код: [Выделить]

    std::array<decltype(tmp),2> what = {0,0};
    auto place = std::search(begin, end,  what.begin(), what.end());

Как побочный профит - получаем независимость от используемых контейнеров (если они вообще используются - итеротор может быть для stdin - потока ввода) и от типов.

PS. В коде использовал C++11, но std::search есть и в C++98, просто с C++11 чуть покороче обвязка вышла (но не сам поиск).

[valexey]

Вообще, идеальный цикл, это тот которого нет :-) Также как и идеальный SQL-запрос, идеальный полигон и идеальное преобразование Фурье :-)

[vlad]

Ну вот и я добрался до этой темы :-)
По моему мнению, в данном случае явное использование цикла это явный оверкилл. Ведь задача отлично ложится на один из стандартных библиотечных алгоритмов, а именно - std::search:

Хитрый какой std::search использовать нельзя - потому что конец последовательности неизвестен, блин! Чтобы найти конец последовательности и отдать его в std::search - надо сначала найти два нуля

[valexey]

Ну вот и я добрался до этой темы :-)
По моему мнению, в данном случае явное использование цикла это явный оверкилл. Ведь задача отлично ложится на один из стандартных библиотечных алгоритмов, а именно - std::search:

Хитрый какой std::search использовать нельзя - потому что конец последовательности неизвестен, блин! Чтобы найти конец последовательности и отдать его в std::search - надо сначала найти два нуля

Не понял. Конец - это, в частном случае, просто барьер для контейнера. Все остальные примеры решений радостно используют какой-нибудь LEN(a), а чем я хуже? Дискриминация по алгоритмическому признаку шоле?!

:-)

search будет искать пока либо не найдейт что дадено, либо не упрется в end.

[valexey]

Вообще, контрпример давай, где это не будет работать. Показывай твои входные данные, а я попробую на них натянуть std::search. Может тебе из stdin читать что-нибудь? :-) stdin вполне себе "бесконечный".

[vlad]

Вообще, контрпример давай, где это не будет работать. Показывай твои входные данные, а я попробую на них натянуть std::search. Может тебе из stdin читать что-нибудь? :-) stdin вполне себе "бесконечный".

Я там когда свое решение приводил - говорил откуда данные. Голый wchar_t* там, без длины. Избаловался ты на всяких разных ЯВУ...
В случае stdin как раз проблем нет, у него есть eof

[valexey]

Вообще, контрпример давай, где это не будет работать. Показывай твои входные данные, а я попробую на них натянуть std::search. Может тебе из stdin читать что-нибудь? :-) stdin вполне себе "бесконечный".

Я там когда свое решение приводил - говорил откуда данные. Голый wchar_t* там, без длины. Избаловался ты на всяких разных ЯВУ...
В случае stdin как раз проблем нет, у него есть eof

Эмм... Ну нет длины и даже нет eof, и какие от этого тут могут быть проблемы?

Код: [Выделить]

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

template<typename Iterator>
Iterator search_00(Iterator begin, Iterator end) {
    auto tmp = *begin;
    std::array<decltype(tmp),2> what = {0,0};
    return std::search(begin, end,  what.begin(), what.end());
}

int main() {
    char where[] = "hello\0world\0\0here";
    auto place = search_00(where, (char*)nullptr);
    std::cout << "place number: " << (int)(place-where) << std::endl;
}

Все прекрасно работает. Код собственно поиска менять не пришлось, как и обещалось мною ранее :-)

[vlad]

Ответ на сообщение: http://forum.oberoncore.ru/viewtopic.php?p=72961#p72961

Чтобы не казалось, что мой вариант сложнее, перепишу на Обероне-07, где ЦД есть явно:

Код: [Выделить]

i := 0;
oneZero := FALSE; (*oneZero = перед i стоит нуль*)
WHILE (i < LEN(a)) & ~oneZero DO
oneZero := a[i] = 0;
INC(i);
ELSIF (i < LEN(a)) & (a[i] # 0) DO
oneZero := FALSE;
INC(i);
END;


Все равно write-only код. Даже на языке с непосредственной поддержкой ЦД. Что еще раз показывает ненужность данного конструкта в ЯП общего назначения. И нечего пенять на необразованность авторов "более другмх" ЯП.

Рукосуи, не понимающие, с чем "едят" ЦД (это про альтернативно удаленных), не въезжают, что конъюнкция отрицаний охран сразу доказывает корректность цикла:

(i >= LEN(a)) OR (oneZero & (a=0))

Люди, которые не читают код, а только пишут, не понимают, что "конъюнкция отрицаний охран" даже в таком тривиальном примере неочевидна и неявна. Люди, которые читают код, хотят все видеть в явном виде и сразу. А не заниматься коньюнкциями в уме с человеческим правом ошибиться.

И даже не понимают, что это ("сразу дает ...") важно.

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

[vlad]

Все прекрасно работает. Код собственно поиска менять не пришлось, как и обещалось мною ранее :-)

Мда... Признаюсь, о таком хаке как передача заведомо невалидного итератора в качестве конца я не подумал. Подозреваю, что оно будет валится в отладочном режиме любой приличной реализации STL Спасибо за "нестандартное" решение, но в свой в код я такое не вставлю

P.S. Еще можно представить какую-нибудь мультипроцессорную реализацию, которая будет бить последовательность на отрезки по количеству процессоров и искать а параллель. Такая реализация тоже обломается

[valexey]

Рукосуи, не понимающие, с чем "едят" ЦД (это про альтернативно удаленных), не въезжают, что конъюнкция отрицаний охран сразу доказывает корректность цикла:

Код: [Выделить]

(i >= LEN(a)) OR (oneZero & (a[i]=0))

Люди, которые не читают код, а только пишут, не понимают, что "конъюнкция отрицаний охран" даже в таком тривиальном примере неочевидна и неявна. Люди, которые читают код, хотят все видеть в явном виде и сразу. А не заниматься коньюнкциями в уме с человеческим правом ошибиться.

Кстати, да. Результат конъюнкции отрицания охран хочется видеть сразу, в не бегать по коду глазами вычисляя его в уме.

Кстати в именно данном случае " конъюнкция отрицаний охран" сразу ничего не доказывает (даже если привести её в явном виде) хотя бы потому, что в выражении

Код: [Выделить]

(i >= LEN(a)) OR (oneZero & (a[i]=0)) присутствует вычисляемое в теле (точнее в телах) ЦД переменная oneZero, таким образом чтобы удостевериться в правильности результирующего выражения нужно прочитать ВЕСЬ цикл целиком, со всем императивным фаршем внутри, прокрутить в голове по шагам этот цикл. Одних охранных выражений с последующим их отрицанием и конъюнкцией не достаточно.

[valexey]

Все прекрасно работает. Код собственно поиска менять не пришлось, как и обещалось мною ранее :-)

Мда... Признаюсь, о таком хаке как передача заведомо невалидного итератора в качестве конца я не подумал. Подозреваю, что оно будет валится в отладочном режиме любой приличной реализации STL Спасибо за "нестандартное" решение, но в свой в код я такое не вставлю

P.S. Еще можно представить какую-нибудь мультипроцессорную реализацию, которая будет бить последовательность на отрезки по количеству процессоров и искать а параллель. Такая реализация тоже обломается

В обоих случаях не обломается. Просто потому, что в std::search аргументами идут ForwardIterator, а не RandomIterator. Алгоритм std::search не имеет права бить последовательность на куски, не имеет права идти от конца к началу (в любом месте). Я все это постарался учесть перед тем как постить сюда решение :-) nullptr абсолютно валидный в данном случае "конец" последовательности. Вообще ты же знаешь, что end() это итератор "указывающий" на элемент ПОСЛЕ последнего, то есть его разименовывать тоже нельзя.

[vlad]

В обоих случаях не обломается.

Проверил. Падает. И это правильно. VC10.

[vlad]

В обоих случаях не обломается.

По поводу forward итертаоров. Ты уверен, что запрещается специализировать std::search для более специализированных итераторов (random)?

[valexey]

В обоих случаях не обломается.

Проверил. Падает. И это правильно. VC10.

Это очень странно. Я не вижу противоречий стандарту в таком использовании.

[DIzer]

Все равно write-only код. Даже на языке с непосредственной поддержкой ЦД. Что еще раз показывает ненужность данного конструкта в ЯП общего назначения. И нечего пенять на необразованность авторов "более другмх" ЯП.

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