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

204

10 июля 2019, 07:20

std::string ss("some unknown word");
std::list<char> 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

Answer 1

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

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

#include <iostream>
#include <string>
struct list_node_base //Базовый узел, который содержит два указателя на соседние узлы
{
    list_node_base * next;
    list_node_base * prev;
};
template<typename T>
struct list_node: list_node_base //Узел целевого типа добавляет данные к базовому узлу
{
    list_node(T const & src): data(src) {
    }
    T data;
};

template<typename T>
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<T> * get_pointer() {
            return static_cast<list_node<T>*>(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>{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<std::string> 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 <iostream>
#include <string>
#include <list>
int main()
{
    std::list<std::string> 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

Answer 2

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