Почему std::list<char>::iterator не выходит за начало

#cpp #алгоритм

std::string ss("some unknown word");
std::list word(ss.begin(), ss.end());
auto first = word.begin(), last = word.end(),
        middle = first;
size_t p = ss.size()/2;
std::advance(middle, p);   
while (last != first)
    *(--middle) = *(--last);  //результат:   own wordnown word


И почему этот цикл ведет себя как следующий? 

// while (p--)
//    *(--middle) = *(--last); //результат:    own wordnown word


Ведь, в принципе,  middle  должен был выходить за начало контейнера?!..

Обновление
Если же итератор middle выйдет за пределы контейнера(сначала я думал, что может этого
компилятор не позволяет, т.е. может быть какая то оптимизация),   какое неопределенное
поведение может  влиять на результат следующего?

size_t p = ss.size()/4;
std::advance(middle, p);
while (last != first)
    *(--middle) = *(--last);  //результат:    word word unknown

    

Ответы

Ответ 1

Использование итератора end приведет к неопределенному поведению.

Однако, список может быть построен таким образом, что сам список является узлом,
и таким образом список оказывается закольцованным. Абстрактный пример:

#include 
#include 

struct list_node_base //Базовый узел, который содержит два указателя на соседние узлы
{
    list_node_base * next;
    list_node_base * prev;
};

template
struct list_node: list_node_base //Узел целевого типа добавляет данные к базовому узлу
{
    list_node(T const & src): data(src) {
    }
    T data;
};


template
struct list: list_node_base //Список является узлом самого себя, но без данных
{
    struct iterator {
        T & operator*() {
            return get_pointer()->data;
        }
        T * operator->() {
            return &get_pointer()->data;
        }
        bool operator!=(iterator const & rhv) {
            return p != rhv.p;
        }
        list_node * get_pointer() {
            return static_cast*>(p);
        }
        iterator & operator++() {
            p = p->next;
            return *this;
        }

        list_node_base * p;
    };

    list(): list_node_base{this, this} {//Список в начальном состоянии состоит из
одного узла - самого списка
    }

    void push(T const & v) {
        list_node_base * p = new list_node{T(v)};
        prev->next = p;//this->next исправится автоматически при вставке первого элемента
        p->prev = prev;
        p->next = this;//Элемент следующий за последним - сам список
        prev = p;
    }

    iterator begin() {
        return iterator{next};//На первый узел указывает next
    }

    iterator end() {
        return iterator{this};//Сам список и является узлом end
    }
};


int main()
{
    list lst;
    lst.push("some");
    lst.push("unknown");
    lst.push("word");
    auto current = lst.begin();
    for(unsigned i = 0; i < 10; ++i) {
        if (current != lst.end()) {//Чтобы не разыменовать end
            std::cout << *current << std::endl;//ведь в нем нет члена data
        }
        ++current;//Для нашей реализации это валидно даже для end
    }
}


https://rextester.com/JBC22118

В данном списке все узлы, кроме одного, содержат член data.
Этот "особенный" узел содержит нужные указатели на первый и последний элементы списка,
и является основой итератора end. Так как в этом узле нет члена data, то get_pointer()->data
в итераторе приведет к неопределенному поведению.  

Такие списки достаточно просты и удобны в реализации. 
Подобным способом реализован список в gcc:

//g++  5.4.0

#include 
#include 
#include 

int main()
{
    std::list lst;
    lst.push_back("some");
    lst.push_back("unknown");
    lst.push_back("word");
    auto current = lst.begin();
    for(unsigned i = 0; i < 10; ++i) {
        if (current != lst.end()) {
            std::cout << *current << std::endl;
        }
        ++current;
    }
}


https://rextester.com/VMNO65384


Ответ 2

Итератор middle выйдет за пределы контейнера на 9 итерации, соответственно его разыменование
приведёт к Неопределенному Поведению.