Викторина: как Вы думаете, где ошибка (STL misconception)?

Question

[coodan]

На тему того, как навешивание функциональности без связи с изначальными концепциями может убить идею.

Вот занятный вопрос нашел. Он мне чисто академически интересен был. В моем наивном изложении он звучал бы так - а существует ли бесконечный, замкнутый на свой хвост контейнер STL? В дискуссии на stackoverflow он сформулирован как а существует ли циркулярый итератор для контейнеров STL, что, конечно, выглядит более элегантно и просто.

stackoverflow.com/questions/2616643/is-there-a-sta...

И даже незатейливая реализация предложена:

Iterator cursor;
Iterator begin;
Iterator end;
RingIterator (Container& v) : data(v), cursor(v.begin()), begin(v.begin()), end(v.end()) {}

RingIterator& operator++()
{
++cursor;
if (cursor == end)
cursor = begin;
return *this;
}

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

Главное другое. Скажите, чем глобальная несовместимость с идеями STL? Может Вы несколько видите, тогда поделитесь, пожалуйста, интересно просветиться :)

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

Comments

[Adamos]

Имхо, вы ушли в туман теории и не вернулись.
Есть практика - любой STL контейнер перебирается циклом for от begin до end полностью и один раз.
Программисты привыкли к такой практике. А вы ее ломаете.
Вот вам и глобальная несовместимость с главной идеей STL - стандартной абстракции, подходящей для типовых случаев работы с данными, в общем случае обрабатывающей их эффективнее, чем самодельные велосипеды.

[coodan]

Adamos: С этим не согласен. Практика вторична. Концепция первична. Может, завтра практика концепцию STL поломает, что же теперь, вместе со всеми в колодец прыгать?

[Adamos]

coodan: да, это называется "мэйнстрим".
Посмотрите, сколько вокруг решений defective by design, под которые все вынуждены подстраиваться.
Концепции - просто способ придумать что-то, что в обозримом будущем не окажется граблями. Сами по себе они никого, кроме преподавателей, не волнуют.

Answer 1

[MiiNiPaa]

Если it — валидный итератор к контейнеру container, который можно разыменовать, то следущее условие должно когда-либо стать истинным ++it == container.end() и все промежуточные значения it должны быть валидными и разыменовываемыми.

Можно это обойти, если заставить RingIterator быть равным end в некоторых случаях.

Comments

[coodan]

Интересное математическое рассуждение. Интересно, а где можно почитать о математике, лежащей в основе идеи STL контейнеров и generic programming в целом? Ну, чтобы не рушить их концепций, незаметно для себя. Ведь под этим подходом явно лежит какая-то алгебра. И в этом совершенство их подхода. К каким разделам математики это вообще относится?

Таким образом, исходя из Вашей формулировки, реализация соответствует критериям валидности и разыменовываемости, но условие достижения конца итератором не выполняется, что и определяет его непригодность.

Вообще, замечательная формулировка. Собственно, для практика, когда мы запускаем алгоритм по контейнеру, или просто хотим проитерировать его содержимое принятым способом, мы, естественно, не ожидаем, что запустим бесконечный цикл. Концепция STL вроде бы не подразумевает такой засады :) Но это одна и та же вещь, только в разных формулировках...

Кстати, а если мы хотим невозбранно гулять по кругу в STL контейнере, может быть, алгоритм мог бы взять на себя работу по отслеживанию положения итератора и его подмене в момент достижения конца контейнера? Он исполняет, ему бы и знать когда пойти на новый круг, а когда остановиться? Такой алгоритм нарушил бы концепцию STL, как Вы думаете?

[MiiNiPaa]

coodan: Кстати этот итератор нормально бы работал в качестве адаптера для итераторов, если бы была адекватная возможность остановить итерацию после определённого элемента и были бы прописаны и продуманы правила поведения.

Ограничения и требования к сущностям стандартной библиотеки можно почитать в стандарте.

В основе описания требований к сущностям библиотеки лежит логика. А конкретно: необходимость и достаточность. Необходимым и достаточным условием принадлежности определённой сущности к определённому классу является выполнение всех требований. Принадлежность к суперклассу является достаточным (но не необходимым) условием и т.д.

> Такой алгоритм нарушил бы концепцию STL, как Вы думаете?
Нет. Если придумаете зачем такой алгоритм нужен, как он работает и опишете его поведение во всех спорных ситуациях, то вполне.

Я могу себе представить какой-либо iterative_search который раз за разом обходит последовательность надеясь что другой поток всё же положил искомое значение.

[coodan]

MiiNiPaa: Да, но налицо его избыточные функции. Зачем ему знать пределы контейнера и текущее положение в нем? Это вроде как не его функция.

То есть действительно получается, что циклический контейнер был бы избыточен, циклический итератор недопустим, а вот алгоритму всякими фокусами, рекурсиями и повторными циклами заниматься никто не запрещает, правильно? :)

Сначала оно меня заинтересовало просто так, как диковина - почитал книжку Сферляндия, а там Циркуляндия описана, с жителями, которые убеждены, что живут на бесконечной прямой, а сами сидят в замкнутой окружности. Сразу стало интересно, а в STL контейнерах такое возможно? :) Поглядел что на stackoverflow народ пишет, забавно оказалось.

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

Мне почему-то видится std::list из которого выбирают элементы, на вылет, вне зависимости от текущего положения, но в соответствии с порядком уже выбранных элементов до тех пор, пока алгоритм не обнаружит, что выбрал все и контейнер пуст. Это задачка с количеством циклов, зависящей от порядка в контейнере и его длины.

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

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

[coodan]

MiiNiPaa: Тут, конечно, нельзя не признать, что ходить по кругу, чтобы набирать порядок тоже не менее странная затея - отчего бы тогда не отсортировать для начала? :)

Может, для поиска циклических перестановок фрагментов и правда сгодился бы :)

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