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

E>>>На самом деле, зачем хранить ДВЕ ноды — терминатора, когда можно хранить ОДНУ? То, что возвращает end -- поле list, элемент двусвязного циклического списка. Его next -- это begin списка. Сверху этого всего декоратор, для rbegin и т. д...
BFE>>О звёзды! Это что? В списке всегда хранится один лишний элемент с аллоцированной памятью под пользовательские данные? Какой кошмар...
EP>Нет, необязательно. У end'а может быть другой тип (базовый), не включающий память под пользовательские данные.
Может, но в исходниках именно так. А почему вообще нельзя обойтись без этой ноды?

E>>>Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же?
BFE>>Потому, что список существует как структура и к ней применяется алгоритм. А при поиске цикла в ГПСЧ нам сама структура не нужна, насколько я понимаю.
EP>Алгоритм тот же самый, который как раз обходит структуру. А тот же самый он потому, что структура (в общепринятом математическом смысле) в обоих случаях одинаковая.
EP>А вот выражены ли связи в коде явно как указатели, или же задаются функцией перехода — на применимость алгоритма не влияют

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