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

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

Я посмотрел в исходниках libstdc++ — насколько я распарсил, там именно так — последний узел имеет только два указателя, без места под данные.
В других реализациях может быть по-другому.

BFE>А почему вообще нельзя обойтись без этой ноды?

Ты имеешь в виду использовать вместо неё nullptr? Не получится — список двусвязный, мы можем взять std::prev от .end(). Можно конечно попробовать без дополнительного узла, но будет сложнее, а главное медленнее.

Да и проблемы в дополнительной ноде нет никакой — она хранится по значению в std::list, и содержит только два указателя которые нужны в любом случае.
То есть схематически там следующая структура данных:

template<typename T, ююю>
class list
{
    struct base_node
    {
        base_node *prev, *next;
    };

    struct value_node : base_node
    {
        T value;
    };
    
    base_node end_node;
    
    ...
};

Из этого кстати вытекает что итератор .end() у такого списка инвалидируется при swap'е и т.п., что не запрещено стандартном:

no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ]

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

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

Я посмотрел в исходниках libstdc++ — насколько я распарсил, там именно так — последний узел имеет только два указателя, без места под данные.
В других реализациях может быть по-другому.

BFE>А почему вообще нельзя обойтись без этой ноды?

Ты имеешь в виду использовать вместо неё nullptr? Не получится — список двусвязный, мы можем взять std::prev от .end(). Можно конечно попробовать без дополнительного узла, но будет сложнее, а главное медленнее.

Да и проблемы в дополнительной ноде нет никакой — она хранится по значению в std::list, и содержит только два указателя которые нужны в любом случае.
То есть схематически там следующая структура данных:

template<typename T, ...>
class list
{
    struct base_node
    {
        base_node *prev, *next;
    };

    struct value_node : base_node
    {
        T value;
    };
    
    base_node end_node;
    
    ...
};

Из этого кстати вытекает что итератор .end() у такого списка инвалидируется при swap'е и т.п., что не запрещено стандартном:

no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ]